第36篇： 数据结构核心：栈与队列深度解析

目录

一、📦 栈：后进先出的“子弹夹”

什么是栈？

底层实现：数组 vs 链表

代码实现（基于数组）

二、🚇 队列：先进先出的“排队系统”

什么是队列？

底层实现：链表胜出

代码实现（基于链表）

三、⚔️ 实战：经典算法题

第一题 有效的括号

💡 核心思路：利用栈的“匹配消除”特性

🛠️ 代码演进：从“繁琐”到“优雅”

🚀 最终专业实现

第二题 用队列实现栈

💡 核心思路：利用双队列的“搬运”特性

🛠️ 代码演进：从“暴力”到“巧妙”

1. 初学者的直觉（暴力法）

2. 优化策略：化繁为简（只动一次）

🚀 最终专业实现

📝 复杂度分析

💡 为什么选这种写法？

第三題 用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

核心思路：双栈的“负负得正”效应

🛠️ 代码演进：从“每次必搬”到“按需搬运”

1. 初学者的直觉（笨办法）

2. 优化策略：懒惰搬运（推荐）

🚀 最终专业实现

📝 总结与复杂度分析

第四题 进阶：循环队列

💡 1. 为什么要搞个“圈”？（解决假溢出）

🧠 2. 核心难点：如何优雅地“转圈”？

⚔️ 3. 最大的坑：怎么区分“空”和“满”？

方法一：少用一个空间（最常用，推荐）

方法二：多开一个空间（代码最简）

方法三：使用计数器 (size)

💻 4. 代码实现（C语言 - 计数器法）

📝 重点总结

在数据结构的世界里，栈和队列是两种最基础但也最重要的线性表。它们不仅在日常编程中无处不在，更是操作系统、编译器乃至高并发系统的基石。

今天我们就结合经典课件与实战经验，彻底搞懂这两个“性格迥异”的数据结构。

一、📦 栈：后进先出的“子弹夹”

什么是栈？

栈是一种特殊的线性表，它有着严格的纪律：只允许在固定的一端进行插入和删除操作。

• 栈顶：进行数据插入和删除的一端。
• 栈底：固定不动的一端。
• 核心原则：后进先出。

想象一下手枪的弹夹，最后压入的子弹会最先被打出去。

底层实现：数组 vs 链表

虽然栈可以用数组或链表实现，但数组通常是更优的选择。

• 数组实现：在数组尾部进行插入和删除操作的时间复杂度为 O(1)，且内存连续，缓存命中率高。
• 链表实现：虽然也能实现，但需要额外的指针空间，且频繁的内存分配效率略低。

代码实现（基于数组）

我们定义一个动态增长的栈结构：

