详解栈和队列面试题(C语言版)，含动图和思路分析

✨✨大家好呀！博主这几天正在用C语言学习简单的数据结构😇😇
🌀🌀刚好学习到了栈和队列，学了这么久，想着能不能找几道题来做做😥😥
🌝🌝虽说用C语言做题着实很痛苦💫💫，被小小地打击了一下😟😟
🐸🐸但也加深了博主对数据结构的理解，下面整理了几道栈和队列的题与大家分享。🌏🌏

山外青山楼外楼，自然探秘永无休
成功易使人陶醉，莫把百尺当尽头

文章目录

😊0.前言😊

前提知识：
C语言实现栈和队列

💥1.栈和队列面试题💥

🌎1.1 括号匹配问题🌎

题目链接
**思路分析：初始化栈，如果是左括号就入栈，如果是右括号就出栈一个左括号元素，出栈了之后与右括号进行匹配，如果不匹配就

return false

，匹配就继续比。如果左右括号的数量不相等怎么办呢？只要在最后判断一下栈是否为空就行了，栈为空

return true；

栈不为空，

return false

；另外只有右括号时也要单独判断一下，因为只有右括号，栈就是空了，此时再出栈就越界了。**
💫友情提醒，return之前别忘了free哦，防止内存泄漏，养成好习惯。💫

//C语言实现栈/******************************************************************************************/typedefchar STDataType;typedefstructStack{
    STDataType* a;int top;// 栈顶的位置int capacity;// 容量}ST;voidStackInit(ST* ps);voidStackDestory(ST* ps);voidStackPush(ST* ps, STDataType x);voidStackPop(ST* ps);
bool StackEmpty(ST* ps);
STDataType StackTop(ST* ps);voidStackInit(ST* ps){assert(ps);
    ps->a =NULL;
    ps->top =0;
    ps->capacity =0;}voidStackDestroy(ST* ps){assert(ps);free(ps->a);
    ps->a =NULL;
    ps->capacity = ps->top =0;}voidStackPush(ST* ps, STDataType x){assert(ps);if(ps->top == ps->capacity){int newCapacity = ps->capacity ==0?4: ps->capacity *2;
        ps->a =(STDataType*)realloc(ps->a, newCapacity*sizeof(STDataType));if(ps->a ==NULL){printf("realloc fail\n");exit(-1);}

        ps->capacity = newCapacity;}

    ps->a[ps->top]= x;
    ps->top++;}voidStackPop(ST* ps){assert(ps);assert(ps->top >0);--ps->top;}

bool StackEmpty(ST* ps){assert(ps);return ps->top ==0;}

STDataType StackTop(ST* ps){assert(ps);assert(ps->top >0);return ps->a[ps->top -1];}/******************************************************************************************///做题
bool isValid(char* s){
    ST st;StackInit(&st);while(*s){//如果是左括号就入栈if(*s =='['||*s =='('||*s =='{'){StackPush(&st,*s);++s;}else{//只有右括号，匹配失败if(StackEmpty(&st))return false;//如果是右括号，出栈一个左括号进行匹配char top =StackTop(&st);StackPop(&st);if((*s==']'&& top !='[')||(*s=='}'&& top !='{')||(*s==')'&& top !='(')){//匹配失败，return false，return之前销毁栈防止内存泄漏StackDestroy(&st);return false;}else{//匹配成功，继续比++s;}}}//栈为空，说明所有括号都匹配了
    bool ret =StackEmpty(&st);StackDestroy(&st);return ret;}

🐸1.2. 用队列实现栈🐸

题目链接

两个队列模拟出栈：

再入栈再出栈：

结构实现：

//C语言实现队列/******************************************************************************************/typedefint QDataType;typedefstructQueueNode{
    QDataType data;structQueueNode* next;}QNode;typedefstructQueue{
    QNode* head;
    QNode* tail;}Queue;voidQueueInit(Queue* pq);voidQueueDestroy(Queue* pq);voidQueuePush(Queue* pq, QDataType x);voidQueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);size_tQueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);voidQueueInit(Queue* pq){assert(pq);
    pq->head = pq->tail =NULL;}voidQueueDestroy(Queue* pq){assert(pq);
    QNode* cur = pq->head;while(cur){
        QNode* next = cur->next;free(cur);
        cur = next;}

    pq->head = pq->tail =NULL;}voidQueuePush(Queue* pq, QDataType x){assert(pq);
    QNode* newnode =(QNode*)malloc(sizeof(QNode));assert(newnode);

    newnode->data = x;
    newnode->next =NULL;if(pq->tail ==NULL){assert(pq->head ==NULL);
        pq->head = pq->tail = newnode;}else{
        pq->tail->next = newnode;
        pq->tail = newnode;}}voidQueuePop(Queue* pq){assert(pq);assert(pq->head && pq->tail);if(pq->head->next ==NULL){free(pq->head);
        pq->head = pq->tail =NULL;}else{
        QNode* next = pq->head->next;free(pq->head);
        pq->head = next;}}

bool QueueEmpty(Queue* pq){assert(pq);return pq->head ==NULL;}size_tQueueSize(Queue* pq){assert(pq);
    QNode* cur = pq->head;size_t size =0;while(cur){
        size++;
        cur = cur->next;}return size;}

QDataType QueueFront(Queue* pq){assert(pq);assert(pq->head);return pq->head->data;}

QDataType QueueBack(Queue* pq){assert(pq);assert(pq->tail);return pq->tail->data;}/******************************************************************************************///做题typedefstruct{
    Queue q1;
    Queue q2;} MyStack;

