前情提要

本章节是数据结构的栈和队列的相关面试题目讲解~

以下的内容一定会让你对栈和队列相关知识的题目,有一个颠覆性的认识哦！！！

❗以下内容以C语言的方式实现❗

以下内容干货满满，跟上步伐吧~

作者介绍：

作者： 热爱编程不起眼的小人物
作者的Gitee：代码仓库
系列文章&专栏推荐： 《刷题特辑》、 《C语言学习专栏》、《数据结构_初阶》

我和大家一样都是初次踏入这个美妙的“元”宇宙 希望在输出知识的同时，也能与大家共同进步、无限进步

导航小助手

• 前情提要
• 面试真题【全面深度解析】
• • ️ 有效的括号【难度：简单】
  • ️ 用队列实现栈【难度：简单】
  • ️用栈实现队列【难度：简单】
  • ️ 设计循环队列【难度：中等】
• 总结

前情提要

• 本次题目涉及面试题解答思路&中等难度题目

• 欢迎大家上手测试一波

面试真题【全面深度解析】

️ 有效的括号【难度：简单】

题目传送门：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合

2. 左括号必须以正确的顺序闭合

• 示例 1：

输入：s = "()"输出：true

• 示例 2：

输入：s = "()[]{}"输出：true

• 示例 3：

输入：s = "(]"输出：false

• 示例 4：

输入：s = "([)]"输出：false

• 示例 5：

输入：s = "{[]}"输出：true

解题关键：

• 我们不难发现这是一个括号匹配的问题，即括号的特性就是一左一右在对应的位置上相互匹配的

• 我们便可以利用此特性，借助栈来实现括号匹配的功能

➡️思路： 栈

❓为什么利用栈这个结构呢

• 1️⃣括号一左一右的特性，刚好符合栈的LIFO（Last in first out）原则

• 2️⃣那这样我们就可以利用栈将左括号类型的括号依次入栈，根据括号需要相互对应的特性，就可以按顺序出栈并依次按顺序与右括号类型比较，看是否匹配

  • 若直至左括号类型全部出栈，且全都匹配的话，说明括号全部匹配，返回true

  • 否则，若中途有不匹配的，则匹配失败，返回false

❗特别注意：

• 因为我们需要借助栈的数据结构，在任何时候返回结果前都需要检查借助数据结构所申请的空间是否释放了，否则会造成内存泄露的问题

特殊情况：

1. 数组没走完，但栈却是NULL的【Eg：第一个元素就为右括号类型】，就可以不用接着匹配下去了，返回false

2. 数组走完了，但栈却不为NULL，那此时相当于还有左括号类型没有得匹配，返回false

✊动图示例：

实现：

1️⃣实现栈