typedef int STDataType; typedef struct Stack { STDataType* a; // 指向动态开辟的数组 int top; // 栈顶指针（通常指向栈顶元素的位置，或下一个可插入位置） int capacity; // 容量 } ST; // 核心接口声明 void STInit(ST* ps); // 初始化 void STDestroy(ST* ps); // 销毁 void STPush(ST* ps, STDataType x); // 入栈 void STPop(ST* ps); // 出栈 STDataType STTop(ST* ps); // 获取栈顶元素 int STSize(ST* ps); // 获取有效元素个数 bool STEmpty(ST* ps); // 判空

💡 补充思考：在实现top变量时，有两种常见流派。一种是top指向当前栈顶元素（初始化-1），另一种是top指向下一个可插入的位置（初始化0）。后者在计算元素个数时直接返回top即可，逻辑上往往更简洁。

void STInit(ST* ps)// 初始化 { assert(ps); ps->a = NULL; ps->top = ps->capacity = 0; } void STDestroy(ST* ps) // 销毁 { assert(ps); if (ps->a) free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } void STPush(ST* ps, STDataType x) // 入栈 { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail:\n"); exit(1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top++] = x; } bool STEmpty(ST* ps) // 判空 { assert(ps); return ps->top == 0; } void STPop(ST* ps) // 出栈 { assert(!STEmpty(ps)); ps->top--; } STDataType STTop(ST* ps) // 获取栈顶元素 { assert(ps); return ps->a[ps->top-1]; } int STSize(ST* ps) // 获取有效元素个数 { assert(ps); return ps->top; }

二、🚇 队列：先进先出的“排队系统”

什么是队列？

队列也是一种特殊的线性表，但它允许在一端插入，在另一端删除。

• 队尾：进行插入操作。
• 队头：进行删除操作。
• 核心原则：先进先出。

就像我们在超市结账排队，先来的人先结账离开。

底层实现：链表胜出

与栈不同，队列的实现通常推荐使用链表。

• 数组的劣势：如果使用普通数组，出队列需要删除头部元素，这会导致后续所有元素向前移动，时间复杂度高达 O(N)。
• 链表的优势：维护一个头指针和一个尾指针，入队在尾部插，出队在头部删，时间复杂度均可为 O(1)。

代码实现（基于链表）

为了高效操作，我们需要维护头尾两个指针：

typedef int QDataType; // 队列结点结构 typedef struct QueueNode { QDataType val; struct QueueNode* next; } 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); // 取队尾数据 bool QueueEmpty(Queue* pq); int QueueSize(Queue* pq);

#include"queue.h" void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* pcur = pq->phead; while (pcur) { QNode* next = pcur->next; free(pcur); pcur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } void QueuePush(Queue* pq, QDataType x) // 入队（尾） { assert(pq); QNode* newnode = (QNode*)mealloc(sizeof(QNode)); if (newnode == NULL) { perror("QNode fail:"); exit(1); } newnode->val = x; newnode->next = NULL; if (pq->ptail == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; } void QueuePop(Queue* pq) // 出队（头） { assert(pq); assert(!QueueEmpty(pq)); 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(!QueueEmpty(pq)); return pq->phead->val; } QDataType QueueBack(Queue* pq) // 取队尾数据 { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->val; } int QueueSize(Queue* pq) { assert(pq); return pq->size; }

三、⚔️ 实战：经典算法题

掌握了基础结构后，我们来看看 LeetCode 上的经典面试题，这些题目考察的是对数据结构的灵活运用。

第一题 有效的括号

20. 有效的括号 - 力扣（LeetCode）

💡 核心思路：利用栈的“匹配消除”特性

解决括号匹配问题，最直觉的方法就是利用栈（Stack）的“后进先出”特性。我们可以把整个过程想象成一种“消除游戏”：

1. 遇到左括号：说明需要等待一个右括号来闭合，将其入栈。
2. 遇到右括号：说明需要寻找最近的左括号进行匹配，将栈顶元素出栈比对。
3. 最终判定：如果遍历完字符串后，栈为空（所有括号都完美消除），则字符串有效；否则无效。

🛠️ 代码演进：从“繁琐”到“优雅”

在写具体逻辑时，初学者很容易写出下面这种“繁琐”的代码： 遇到右括号时，先判断栈是否为空，再取栈顶元素，然后用一大串if-else去判断左右括号是否对应。如果不匹配，还要记得销毁栈再返回false。

痛点分析：

1. 匹配逻辑嵌套太深，阅读体验差。
2. 在循环中多次调用STDestroy(&st); return false;，一旦后续增加逻辑，极易遗漏清理步骤，导致内存泄漏。

优化策略： 我们不妨换个思路——取反面。不要一直去判断“什么时候该继续”，而是直接找出“什么时候该直接判定失败”。只要遇到以下三种情况，直接break跳出循环：

1. 栈为空，但遇到了右括号。
2. 栈顶的左括号与当前右括号不匹配。
3. 字符串遍历结束，但栈里还有未消除的左括号。

🚀 最终专业实现

结合上述思路，我们可以将代码重构得更加清晰、健壮：

/** * @brief 判断给定的括号字符串是否有效 * @param s 待检测的括号字符串 * @return true 如果括号有效，否则返回 false */ bool isValid(const char* s) { // 1. 防御性编程：检查空指针 if (s == NULL) return false; ST st; STInit(&st); bool valid = true; // 默认假设有效，遇到异常再置为 false // 2. 遍历字符串进行匹配消除 while (*s != '\0') { // 遇到左括号，直接入栈等待匹配 if (*s == '(' || *s == '{' || *s == '[') { STPush(&st, *s); } // 遇到右括号，进行匹配验证 else { // 异常1：栈为空，说明没有左括号可以匹配 if (STEmpty(&st)) { valid = false; break; } // 异常2：栈顶左括号与当前右括号不匹配 char topChar = STTop(&st); bool isMatch = (topChar == '(' && *s == ')') || (topChar == '{' && *s == '}') || (topChar == '[' && *s == ']'); if (!isMatch) { valid = false; break; } // 匹配成功，弹出栈顶左括号（完成一次消除） STPop(&st); } s++; } // 异常3：遍历结束，但栈内还有残留的左括号 if (valid && !STEmpty(&st)) { valid = false; } // 3. 统一释放栈资源，防止内存泄漏 STDestroy(&st); return valid; }

第二题 用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

💡 核心思路：利用双队列的“搬运”特性

首先我们要明确两个数据结构的本质区别：

• 队列 (Queue)：先进先出（FIFO），像排队买票，先来的先走。
• 栈 (Stack)：后进先出（LIFO），像叠盘子，最后放上去的最先拿走。

矛盾点在于：队列只能从队头取数据，而栈要求取“最新”的数据。解决策略：既然队列取不到最新的，我们就把旧的都移走，让“最新”的那个变成队头。我们需要两个队列：

1. 主队列 (q1)：用来存储最终排好序的数据，保证队头永远是栈顶元素。
2. 辅助队列 (q2)：作为“中转站”，在插入新元素时暂存旧数据。

🛠️ 代码演进：从“暴力”到“巧妙”

1. 初学者的直觉（暴力法）

很多人第一反应是：每次push进q1，然后执行pop操作时，把q1的前 N-1 个元素全部倒腾到q2，取出最后一个，再把q2倒回q1。

缺点：太麻烦了！每次pop都要把数据搬来搬去两次，效率极低。

2. 优化策略：化繁为简（只动一次）

我们可以换个角度：不要等到pop时才整理数据，而是在push时就把它排好序。

具体步骤：

1. 新元素x进来时，先放入空的辅助队列q2。
2. 将主队列q1中的所有旧元素依次出队，并进入q2。
   • 此时，q2的顺序变成了：[新元素 x, 旧元素1, 旧元素2...]
3. 交换q1和q2的角色（或者直接赋值）。
   • 现在q1的队头就是刚才进来的x，完美符合栈的特性！

这样，pop、top和empty操作就变得极其简单，直接对q1操作即可。

🚀 最终专业实现

这种写法将复杂逻辑集中在push中，保持了其他操作的高效（O(1) 时间复杂度）。

//上面是 Queue.h 和 Queue.c (包含 QueueInit, QueuePush, QueuePop, QueueFront, QueueEmpty, QueueDestroy) typedef struct { Queue q1; // 主队列：始终保持栈的顺序（队头即栈顶） Queue q2; // 辅助队列：用于 push 时的临时中转 } MyStack; /** * 创建并初始化栈 */ MyStack* myStackCreate() { MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } /** * 入栈操作 * 核心逻辑：先把新元素放进空队列，再把旧元素全搬过来 */ void myStackPush(MyStack* obj, int x) { // 1. 新元素先入辅助队列 q2 QueuePush(&obj->q2, x); // 2. 将主队列 q1 的所有旧元素搬运到 q2 // 这样 q2 的顺序就变成了：[新元素, 旧元素1, 旧元素2 ...] while (!QueueEmpty(&obj->q1)) { int front = QueueFront(&obj->q1); QueuePop(&obj->q1); QueuePush(&obj->q2, front); } // 3. 交换 q1 和 q2 // 现在 q1 又变成了主队列，且队头是最新的元素 Queue tmp = obj->q1; obj->q1 = obj->q2; obj->q2 = tmp; } /** * @brief 出栈操作 * 因为 push 时已经排好序，直接取队头即可 */ int myStackPop(MyStack* obj) { int val = QueueFront(&obj->q1); QueuePop(&obj->q1); return val; } /** * @brief 获取栈顶元素 */ int myStackTop(MyStack* obj) { return QueueFront(&obj->q1); } /** * @brief 判断栈是否为空 */ bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1); } /** * @brief 销毁栈，释放内存 */ void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); }

📝 复杂度分析

• 时间复杂度：
  • push: O(N)O(N) 。因为每次入栈都需要把旧元素搬运一次。
  • pop,top,empty: O(1)O(1) 。直接操作队头，非常快。
• 空间复杂度： O(N)O(N) 。需要两个队列来存储 NN 个元素。

💡 为什么选这种写法？

虽然push慢了一点，但在实际业务中，我们往往希望读取数据（pop/top）越快越好。这种“写入时整理”的策略，保证了后续操作的丝滑流畅，非常适合读多写少的场景。

第三題 用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

核心思路：双栈的“负负得正”效应

首先我们要明确两个数据结构的本质区别：

• 栈 (Stack)：后进先出 (LIFO)。像叠盘子，最后放上去的在最上面。
• 队列 (Queue)：先进先出 (FIFO)。像排队，最先来的最先走。

矛盾点：栈只能从顶部取数据（最新的），而队列要求从底部取数据（最老的）。
解决策略：利用数学上的“负负得正”原理。如果我们把数据从一个栈倒入另一个栈，数据的顺序就会反转一次。

我们需要两个栈：

1. 输入栈 (pushST)：专门负责接收新进来的数据。
2. 输出栈 (popST)：专门负责提供队头数据。当需要pop或peek时，如果输出栈为空，就将输入栈的数据全部倒过来。

🛠️ 代码演进：从“每次必搬”到“按需搬运”

1. 初学者的直觉（笨办法）

很多人第一反应是：为了保证顺序，每次push一个新元素，我都把旧元素倒腾一遍，让新元素沉底；或者每次pop完，为了维持原状，又把数据倒回去。

痛点分析：这样做的复杂度太高了！每次操作都要移动所有元素，时间复杂度是 O(N)，效率极低。

2. 优化策略：懒惰搬运（推荐）

其实我们不需要时刻保持数据是有序的。只有当我们需要取数据（pop或peek），且输出栈为空时，才进行搬运。

具体逻辑：

• 出队/查看 (pop/peek)：
  • 检查popST是否有数据？
  • 如果有：直接弹出/查看栈顶（这就是最早进入的那个元素）。
  • 如果没有：将pushST里的所有数据依次弹出，压入popST。此时popST的栈顶就是我们要找的“队头”。

为什么这样是对的？
假设依次入栈 1, 2, 3。pushST从底到顶是 [1, 2, 3]。
倒入popST后，popST从底到顶变成 [3, 2, 1]。
此时popST的栈顶是 1，正是最先入队的元素！完美符合队列特性。

🚀 最终专业实现

结合你之前提供的Stack接口，我们可以写出非常优雅的代码。

typedef struct { Stack pushST; // 输入栈：只管进 Stack popST; // 输出栈：只管出 } MyQueue; /** 初始化队列 */ MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&obj->pushST); StackInit(&obj->popST); return obj; } /** 入队操作：直接压入输入栈 */ void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushST, x); } /** * 辅助函数：确保输出栈有数据 * 只有当输出栈为空时，才把输入栈的数据导过来 */ void moveDataIfEmpty(MyQueue* obj) { if (StackEmpty(&obj->popST)) { while (!StackEmpty(&obj->pushST)) { // 将输入栈顶元素弹出，压入输出栈 StackPush(&obj->popST, StackTop(&obj->pushST)); StackPop(&obj->pushST); } } } /** 出队操作 */ int myQueuePop(MyQueue* obj) { // 1. 先保证输出栈里有数据 moveDataIfEmpty(obj); // 2. 弹出输出栈顶（即队头） int front = StackTop(&obj->popST); StackPop(&obj->popST); return front; } /** 查看队头元素 */ int myQueuePeek(MyQueue* obj) { // 1. 先保证输出栈里有数据 moveDataIfEmpty(obj); // 2. 返回输出栈顶，但不弹出 return StackTop(&obj->popST); } /** 判断队列是否为空 */ bool myQueueEmpty(MyQueue* obj) { // 只有两个栈都为空，队列才为空 return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST); } /** 释放内存 */ void myQueueFree(MyQueue* obj) { StackDestroy(&obj->pushST); StackDestroy(&obj->popST); free(obj); }

📝 总结与复杂度分析

这种“双栈法”是面试中的标准答案。

• 时间复杂度：
  • push是 O(1)。
• 空间复杂度：O(N)，需要两个栈来存储数据。

第四题 进阶：循环队列

622. 设计循环队列 - 力扣（LeetCode）

💡 1. 为什么要搞个“圈”？（解决假溢出）

想象你在排队买奶茶：

• 普通队列（数组版）：队伍一直往后排。前面的人买完走了，前面的位置就空了。但是后面不断有人来，队伍越来越长，最后超出了店门（数组越界）。哪怕前面空了一万个位置，你也得说“满了”，这就是假溢出。
• 循环队列：把队伍首尾相连。当最后一个人买完走了，新来的人可以回到最前面的空位继续排队。这就叫循环利用空间。

🧠 2. 核心难点：如何优雅地“转圈”？

在代码里，我们不能真的把数组连成环，我们是通过**取模运算（%）**来模拟“回头”的动作。

假设数组长度为k，当前下标是i：

• 普通前进：i + 1
• 循环前进：(i + 1) % k

原理解析：
如果k=5，当前下标是 4（最后一个位置）。
(4 + 1) % 5=5 % 5=0。
看！下标瞬间回到了起点。这就是“循环”的魔法。

⚔️ 3. 最大的坑：怎么区分“空”和“满”？

这是这道题唯一的考点。
当front（头指针）和rear（尾指针）重合时，既可能是空（没人），也可能是满（挤爆了）。

有三种解法。

方法一：少用一个空间（最常用，推荐）

• 规定：数组虽然开了k个大小，但我们只存k-1个数据。永远留一个空位作为“警戒线”。
• 判空：front == rear
• 判满：(rear + 1) % k == front（意思是：尾指针再走一步就要追上头指针了，这时候就算满了）。

方法二：多开一个空间（代码最简）

• 做法：题目要求容量为k，我们实际分配k + 1的空间。
• 好处：逻辑和方法一完全一样，但对外接口来说，你就是存了k个数，不需要在计算时减来减去，非常不容易出错。

方法三：使用计数器 (size)

• 做法：额外定义一个变量size记录当前元素个数。
• 判空：size == 0
• 判满：size == capacity
• 评价：这种方法最简单粗暴，完全避开了指针重合的问题，也是工程上常用的做法。

💻 4. 代码实现（C语言 - 计数器法）

这里使用**方法三（计数器法）**来实现，因为它的逻辑最清晰，最不容易在下标计算上晕头转向。

typedef struct { int* a; // 动态数组 int front; // 队头下标 int rear; // 队尾下标（指向下一个插入位置） int k; // 容量限制 int size; // 当前元素个数（关键变量） } MyCircularQueue; // 1. 创建 MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); // 注意：这里分配 k 个空间就够了 obj->a = (int*)malloc(sizeof(int) * k); obj->k = k; obj->front = 0; obj->rear = 0; obj->size = 0; return obj; } // 2. 入队 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { // 先检查满没满 if (obj->size == obj->k) { return false; } // 放入数据 obj->a[obj->rear] = value; // 移动尾指针（利用 % 实现循环） obj->rear = (obj->rear + 1) % obj->k; // 计数加 1 obj->size++; return true; } // 3. 出队 bool myCircularQueueDeQueue(MyCircularQueue* obj) { // 先检查空没空 if (obj->size == 0) { return false; } // 移动头指针（利用 % 实现循环） obj->front = (obj->front + 1) % obj->k; // 计数减 1 obj->size--; return true; } // 4. 获取队头 int myCircularQueueFront(MyCircularQueue* obj) { if (obj->size == 0) { return -1; } return obj->a[obj->front]; } // 5. 获取队尾 int myCircularQueueRear(MyCircularQueue* obj) { if (obj->size == 0) { return -1; } // 难点：rear 指向的是“下一个空位”，所以真正的队尾是 rear 的前一个 // 为了防止 rear 为 0 时减 1 变成负数，我们需要加上 k 再取模 int index = (obj->rear - 1 + obj->k) % obj->k; return obj->a[index]; } // 6. 判空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->size == 0; } // 7. 判满 bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->size == obj->k; } // 8. 销毁 void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }

📝 重点总结

1. 取模运算%是灵魂：
   在循环队列中，任何指针的移动都不能直接+1，必须是(index + 1) % capacity。这保证了指针永远在0到capacity-1之间跳动。

2. Rear函数的陷阱：
   大多数时候rear指向的是“下一个要插入的位置”（空位）。所以获取最后一个元素时，需要找rear - 1。
   特别注意：当rear在0号位置时，rear - 1会变成-1，导致数组越界。
   万能公式：(rear - 1 + k) % k。这个公式能完美处理rear为 0 的情况（例如(0 - 1 + 5) % 5 = 4，正确回到了数组末尾）。

📌 总结

希望这篇博客能帮你理清栈和队列的脉络！如果有代码实现上的疑问，欢迎在评论区留言。

🌟 写在最后
代码写完了，但我想对正在阅读这篇博客的你说几句心里话。
最近身边有很多同学在迷茫、害怕，大体原因是只能靠自己一个人在这个世界打拼，无依无靠；而世界又在不断变化进步，不知道自己的出路在哪里。
我把送给他们的话，也送给正在屏幕前努力的你：
保持乐观，悲观者正确，乐观者前行。
相信时间的力量，就不必问何时才有回报。
拥有坚持的毅力，就不必在意暂时的苟且。
保持每天的进步，就不必对未来感到迷茫。
愿你在代码的世界里披荆斩棘，也在人生的道路上步履不停。