在前面两篇博客中我们分别学习了栈和队列。栈是后进先出LIFO队列是先进先出FIFO两者看起来截然相反却在很多场景下可以互相模拟也可以配合使用来解决更复杂的问题。这篇博客从三个角度展开用两个栈模拟一个队列用两个队列模拟一个栈栈与队列协同解决经典问题回文判断、迷宫最短路径文中所有代码均使用 C 语言实现。一、用两个栈模拟一个队列1. 思路栈是后进先出队列是先进先出。用两个栈可以实现队列inStack专门负责入队outStack专门负责出队规则入队直接压入inStack出队如果outStack不为空直接从outStack弹出如果outStack为空把inStack中所有元素依次弹出并压入outStack然后再从outStack弹出这样元素经过两次“逆序”就变成了先进先出。2. 过程演示依次入队1, 2, 3inStack: [1, 2, 3] (栈顶是 3) outStack: []出队一次把 inStack 全部倒入 outStack inStack: [] outStack: [3, 2, 1] (栈顶是 1) 弹出 outStack 栈顶 - 1 outStack: [3, 2]再出队一次outStack 不为空直接弹出 - 2 outStack: [3]再入队4inStack: [4] outStack: [3]出队outStack 不为空弹出 - 3 outStack: []可以看到出队顺序是1, 2, 3符合先进先出。3. C 语言实现这里复用之前博客中的顺序栈结构。#include stdio.h #include stdlib.h #define MAX_SIZE 100 /* 顺序栈 */ typedef struct { int data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int stackEmpty(const Stack *s) { return s-top -1; } int stackFull(const Stack *s) { return s-top MAX_SIZE - 1; } int stackPush(Stack *s, int value) { if (stackFull(s)) return 0; s-data[s-top] value; return 1; } int stackPop(Stack *s, int *value) { if (stackEmpty(s)) return 0; *value s-data[s-top--]; return 1; } int stackPeek(const Stack *s, int *value) { if (stackEmpty(s)) return 0; *value s-data[s-top]; return 1; } /* 两个栈模拟队列 */ typedef struct { Stack inStack; /* 入队栈 */ Stack outStack; /* 出队栈 */ } QueueByTwoStacks; void initQueueByTwoStacks(QueueByTwoStacks *q) { initStack(q-inStack); initStack(q-outStack); } /* 入队 */ int queueEnqueue(QueueByTwoStacks *q, int value) { return stackPush(q-inStack, value); } /* 把 inStack 中所有元素倒入 outStack */ static void transferInToOut(QueueByTwoStacks *q) { if (!stackEmpty(q-outStack)) { return; /* outStack 不为空不需要倒 */ } int value; while (stackPop(q-inStack, value)) { stackPush(q-outStack, value); } } /* 出队 */ int queueDequeue(QueueByTwoStacks *q, int *value) { transferInToOut(q); return stackPop(q-outStack, value); } /* 查看队头 */ int queuePeek(QueueByTwoStacks *q, int *value) { transferInToOut(q); return stackPeek(q-outStack, value); } /* 判断队列是否为空 */ int queueEmpty(QueueByTwoStacks *q) { return stackEmpty(q-inStack) stackEmpty(q-outStack); }踩坑提示transferInToOut的参数一定要传指针。如果按值传递函数内部修改的是副本出队时outStack永远是空的逻辑就全乱了。4. 复杂度分析入队O(1)出队均摊O(1)。虽然某一次出队可能要把inStack中所有元素搬到outStack但每个元素最多被搬运一次所以均摊下来仍是O(1)。空间O(n)需要两个栈的容量。二、用两个队列模拟一个栈1. 思路用两个队列q1和q2模拟栈始终保证有一个队列为空另一个队列存放所有元素。入栈把元素放入非空队列的队尾。出栈把非空队列中前n-1个元素依次出队并进入空队列剩下的最后一个元素就是“栈顶”直接出队返回。2. 过程演示依次入栈1, 2, 3q1: [1, 2, 3] q2: []出栈一次把 q1 中前 2 个元素移到 q2 q1: [3] q2: [1, 2] q1 弹出 3 - 返回 3 q1: [] q2: [1, 2]再入栈4q2: [1, 2, 4] q1: []出栈一次把 q2 中前 2 个元素移到 q1 q2: [4] q1: [1, 2] q2 弹出 4 - 返回 4 q2: [] q1: [1, 2]可以看到出栈顺序是3, 4符合后进先出。3. C 语言实现这里复用之前博客中的循环队列结构。/* 循环队列 */ typedef struct { int data[MAX_SIZE]; int front; int rear; int size; } CircularQueue; void initCircularQueue(CircularQueue *q) { q-front 0; q-rear 0; q-size 0; } int circularQueueEmpty(const CircularQueue *q) { return q-size 0; } int circularQueueFull(const CircularQueue *q) { return q-size MAX_SIZE; } int circularQueueEnqueue(CircularQueue *q, int value) { if (circularQueueFull(q)) return 0; q-data[q-rear] value; q-rear (q-rear 1) % MAX_SIZE; q-size; return 1; } int circularQueueDequeue(CircularQueue *q, int *value) { if (circularQueueEmpty(q)) return 0; *value q-data[q-front]; q-front (q-front 1) % MAX_SIZE; q-size--; return 1; } /* 两个队列模拟栈 */ typedef struct { CircularQueue q1; CircularQueue q2; } StackByTwoQueues; void initStackByTwoQueues(StackByTwoQueues *s) { initCircularQueue(s-q1); initCircularQueue(s-q2); } /* 入栈 */ int stackPushByQueues(StackByTwoQueues *s, int value) { /* 把元素放入非空队列 */ if (!circularQueueEmpty(s-q1)) { return circularQueueEnqueue(s-q1, value); } else { return circularQueueEnqueue(s-q2, value); } } /* 出栈 */ int stackPopByQueues(StackByTwoQueues *s, int *value) { CircularQueue *nonEmpty, *empty; if (!circularQueueEmpty(s-q1)) { nonEmpty s-q1; empty s-q2; } else if (!circularQueueEmpty(s-q2)) { nonEmpty s-q2; empty s-q1; } else { return 0; /* 栈空 */ } /* 把前 n-1 个元素移到空队列 */ int n nonEmpty-size; int tmp; for (int i 0; i n - 1; i) { circularQueueDequeue(nonEmpty, tmp); circularQueueEnqueue(empty, tmp); } /* 剩下的最后一个元素就是栈顶 */ return circularQueueDequeue(nonEmpty, value); } /* 查看栈顶 */ int stackPeekByQueues(StackByTwoQueues *s, int *value) { CircularQueue *nonEmpty, *empty; if (!circularQueueEmpty(s-q1)) { nonEmpty s-q1; empty s-q2; } else if (!circularQueueEmpty(s-q2)) { nonEmpty s-q2; empty s-q1; } else { return 0; } int n nonEmpty-size; int tmp; for (int i 0; i n - 1; i) { circularQueueDequeue(nonEmpty, tmp); circularQueueEnqueue(empty, tmp); } /* 取出最后一个元素 */ int top; circularQueueDequeue(nonEmpty, top); circularQueueEnqueue(empty, top); /* 再放回去 */ *value top; return 1; } int stackEmptyByQueues(StackByTwoQueues *s) { return circularQueueEmpty(s-q1) circularQueueEmpty(s-q2); }性能优化建议出栈操作是O(n)如果频繁出栈性能会比较差。实际工程中更推荐直接用链表实现栈或者用“双端队列”来兼顾两端操作。4. 复杂度分析入栈O(1)出栈O(n)需要把前n-1个元素搬走空间O(n)两个队列用两个队列模拟栈出栈操作效率比较低。如果追求高效可以直接用栈或链表。但这道题经常出现在面试中考察的是对两种结构本质的理解。三、栈与队列协同解决经典问题1. 回文判断栈 队列思路把字符串同时入栈和入队然后依次比较出栈和出队的字符。如果全部相同就是回文。#include string.h int isPalindrome(const char *str) { Stack s; CircularQueue q; initStack(s); initCircularQueue(q); int len strlen(str); for (int i 0; i len; i) { stackPush(s, str[i]); circularQueueEnqueue(q, str[i]); } while (!stackEmpty(s)) { int a, b; stackPop(s, a); circularQueueDequeue(q, b); if (a ! b) { return 0; } } return 1; }测试abcba - 是回文 abccba - 是回文 abcd - 不是回文这里巧妙地利用了两者的特性栈出栈顺序是逆序队列出队顺序是正序逆序和正序逐一比较正好可以判断回文2. 迷宫最短路径队列BFS求迷宫从起点到终点的最短路径是典型的广度优先搜索BFS必须用队列实现。用栈实现的是深度优先搜索不一定能找到最短路径。思路用队列保存待访问的格子每次从队头取出一个格子向四个方向扩展新格子入队并记录步数第一次到达终点时的步数就是最短路径#define ROW 5 #define COL 5 typedef struct { int x, y; int step; } Point; int maze[ROW][COL] { {0, 0, 0, 0, 0}, {1, 1, 0, 1, 0},