【经典题目】栈和队列面试题（括号匹配问题、用队列实现栈、设计循环队列、用栈实现队列）-洪萨配资

小编主页详情<-请点击
小编gitee代码仓库<-请点击

本文主要介绍了栈和队列面试题（括号匹配问题、用队列实现栈、设计循环队列、用栈实现队列），内容全由作者原创（无AI），同时深度解析了每道题目的解题思路和解决方法，并带有配图帮助博友们更好的理解，点个关注不迷路，下面进入正文~~

1.括号匹配问题

2.用队列实现栈

3.设计循环队列

4.用栈实现队列

结语：

1.括号匹配问题

题目链接：有效的括号

这道题目就可以很好的使用栈来完成。

核心思路：
1.左括号入栈
2.右括号出栈与左括号匹配。如果全部都能匹配返回true，否则返回false

其中有两个需要注意的地方：

1.当全部符号都遍历完时，要判断栈是否为空，如果不为空，说明栈还有剩余的左括号没有和右括号进行匹配，说明匹配失败，要返回false。如果栈确实为空，就返回true。

2.如果给定的字符串是下图时：

如果当前栈已经为空，却还有右括号要和左括号匹配，这个时候访问一个为空的栈程序会报错。因此，在右括号和左括号匹配之前，要先判断当前链表是否为空，如果为空，直接返回false；如果不为空。右括号再和左括号进行匹配。

完整代码如下图所示：

typedef char SLDataType; typedef struct Stact { SLDataType* a; int top; int capacity; }ST; // 初始化和销毁 void STInit(ST* pst); void STDestroy(ST* pst); // 入栈 出栈 void STPush(ST* pst,SLDataType x); void STPop(ST* pst); // 取栈顶数据 SLDataType STTop(ST* pst); // 判空 bool STEmpty(ST* pst); // 获取数据个数 int STSize(ST* pst); void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->capacity = pst->top = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->capacity = pst->top = 0; } // 入栈 出栈 void STPush(ST* pst, SLDataType x) { assert(pst); if (pst->capacity == pst->top) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(pst->a, newcapacity * sizeof(SLDataType)); if (tmp == NULL) { perror("STpush"); return; } pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { assert(pst); assert(pst->top > 0); pst->top--; } // 取栈顶数据 SLDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top - 1]; } // 判空 bool STEmpty(ST* pst) { assert(pst); /*if (pst->top == 0) { return true; } return false;*/ return pst->top == 0; } // 获取数据个数 int STSize(ST* pst) { assert(pst); return pst->top; } bool isValid(char* s) { ST st; STInit(&st); while(*s!='\0') { if(*s=='('||*s=='{'||*s=='[') { STPush(&st,*s); } else { if(STEmpty(&st)) { STDestroy(&st); return false; } if(STTop(&st)=='('&&*s!=')' ||STTop(&st)=='{'&&*s!='}' ||STTop(&st)=='['&&*s!=']') { STDestroy(&st); return false; } STPop(&st); } s++; } bool ret = STEmpty(&st); STDestroy(&st); return ret; }

为了养成良好的代码习惯，在返回false之前，可以先把栈给释放掉。

2.用队列实现栈

题目链接：用队列实现栈

这题的关键任务是用两个队列实现栈。首先我们先要充分认识到队列是先进先出，而栈是后进先出，这就说明单纯的用队列的出数据逻辑是完不成出栈的。

那我们到底要怎么完成这道题目呢？先看下面的图片

我们此时往第一个队列插入了4个数据1、2、3、4，如果说要出栈的话，应当要出4。按照出队列的方法我们只能出1，那么如果我们把4前面的123先保存在第二个队列里，是不是就可以把4出栈了。

按照这个逻辑，我们的进数据就可以往有数据的队列进，保持一定的逻辑性。要出数据时，就把要出的数据的前面的所有数据都先暂时保存在另一个空链表中。

核心思路：保持一个存数据，一个为空。入数据不入空的队列，出数据通过空的导一下

题目完整代码如下：

typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType val; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }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); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq); void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("QueuePush"); return; } newnode->val = x; newnode->next = NULL; if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(pq->size != 0); if (pq->phead == pq->ptail) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } // 取队头和队尾的数据 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->val; } QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->ptail); return pq->ptail->val; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst; } void myStackPush(MyStack* obj, int x) { if(QueueEmpty(&(obj->q1))) { QueuePush(&(obj->q2),x); } else { QueuePush(&(obj->q1),x); } } int myStackPop(MyStack* obj) { Queue* empty = &(obj->q1); Queue* nonempty = &(obj->q2); if(QueueEmpty(&(obj->q2))) { empty = &(obj->q2); nonempty = &(obj->q1); } while(QueueSize(nonempty)>1) { QueuePush(empty,QueueFront(nonempty)); QueuePop(nonempty); } int ret = QueueFront(nonempty); QueuePop(nonempty); return ret; } int myStackTop(MyStack* obj) { if(QueueEmpty(&(obj->q1))) { return QueueBack(&(obj->q2)); } else { return QueueBack(&(obj->q1)); } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&(obj->q1))&&QueueEmpty(&(obj->q2)); } void myStackFree(MyStack* 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); */

需要注意的是，在释放obj之前要先把obj里面的q1和q2先释放掉

这道题目虽然理解起来不难，但是逻辑较复杂且内容繁多，是一道不错的联系题，还希望博友们多多练习，多多交流~

3.设计循环队列

题目链接：设计循环队列

循环队列可以使用链表或数组实现，这里选择用数组。

循环队列简单来说就是有限空间的队列，当空间满了就不能插入。如果有数据出了空间，就可以继续插入。