MyStack*myStackCreate(){
    MyStack* pst =(MyStack*)malloc(sizeof(MyStack));assert(pst);QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;}voidmyStackPush(MyStack* obj,int x){if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}}intmyStackPop(MyStack* obj){assert(obj);//默认q1是空队列，q2是非空队列
    Queue* emptyQ =&obj->q1;
    Queue* nonEmptyQ =&obj->q2;//修正if(!QueueEmpty(&obj->q1)){
        emptyQ =&obj->q2;
        nonEmptyQ =&obj->q1;}//把非空队列的前N-1个数据，倒入空队列//就实现了后进先出while(QueueSize(nonEmptyQ)>1){int front =QueueFront(nonEmptyQ);QueuePush(emptyQ,front);QueuePop(nonEmptyQ);}int top =QueueFront(nonEmptyQ);//剩下一个删掉QueuePop(nonEmptyQ);return top;}intmyStackTop(MyStack* obj){assert(obj);if(!QueueEmpty(&obj->q1)){returnQueueBack(&obj->q1);}else{returnQueueBack(&obj->q2);}}

bool myStackEmpty(MyStack* obj){assert(obj);returnQueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}voidmyStackFree(MyStack* obj){assert(obj);QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);}/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

🌀1.3 用栈实现队列🌀

题目链接

模拟QueuePop：

再入队列再出队列：

// 使用两个数组（栈）和指针定义队列，两个指针分别指向对应的栈顶typedefstruct{int PushSTTop, PopSTTop;int PushST[100], PopST[100];} MyQueue;// 开辟一个队列
MyQueue*myQueueCreate(){
    MyQueue* queue =malloc(sizeof(MyQueue));
    queue->PushSTTop =0;
    queue->PopSTTop =0;return queue;}// 将元素存入输入栈中，存入后栈顶指针 +1voidmyQueuePush(MyQueue* obj,int x){
    obj->PushST[(obj->PushSTTop)++]= x;}intmyQueuePop(MyQueue* obj){// 优化：复制栈顶指针，减少对内存的访问次数int PushSTTop = obj->PushSTTop;int PopSTTop = obj->PopSTTop;// 若输出栈为空if(PopSTTop ==0){// 将输入栈中所有元素复制到输出栈中while(PushSTTop >0){
            obj->PopST[PopSTTop++]= obj->PushST[--PushSTTop];}}// 将输出栈栈顶元素出栈并保存int top = obj->PopST[--PopSTTop];// 将输出栈中元素放回输入栈中while(PopSTTop >0){
        obj->PushST[PushSTTop++]= obj->PopST[--PopSTTop];}// 更新栈顶指针
    obj->PushSTTop = PushSTTop;
    obj->PopSTTop = PopSTTop;// 返回队列中的第一个元素return top;}// 返回输入栈的栈底元素intmyQueuePeek(MyQueue* obj){return obj->PushST[0];}// 若输入栈和输出栈都为空，则队列为空
bool myQueueEmpty(MyQueue* obj){return obj->PushSTTop ==0&& obj->PopSTTop ==0;}// 将栈顶指针都归 0voidmyQueueFree(MyQueue* obj){
    obj->PushSTTop =0;
    obj->PopSTTop =0;}

😇1.4 设计循环队列😇

题目链接

思路分析：

Push:

**为了避免空和满混淆，无法区分，多开一个空间(比如开4个空间只能存3个数据）。当

front==tail

时是空，

tail

的下一个位置是

front

，就是满。满又分为两种情况：**
1.

2.

**此时已经是满了，不能再进行Push数据，必须先

Pop

数据。**
Pop:

**只要队列不是满的，就可以继续插入数据，

front == tail

就删为空。**

继续Push数据：

此时队列又写满了，必须删除数据再写入数据，以此达到循环队列的目的。

typedefstruct{int* a;int front;int tail;int k;} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue*myCircularQueueCreate(int k){
    MyCircularQueue* obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//数组多开一个空间
    obj->a =(int*)malloc(sizeof(int)*(k+1));
    obj->front = obj->tail =0;
    obj->k = k;return obj;}

bool myCircularQueueEnQueue(MyCircularQueue* obj,int value){//满了就不能写入数据if(myCircularQueueIsFull(obj))return false;
    obj->a[obj->tail]= value;//tail走到最后一个空间，到了边界，就置回第一个位置if(obj->tail == obj->k){
        obj->tail =0;}else{
        obj->tail++;}return true;}

bool myCircularQueueDeQueue(MyCircularQueue* obj){//空了就不能删除数据if(myCircularQueueIsEmpty(obj))return false;//front走到最后一个空间，到了边界，置回第一个位置if(obj->front == obj->k){
        obj->front =0;}else{
        obj->front++;}return true;}//取队头数据intmyCircularQueueFront(MyCircularQueue* obj){//题目要求队列为空返回-1if(myCircularQueueIsEmpty(obj))return-1;return obj->a[obj->front];}//取队尾数据intmyCircularQueueRear(MyCircularQueue* obj){//题目要求，空队列返回-1if(myCircularQueueIsEmpty(obj))return-1;//如果tail在第一个位置，队尾是在kif(obj->tail ==0){return obj->a[obj->k];}else{//否则队尾就是tail-1return obj->a[obj->tail-1];}}

bool myCircularQueueIsEmpty(MyCircularQueue* obj){return obj->front == obj->tail;}

bool myCircularQueueIsFull(MyCircularQueue* obj){//满的第二种情况if(obj->tail == obj->k && obj->front ==0){return true;}else{//满的第一种情况return obj->tail+1== obj->front;}}voidmyCircularQueueFree(MyCircularQueue* obj){free(obj->a);free(obj);}/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/