【LeetCode数据结构】栈和队列的应用
🔥个人主页：胡萝卜3.0
🎬作者简介：C++研发方向学习者
📖个人专栏： 《C语言》、《数据结构》 、《C++干货分享》、LeetCode&牛客代码强化刷题
⭐️人生格言：不试试怎么知道自己行不行
目录
一、有效的括号
二、用队列来实现栈
三、用栈来实现队列
四、选择题
一、有效的括号
20. 有效的括号 - 力扣（LeetCode）
题目描述
思路：借助数据结构——栈，遍历字符串，遇到左括号就入栈；遇到右括号就取栈顶元素，看是否匹配，如果成功匹配栈顶元素就出栈，继续遍历字符串；如果不匹配，就直接返回false。
我们根据上面的思路就可以写出相应的代码：
上面的代码看似是正确的，其实还是有些错误的，有些特殊情况没有考虑到。
当第一个字符就是右括号时，该怎么办？当字符串中只有一个左括号时，该怎么办？
当第一个字符就是右括号时，我们执行的取栈顶元素的操作，但是此时栈中并没有元素，栈为空栈，所以我们需要判断栈是否为空，如果栈为空，直接返回false。
当字符串中只有一个左括号时，当遍历结束时，栈不为空，所以当结束遍历时，需要判断栈是否为空，如果为空，返回true；如果不为空，返回false。
代码
bool isValid(char* s) {ST ps;StInit(&ps);STDataType* pi=s;//遍历字符串，遇到左括号，就让其入栈，遇到右括号，让栈顶元素出栈，看是否匹配while(*pi!='\0'){//遇到左括号就入栈if((*pi=='(')||(*pi=='[')||(*pi=='{')){StPush(&ps,*pi);}//遇到右括号就取栈顶元素else{if(StEmpty(&ps)){StDestory(&ps);return false;}STDataType top=StTop(&ps);if(((*pi==')')&&(top!='(')) || ((*pi==']')&&(top!='[')) || ((*pi=='}')&&(top!='{'))){StDestory(&ps);return false;}else{//栈顶元素出栈StPop(&ps);}}pi++;}if(StEmpty(&ps)){StDestory(&ps);return true;}else{StDestory(&ps);return false;}
}二、用队列来实现栈
225. 用队列实现栈 - 力扣（LeetCode）
题目描述
思路：
入栈：往不为空的队列中入数据出栈：将不为空的队列中前size-1个数据依次入为空的队列中，最后一个数据直接出队
取栈顶元素：找不为空的队列，直接返回该队列的队尾数据
将上面思路转换成代码：
typedef struct {Queue q1;Queue q2;
} MyStack;//向操作系统申请栈的空间
MyStack* myStackCreate() {MyStack* st=(MyStack*)malloc(sizeof(MyStack));if(st==NULL){perror("malloc fail!");exit(1);}//队列的初始化QueueInit(&st->q1);QueueInit(&st->q2);return st;
}
//入栈
//往不为空的队列中入数据
void myStackPush(MyStack* obj, int x) {//找出空的队列if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}
//出栈
//把不为空的队列中的前size-1个数据挪到另一个队列中，再将最后一个数据出队列
int myStackPop(MyStack* obj) {//找出空的队列Queue* empty=&obj->q1;Queue* nonempty=&obj->q2;if(!QueueEmpty(empty)){nonempty=&obj->q1;empty=&obj->q2;}int size=QueueSize(nonempty);QDataType top=0;while(size-->1){//取队头top=QueueFront(nonempty);//将队头数据往空的队列中入QueuePush(empty,top);//出队头QueuePop(nonempty);}top=QueueFront(nonempty);QueuePop(nonempty);return top;
}
//取栈顶
int myStackTop(MyStack* obj) {//找出不为空的队列，然后返回队尾数据if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}
//判断栈是否为空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
//销毁栈
void myStackFree(MyStack* obj) {QueueDestory(&obj->q1);QueueDestory(&obj->q2);free(obj);obj=NULL;
}
队列相关代码看：
数据结构初阶：详解栈和队列（下）——队列-CSDN博客
三、用栈来实现队列
232. 用栈实现队列 - 力扣（LeetCode）
题目描述
思路：
入队：往pushst中入数据出队：如果popst为空，将pushst（不为空）中的数据先倒过去再出数据
取队头数据：逻辑和出队的差不多，如果popst为空，将pushst（不为空）中的数据先倒过去，但是不出数据，最后再取队头
将上面思路转换成代码：
//队列的结构
typedef struct {ST pushst;ST popst;
} MyQueue;
//向系统申请一个队列空间
MyQueue* myQueueCreate() {MyQueue* q=(MyQueue*)malloc(sizeof(MyQueue));if(q==NULL){perror("malloc fail!");exit(1);}StInit(&q->pushst);StInit(&q->popst);return q;
}
//入队
//往pushst中入数据
void myQueuePush(MyQueue* obj, int x) {StPush(&obj->pushst,x);
}
//出队
//如果popst为空，将pushst(不为空)中的数据全部挪到popst中，然后出栈
int myQueuePop(MyQueue* obj) {if(StEmpty(&obj->popst)){while(!StEmpty(&obj->pushst)){STDataType top=StTop(&obj->pushst);StPush(&obj->popst,top);StPop(&obj->pushst); }} STDataType top=StTop(&obj->popst);StPop(&obj->popst);return top;
}
//返回队头数据
int myQueuePeek(MyQueue* obj) {if(StEmpty(&obj->popst)){while(!StEmpty(&obj->pushst)){STDataType top=StTop(&obj->pushst);StPush(&obj->popst,top);StPop(&obj->pushst); }} STDataType top=StTop(&obj->popst);return top;
}
//判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {return StEmpty(&obj->pushst)&&StEmpty(&obj->popst);
}
//销毁队列
void myQueueFree(MyQueue* obj) {StDestory(&obj->pushst);StDestory(&obj->popst);free(obj);obj=NULL;
}栈相关代码看：LeetCode&牛客代码强化刷题
四、选择题
一个栈的入栈序列为ABCDE，则不可能的出栈序列为（ D）
A.ABCDE
B.EDCBA
C.DCEBA
D.ECDBA
栈满足后进先出的原则，D选项中E是第一个出栈的，那就说明E是最后一个进栈的，如果E是最后一个进栈，那么出栈的序列应为EDCBA
后续还会有更多题目，敬请期待！！！