typedef char STDatatype;typedef struct Stack{STDatatype* a;int top;// 栈顶int capacity;}ST; void StackInit(ST* ps);void StackDestroy(ST* ps);void StackPush(ST* ps, STDatatype x);void StackPop(ST* ps);bool StackEmpty(ST* ps);int StackSize(ST* ps);STDatatype StackTop(ST* ps); void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->top = 0; // -1ps->capacity = 0;} void StackDestroy(ST* ps){assert(ps);if (ps->a){free(ps->a);}ps->a = NULL;ps->top = 0; ps->capacity = 0;} void StackPush(ST* ps, STDatatype x){assert(ps);// 检查空间够不够，不够就增容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 " />4 : ps->capacity * 2;STDatatype* tmp = realloc(ps->a, sizeof(STDatatype)*newcapacity);if (tmp == NULL){printf("rellaoc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;} ps->a[ps->top] = x;ps->top++;} void StackPop(ST* ps){assert(ps);assert(!StackEmpty(ps)); --ps->top;} bool StackEmpty(ST* ps){assert(ps); return ps->top == 0;} int StackSize(ST* ps){assert(ps); return ps->top;} STDatatype StackTop(ST* ps){assert(ps);assert(!StackEmpty(ps)); return ps->a[ps->top - 1];}

2️⃣实现括号匹配功能

bool isValid(char * s){ST st;StackInit(&st);bool match = true;while(*s){if(*s == '[' || *s == '(' || *s == '{'){StackPush(&st, *s);s++;}else{//数组还没走完，//但栈已经空了if(StackEmpty(&st)){match = false;break;}char ch = StackTop(&st);StackPop(&st);if((*s == ']' && ch != '[')|| (*s == '}' && ch != '{')|| (*s == ')' && ch != '(')){match = false;break;}else{s++;}}}//双重保险，预防上述第二种特殊情况if(match == true){match = StackEmpty(&st);} StackDestroy(&st);return match;}

️ 用队列实现栈【难度：简单】

题目传送门：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素
• int top() 返回栈顶元素
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false

示例 1：

输入：["MyStack", "push", "push", "top", "pop", "empty"][[], [1], [2], [], [], []]输出：[null, null, null, 2, 2, false]解释：MyStack myStack = new MyStack();myStack.push(1);myStack.push(2);myStack.top(); // 返回 2myStack.pop(); // 返回 2myStack.empty(); // 返回 False

解题关键：

• 理解好队列与栈各自的特性，并试想如何利用此特性去操作两个队列模拟实现一个栈【即实现栈的LIFO特性】

➡️思路： 本质由队列底层实现栈

• 1️⃣实现pop接口

• 两个队列实现pop（出栈）接口，即实现后进先出，但队列的性质是先进先出，刚好相反，我们要怎么实现呢？

• 此时就刚好体现两个队列的作用了，将两个队列分为空队列、 非空队列【非空or空是依据队列是否为空来灵活定义的，随时变化的】

• 将 不为空的队列 的数据出队列入到 空队列 当中，当非空队列只剩下一个元素时，就可以pop，达到LIFO的目的

❗这里很巧妙的利用特性即达到后进后出，也达到即使元素在队列间不断出入，也没有改变在栈的角度看这些元素之间的顺序发生改变

✊动图示例：

• 2️⃣实现push接口

• 为了可以像执行pop后一样依旧保持“栈”内的压栈的顺序不变，我们选择往不为空的队列里插入数据，就可以实现同样效果

✊动图示例：

• 3️⃣实现top接口

• 判断两个队列中哪个是非空队列，并返回其队尾的结点即可

• 4️⃣实现empty接口

• 判断两个队列是否都为NULL，是则返回true，否则返回false

实现：

1️⃣实现队列的数据结构

typedef int QDataType;typedef struct QueueNode{struct QueueNode* next;QDataType data;}QNode;typedef struct Queue{//int size;QNode* head;QNode* tail;}Queue;void QueueInit(Queue* pq);void QueueDestroy(Queue* pq);void QueuePush(Queue* pq, QDataType x);void QueuePop(Queue* pq);QDataType QueueFront(Queue* pq);QDataType QueueBack(Queue* pq);bool QueueEmpty(Queue* pq);int QueueSize(Queue* pq);void QueueInit(Queue* pq){assert(pq);pq->head = pq->tail = NULL;}void QueueDestroy(Queue* pq){assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}void QueuePop(Queue* pq){assert(pq);assert(!QueueEmpty(pq));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;}}QDataType QueueFront(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}QDataType QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL;}int QueueSize(Queue* pq){assert(pq);QNode* cur = pq->head;int size = 0;while (cur){++size;cur = cur->next;}return size;}

2️⃣模拟实现栈的接口

typedef struct {Queue q1;Queue q2;} MyStack; //初始化“栈”MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;} //pushvoid myStackPush(MyStack* obj, int x) {//给非空队列进行入队操作if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else{QueuePush(&obj->q2, x);}} //popint myStackPop(MyStack* obj) {Queue* pEmpty = &obj->q1, *pNonEmpty = &obj->q2;if(!QueueEmpty(&obj->q1)){pEmpty = &obj->q2;pNonEmpty = &obj->q1;}while(QueueSize(pNonEmpty) > 1){QueuePush(pEmpty, QueueFront(pNonEmpty));QueuePop(pNonEmpty);}int top = QueueFront(pNonEmpty);//队尾元素出队QueuePop(pNonEmpty);return top;} //topint myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}} //emptybool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);} //释放void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);}

️用栈实现队列【难度：简单】

题目传送门：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾

• int pop() 从队列的开头移除并返回元素

• int peek() 返回队列开头的元素

• boolean empty() 如果队列为空，返回 true ；否则，返回 false

示例 1：

输入：["MyQueue", "push", "push", "peek", "pop", "empty"][[], [1], [2], [], [], []]输出：[null, null, null, 1, 1, false]解释：MyQueue myQueue = new MyQueue();myQueue.push(1); // queue is: [1]myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)myQueue.peek(); // return 1myQueue.pop(); // return 1, queue is [2]myQueue.empty(); // return false

解题关键：

• 理解好队列与栈各自的特性，并试想如何利用此特性去操作两个栈模拟实现一个队列【即实现队列的FIFO特性】

➡️思路： 本质由栈的底层实现队列

• 1️⃣实现pop接口

• 两个栈实现pop（出队列）接口，即实现先进先出，但栈的性质是后进先出，刚好相反，我们要怎么实现呢？

• 此时就刚好体现两个栈的作用了，将两个队列分为专门入数据的栈、 专门出数据的栈

• 将 专门入数据的栈 的数据出栈入到 专门出数据的栈 ，但正因为栈是后进先出的特性，导致数据入到另外一个栈里的顺序就是逆转过后的【不同于队列实现栈】，那此时就可以按照栈的特性去pop，达到队列的LIFO的目的

• 这也是为什么令一个栈为专门入数据的栈，另外一个栈为专门出数据的栈

❗这里很巧妙的利用特性即达到先进后出，正是因为数据从一个栈里出来再入到另外一个栈里的顺序发生改变，从而可以直接利用后进先出达到先进先出的效果

✊动图示例：

✨综上：

• 我们只要每次想出队列的时候，直接看专门出数据的栈进行出数据即可，所以我们可以先判断专门出数据的栈是否为NULL

  • 若为NULL，则将专门入数据的栈里的数据入到专门出数据的栈里，再由专门出数据的栈进行pop

  • 若不为NULL，则可以直接在专门出数据的栈利用后进先出栈的特性，达到队列先进先出对于原本数据的出队列的顺序要求

• 2️⃣实现push接口

• 为了可以依旧保持“队列”内的元素的顺序不变，我们选择往专门如数据的栈里插入数据，就可以实现顺序不变的效果

✊动图示例：

• 3️⃣实现peek接口

• 判断专门出数据的栈是否为空，若不为空则可直接栈顶的数据获取到队列的队头数据

• 4️⃣实现empty接口

• 判断两个栈是否都为NULL，是则返回true，否则返回false

实现：

1️⃣实现栈的数据结构

typedef int STDataType;//数组实现栈typedef struct Stack{STDataType* a;int capacity; //容量，方便增容int top; // 表示栈顶}Stack;//初始化void StackInit(Stack* pst);//销毁void StackDestory(Stack* pst);//插入void StackPush(Stack* pst, STDataType x);//删除void StackPop(Stack* pst);//取栈顶的数据【返回栈顶的数据】STDataType StackTop(Stack* pst);//判断栈内是否为空bool StackEmpty(Stack* pst);//返回栈内数据的个数int StackSize(Stack* pst);void StackInit(Stack* pst){assert(pst);pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);pst->top = 0;pst->capacity = 4;}//销毁void StackDestory(Stack* pst){assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;}//插入数据void StackPush(Stack* pst, STDataType x){assert(pst);if (pst->top == pst->capacity){//增容STDataType* tmp = (STDataType*)realloc(pst->a,sizeof(STDataType) * pst->capacity * 2);if (tmp == NULL){printf("realloc fail\n");exit(-1);//结束程序//这个-1不是return，而是给进程的，直接结束整个程序（return是结束当前函数） }pst->a = tmp;pst->capacity = pst->capacity * 2;}pst->a[pst->top] = x;pst->top++;}//尾删【实际 就是删除排在最后，最晚插进来的 栈顶】void StackPop(Stack* pst){//跟之前一样，对栈顶的数据进行删除时//没必要抹除这个数据，只需要不访问到它就行assert(pst);//这里唯一需要考虑的是：这个栈里面是不是空的assert(!StackEmpty(pst)); //判断是不是 非空的pst->top--;}//返回栈顶的数据STDataType StackTop(Stack*pst){assert(pst);//需要判断是不是不为空的assert(!StackEmpty(pst));return pst->a[pst->top - 1];}//判断栈内是否为空bool StackEmpty(Stack* pst){assert(pst);return pst->top == 0; //如果等于0，则说明为真，即 如果为空，就返回TURE//不为0，不为空，则返回 FALSE}//返回栈内数据的个数int StackSize(Stack* pst){assert(pst);return pst->top; //top就是大小}

2️⃣模拟实现队列的接口

typedef struct {Stack pushST;Stack popST;} MyQueue;//初始化MyQueue* myQueueCreate(){MyQueue*q = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&q->pushST);StackInit(&q->popST);return q;}//插入void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->pushST,x);}//出队列int myQueuePop(MyQueue* obj) {assert(obj);if(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}int top = StackTop(&obj->popST);StackPop(&obj->popST);return top;}//获取对头的数据int myQueuePeek(MyQueue* obj) {if(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}return StackTop(&obj->popST);}//emptybool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->popST)&&StackEmpty(&obj->pushST);}//释放void myQueueFree(MyQueue* obj) {StackDestory(&obj->pushST);StackDestory(&obj->popST);free(obj);}

️ 设计循环队列【难度：中等】

题目传送门：

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k

• Front: 从队首获取元素。如果队列为空，返回 -1

• Rear: 获取队尾元素。如果队列为空，返回 -1

• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真

• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真

• isEmpty(): 检查循环队列是否为空

• isFull(): 检查循环队列是否已满

解题关键：

• 要着重设计通过头尾指针表示出循环队列的结束标志和循环队列为NULL的标志

• 循环队列不像队列，队列没有空间可以增容，但循环队列的空间是有限的

➡️思路： 用数组实现循环队列

• 1️⃣ 当我们创造的空间大小与所需空间大小相等时，我们便无法再借助头尾指针去表示循环队列什么时候为NIULL，什么时候空间满了

  • 所以此时我们便可以通过创造比实际需求多1个空间的循环队列给予头尾指针更多的操作空间

• 2️⃣判空条件即为：tail == front

• 3️⃣判断队列满的条件：【tail+1= tailNext】tailNext== front

• 4️⃣push的时候就根据tail走的去入数据

• 5️⃣pop的时候就用front去走一步以达到删除一个元素的目的，因为front表示的队头的下标，如果队头下标移动了，说明判空条件也随着front下标的移动而移动，到时候原来的队头位置的数据就会因为入新的数据而被覆盖

❗特别注意：

• tail的下标本质指向的是没有数据的空间，即tail-1下标指向的才是有数据的空间，因为每一次push之后，tail++就是指向”无数据”的空间了

• 删除数据并不需要真正的删除，而是以覆盖代替删除，达到删除的效果，只要判断队列满了之后，tail走一步就是队列为空的条件，那tail再循环遍历队列的话，就是覆盖删除了

✊动图示例：

实现：

typedef struct {int* a;int k;//记录队列实际个数的大小int front; //头的下标int tail;//本质：指向的是真正有数据的结点的下一个结点//【因为tail指向的地方是没有数据的，而上一个是有数据的】} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq->a = (int*)malloc(sizeof(int) * (k+1));cq->front = 0;cq->tail = 0;cq->k = k;return cq;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->tail;}bool myCircularQueueIsFull(MyCircularQueue* obj) {int tailNext = obj->tail+1;if(tailNext == obj->k+1) //说明此时tail已经到达空间的尾{tailNext = 0;// 那此时next就为 队列的头}return tailNext == obj->front;}//入数据bool myCircularQueueEnQueue(MyCircularQueue* obj, int value){if(myCircularQueueIsFull(obj)){return false;}else{obj->a[obj->tail] = value;obj->tail++;//如果tail此时在尾巴上if(obj->tail == obj->k+1){obj->tail = 0;}return true;}}//出数据bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}else{obj->front++;if(obj->front == obj->k+1){obj->front = 0;}return true;}}//取头int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];}//取尾 -- tail的前一个int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}//极端情况：tail = 0的时候if(obj->tail == 0){return obj->a[obj->k];}return obj->a[obj->tail-1];}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);}

总结

综上，我们基本了解了数据结构中的 “栈和队列重要面试真题” 的知识啦~~

恭喜你的内功又双叒叕得到了提高！！！

感谢你们的阅读

后续还会继续更新，欢迎持续关注哟~

如果有错误❌，欢迎指正呀

✨如果觉得收获满满，可以点点赞支持一下哟~✨