企业官网建设流程全解析

在前面两篇博客中，我们分别学习了栈和队列。栈是后进先出（LIFO），队列是先进先出（FIFO），两者看起来截然相反，却在很多场景下可以互相模拟，也可以配合使用来解决更复杂的问题。

这篇博客从三个角度展开：

• 用两个栈模拟一个队列
• 用两个队列模拟一个栈
• 栈与队列协同解决经典问题（回文判断、迷宫最短路径）

文中所有代码均使用 C 语言实现。

一、用两个栈模拟一个队列

1. 思路

栈是后进先出，队列是先进先出。用两个栈可以实现队列：

• inStack：专门负责入队
• outStack：专门负责出队

规则：

• 入队：直接压入inStack
• 出队：
  • 如果outStack不为空，直接从outStack弹出
  • 如果outStack为空，把inStack中所有元素依次弹出并压入outStack，然后再从outStack弹出

这样，元素经过两次“逆序”，就变成了先进先出。

2. 过程演示

依次入队1, 2, 3：

inStack: [1, 2, 3] (栈顶是 3) outStack: []

出队一次：

把 inStack 全部倒入 outStack inStack: [] outStack: [3, 2, 1] (栈顶是 1) 弹出 outStack 栈顶 -> 1 outStack: [3, 2]

再出队一次：

outStack 不为空，直接弹出 -> 2 outStack: [3]

再入队4：

inStack: [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, 3：

q1: [1, 2, 3] q2: []

出栈一次：

把 q1 中前 2 个元素移到 q2 q1: [3] q2: [1, 2] q1 弹出 3 -> 返回 3 q1: [] q2: [1, 2]

再入栈4：

q2: [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},