总的来说要在有限空间保持先进先出，重复使用。
因此我们可以使用指针head和tail分别遍历数组，如果有新的数据插入，tail就往后走一位；如果有数组删除，head就往后走一位。这样能保证出数据的head和进出数据的tail永远保持先进先出。

我们首先看如何判断队列是空还是满。

刚开始的时候，队列为空，此时head==tail，tail指向下一个要插入的节点。

当我们插入四个数据后，队列为满，此时head==tail。我们发现无论是队列为空还是队列为满，head==tail都是成立的，这就说明单纯的head==tail来判断队列是空还是满是行不通的。那我们要怎么做呢？

方法1：增加一个size记录队列的大小
方法2：额外多开一个空间

这两种方法都差不多，这里我选择用方法2。

刚开始的时候，队列为空，此时head==tail，tail指向下一个要插入的节点

当我们插入四个数据后，队列为满，此时head==tail+1。当然这个时候tail再加1就越界的，因此每次tail+1都需要取模k+1，保持的下标都在合理的范围。

下面这这道题目的完整代码:

typedef struct { int* a; int head; int tail; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = ( MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a = (int*)malloc(4*(k+1)); obj->head=obj->tail=0; obj->k=k; return obj; } bool myCircularQueueIsFull(MyCircularQueue* obj); bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->a[obj->tail]=value; obj->tail++; obj->tail%=(obj->k+1); return true; } bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->head++; obj->head%=(obj->k+1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else return obj->a[obj->head]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else return obj->tail==0?obj->a[obj->k]:obj->a[obj->tail-1]; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->head==obj->tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->tail+1)%(obj->k+1)==obj->head; } void myCircularQueueFree(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); */

这里我们着重要讲一下myCircularQueueRear函数的实现。这个函数的作用是返回对列的最后一个值。当循环队列为空时，直接返回-1；如果循环队列不为空，因为tail是指向要插入下一个数据的位置，所以循环队列最后一个数据的位置应当是tail-1。可如果此时循环队列是下图的情况呢？

此时tail-1肯定是越界了。因此我们需要着重处理这种情况。我们可以使用三目操作符判断，如果tail==0就返回数组最后一个值，也就是下标为k的值；如果tail！=0返回下标为tail的值。

这里还有一个比较高级的写法，return obj->a[(obj->tail-1+obj->k+1)%(obj->k+1)]。就是先加上给tail-1先加上k+1再取模k+1，这样做就能处理tail-1==-1的问题。这个式子简写后就是

return obj->a[(obj->tail+obj->k)%(obj->k+1)]

4.用栈实现队列

题目链接：用栈实现队列

这道题目我们依旧可以使用“用队列实现栈”的思路去解决，不过稍微有点区别。

例如，我们现在先插入四个数据，如果这个时候我们想拿出一个数据，我们拿出的应该是1，因为队列是先进先出。可是我们现在的方法只能先拿出4，使用“用队列实现栈”的思路，先把数据都移动到另一个栈。

此时我们再去数据就可以顺利的把1给取出来。那我们下次取数据还需要再移动数据吗？

答案是不用！

我们观察到如果我们再把栈的数据去出来刚好就是2，符合队列的顺序。因此我们就可以固定一个栈用来存数据，另一个栈用来出数据。

那么为什么用队列实现栈就需要移动数据呢？因为用队列实现栈不会改变数据的顺序，而用栈实现队列会改变。如上图所示，出数据的顺序原来4、3、2、1，保存到另一个栈出数据的顺序就变成了1、2、3、4，刚好与队列出数据的顺序相同。

下面为题目的完成代码：

typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; // 初始化和销毁 void STInit(ST* pst); void STDestroy(ST* pst); // 入栈 出栈 void STPush(ST* pst,STDataType x); void STPop(ST* pst); // 取栈顶数据 STDataType STTop(ST* pst); // 判空 bool STEmpty(ST* pst); // 获取数据个数 int STSize(ST* pst); // 初始化和销毁 void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->capacity = pst->top = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->capacity = pst->top = 0; } // 入栈 出栈 void STPush(ST* pst, STDataType x) { assert(pst); if (pst->capacity == pst->top) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror("STpush"); return; } pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { assert(pst); assert(pst->top > 0); pst->top--; } // 取栈顶数据 STDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top - 1]; } // 判空 bool STEmpty(ST* pst) { assert(pst); /*if (pst->top == 0) { return true; } return false;*/ return pst->top == 0; } // 获取数据个数 int STSize(ST* pst) { assert(pst); return pst->top; } typedef struct { ST psuhst; ST popst; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); STInit(&obj->psuhst); STInit(&obj->popst); return obj; } void myQueuePush(MyQueue* obj, int x) { STPush(&obj->psuhst,x); } int myQueuePeek(MyQueue* obj); int myQueuePop(MyQueue* obj) { int pop = myQueuePeek(obj); STPop(&obj->popst); return pop; } int myQueuePeek(MyQueue* obj) { if(STEmpty(&obj->popst)) { while(!STEmpty(&obj->psuhst)) { int top = STTop(&obj->psuhst); STPush(&obj->popst,top); STPop(&obj->psuhst); } } return STTop(&obj->popst); } bool myQueueEmpty(MyQueue* obj) { return STEmpty(&obj->psuhst)&&STEmpty(&obj->popst); } void myQueueFree(MyQueue* obj) { STDestroy(&obj->psuhst); STDestroy(&obj->popst); free(obj); } /** * Your MyQueue struct will be instantiated and called as such: * MyQueue* obj = myQueueCreate(); * myQueuePush(obj, x); * int param_2 = myQueuePop(obj); * int param_3 = myQueuePeek(obj); * bool param_4 = myQueueEmpty(obj); * myQueueFree(obj); */