小编主页详情-请点击小编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永远保持先进先出。我们首先看如何判断队列是空还是满。刚开始的时候队列为空此时headtailtail指向下一个要插入的节点。当我们插入四个数据后队列为满此时headtail。我们发现无论是队列为空还是队列为满headtail都是成立的这就说明单纯的headtail来判断队列是空还是满是行不通的。那我们要怎么做呢方法1增加一个size记录队列的大小方法2额外多开一个空间这两种方法都差不多这里我选择用方法2。刚开始的时候队列为空此时headtailtail指向下一个要插入的节点当我们插入四个数据后队列为满此时headtail1。当然这个时候tail再加1就越界的因此每次tail1都需要取模k1保持的下标都在合理的范围。下面这这道题目的完整代码: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*(k1)); obj-headobj-tail0; obj-kk; 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-k1); return true; } bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj-head; obj-head%(obj-k1); 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-tail0?obj-a[obj-k]:obj-a[obj-tail-1]; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj-headobj-tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj-tail1)%(obj-k1)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肯定是越界了。因此我们需要着重处理这种情况。我们可以使用三目操作符判断如果tail0就返回数组最后一个值也就是下标为k的值如果tail0返回下标为tail的值。这里还有一个比较高级的写法return obj-a[(obj-tail-1obj-k1)%(obj-k1)]。就是先加上给tail-1先加上k1再取模k1这样做就能处理tail-1-1的问题。这个式子简写后就是return obj-a[(obj-tailobj-k)%(obj-k1)]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); */结语这篇文章全文由作者手写图片由画图软件所制无AI制作希望各位博友能有所收获欢迎各位博友的讨论觉得不错的小伙伴别忘了点赞关注哦~