我们这里针对栈和队列的一些经典算法题做详细讲解:
1.括号匹配问题.
2.用队列实现栈.
3.用栈实现队列.
4.设计循环队列.
一.详细讲解如下:
1.括号匹配问题.(如下图)
给定一个只包括 '('，')'，'{'，'}'，'['，']'?的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。(试题来源力扣)
//判断括号是否匹配
bool isValid(char * s){
if(NULL==s){//判空
return false;
}
if('}'==s[0] || ']'==s[0] || ')'==s[0]){//判断是否只有一个元素
return false;
}
int i=0;
Stack St;
StackInit(&St);//创建和初始化栈
while(s[i]!='\0'){
if('['==s[i] || '{'==s[i] || '('==s[i]){//为左括号的就入栈
StackPush(&St,s[i]);
}else{//不是左括号就与栈顶元素作比较,为一组就出栈继续向后走,不为一组直接返回false.
if((StackTop(&St)=='[' && ']'==s[i])||
(StackTop(&St)=='(' && ')'==s[i])||
(StackTop(&St)=='{' && '}'==s[i])){
StackPop(&St);
}else{
return false;
}
}
i++;
}
if(0==StackSize(&St)){//如果循环走完并且栈为空说明所有括号都可以匹配,直接返回true.
return true;
}
return false;//否则返回false.
}2.用队列实现栈.
使用两个队列来对栈进行实现:首先我们得知道队列是"先进先出"的一个特性所以我们就可以利用它这个特性来实现栈(后进先出),入栈时我们可以把所有元素全放进一个队列中,出栈时将这个有元素的队列中的元素只留一个剩下的全进入另一个空的队列,此时留在队列中的这个元素就是最后一个进入队列的元素也就是最后一个入栈的元素,令它出队列,也就是出栈,然后重复上面的操作就完成了对栈的实现.(如下图)
//实现栈
typedef struct {
Queue q1;
Queue q2;
} MyStack;
//创建栈的结构体
MyStack* myStackCreate() {
MyStack* l=(MyStack*)malloc(sizeof(MyStack));
if(NULL==l){
printf("申请失败!\n");
return NULL;
}
QueueInit(&(l->q1));
QueueInit(&(l->q2));
return l;
}
//入栈
void myStackPush(MyStack* obj, int x) {
if(NULL==obj){
return;
}
if(obj->q1._front==obj->q1._rear){
QueuePush(&(obj->q2),x);
}else{
QueuePush(&(obj->q1),x);
}
}
//出栈
int myStackPop(MyStack* obj) {
if(1==_myStackEmpty(obj)){
return NULL;
}
int data=0;
if(obj->q1._front==obj->q1._rear){
while(obj->q2._rear!=obj->q2._front->_next){
QueuePush(&(obj->q1),QueueFront(&(obj->q2)));
QueuePop(&(obj->q2));
}
data=obj->q2._rear->_data;
QueuePop(&(obj->q2));
}else{
while(obj->q1._rear!=obj->q1._front->_next){
QueuePush(&(obj->q2),QueueFront(&(obj->q1)));
QueuePop(&(obj->q1));
}
data=obj->q1._rear->_data;
QueuePop(&(obj->q1));
}
return data;
}
//取栈顶元素
int myStackTop(MyStack* obj) {
if(1==_myStackEmpty(obj)){
return NULL;
}
if(obj->q1._front==obj->q1._rear){
return QueueBack(&(obj->q2));
}else{
return QueueBack(&(obj->q1));
}
}
//判空
int _myStackEmpty(MyStack* obj){
if(NULL==obj){
return 1;
}
if(obj->q1._front==obj->q1._rear && obj->q2._front==obj->q2._rear){
return 1;
}
return 0;
}
//栈判空
bool myStackEmpty(MyStack* obj) {
if(NULL==obj){
return true;
}
if(obj->q1._front==obj->q1._rear && obj->q2._front==obj->q2._rear){
return true;
}
return false;
}
//销毁栈
void myStackFree(MyStack* obj) {
if(NULL==obj){
return;
}
free(obj);
obj=NULL;
}
3.用栈实现队列.
与用队列实现栈相似,也是使用两个栈的后进先出的特点来实现队列,入队列时选定一个栈用来做入队列的栈(记作S1)(另一个空队列记作S2),只要时入队列的元素直接插入S1,然后就是出队列,元素总数记作n,将S1中的n-1个元素全进入S2中,然后将S1中剩下的一个元素取出便是出队列,之后再将S2中的元素再次全放入S1中,使S2继续保持空的状态,之后的出队列入队列重复前面两项操作就行.(如下图)
//用栈实现队列
typedef struct {
Stack s1;
Stack s2;
} MyQueue;
//创建队列的结构体(两个栈)
MyQueue* myQueueCreate() {
MyQueue* _queue=(MyQueue*)malloc(sizeof(MyQueue));
if(NULL==_queue){
printf("申请失败!\n");
return NULL;
}
StackInit(&(_queue->s1));
StackInit(&(_queue->s2));
return _queue;
}
// 判空
int isQueueEmpty(MyQueue* obj){
if(NULL==obj){
return 1;
}
if(0==obj->s1._top && 0==obj->s2._top){
return 1;
}
return 0;
}
//入队列
void myQueuePush(MyQueue* obj, int x) {
if(NULL==obj){
printf("结构体不存在!\n");
return;
}
StackPush(&(obj->s1),x);
}
//出队列
int myQueuePop(MyQueue* obj) {
if(isQueueEmpty(obj)){
return NULL;
}
int data=0;
while(obj->s1._top!=0){
StackPush(&(obj->s2),StackTop(&(obj->s1)));
StackPop(&(obj->s1));
}
data=StackTop(&(obj->s2));
StackPop(&(obj->s2));
while(obj->s2._top!=0){
StackPush(&(obj->s1),StackTop(&(obj->s2)));
StackPop(&(obj->s2));
}
return data;
}
//返回队列的头元素
int myQueuePeek(MyQueue* obj) {
if(isQueueEmpty(obj)){
return NULL;
}
int data=0;
while(obj->s1._top!=0){
StackPush(&(obj->s2),StackTop(&(obj->s1)));
StackPop(&(obj->s1));
}
data=StackTop(&(obj->s2));
while(obj->s2._top!=0){
StackPush(&(obj->s1),StackTop(&(obj->s2)));
StackPop(&(obj->s2));
}
return data;
}
//判空
bool myQueueEmpty(MyQueue* obj) {
if(NULL==obj){
return true;
}
if(0==obj->s1._top){
return true;
}
return false;
}
//销毁队列
void myQueueFree(MyQueue* obj) {
if(NULL==obj){
return;
}
free(obj);
obj=NULL;
}
4.设计循环队列.
我们使用数组,外加Head和Rear两个首尾指针来创建循环队列,队列的大小提前给好为n,入队列时让Rear移动插入数据,Head移动出队列,当Head等于Rear时队列为空,当(Rear+1)%n等于Head时队列为满.(如图)
//定义结构体使用动态数组
typedef struct {
int* _loop_queue_list;
int _head;
int _rear;
int _capacity;
} MyCircularQueue;
//创建循环链表
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* _loop_queue=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if(NULL==_loop_queue){
printf("申请失败!\n");
return NULL;
}
_loop_queue->_head=0;
_loop_queue->_rear=0;
_loop_queue->_capacity=k+1;
_loop_queue->_loop_queue_list=(int*)malloc(sizeof(int)*(k+1));
return _loop_queue;
}
//判满
int isFull(MyCircularQueue* obj){
if((obj->_rear+1)%(obj->_capacity)==(obj->_head)){
return 1;
}
return 0;
}
//判空
int isEmpty(MyCircularQueue* obj){
if(obj->_head==obj->_rear){
return 1;
}
return 0;
}
//入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(isFull(obj)){
return false;
}
obj->_rear=(obj->_rear+1)%(obj->_capacity);
obj->_loop_queue_list[obj->_rear]=value;
return true;
}
//出队列
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(isEmpty(obj)){
return false;
}
obj->_head=(obj->_head+1)%(obj->_capacity);
obj->_loop_queue_list[obj->_head]=-1;
return true;
}
//获取队列首元素
int myCircularQueueFront(MyCircularQueue* obj) {
if(isEmpty(obj)){
return -1;
}
return obj->_loop_queue_list[(obj->_head+1)%(obj->_capacity)];
}
//获取队列尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
if(isEmpty(obj)){
return -1;
}
return obj->_loop_queue_list[obj->_rear];
}
//队列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if(NULL==obj){
return true;
}
if(obj->_head==obj->_rear){
return true;
}
return false;
}
//队列判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if(NULL==obj){
return true;
}
if((obj->_rear+1)%(obj->_capacity)==(obj->_head)){
return true;
}
return false;
}
//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {
if(NULL==obj){
return;
}
free(obj);
obj=NULL;
}