现代 C++ 实战（20）：栈、队列与链表

第 19 篇的哈希表用数组 + 指针组织数据；再往前退一步，有三种几乎无处不在的基础结构：栈（LIFO）、队列（FIFO）、链表（动态串联节点）。实现简单，却是表达式求值、BFS、LRU 的底座。

demo：ref/cpp_demo/algorithms/stack_queue_list/（stack_demo、queue_demo、linked_list_demo）。

这是「现代 C++ 实战」系列的第 20 篇。建议先读第 19 篇：哈希表。

一、三种结构一句话

结构	规则	典型操作
栈 Stack	后进先出 LIFO	`push` / `pop` / `top`
队列 Queue	先进先出 FIFO	`enqueue` / `dequeue` / `front`
链表 Linked List	节点 + 指针串联	头插、尾插、删除、遍历

1 2	栈: push → [30][20][10] ← top 队列: front → [10][20][30] ← back 链表: head → (30) → (20) → (10) → nullptr

二、栈：数组 vs 链表

数组实现

class ArrayStack {
    std::vector<int> data_;
public:
    void push(int x) { data_.push_back(x); }
    void pop() { if (!data_.empty()) data_.pop_back(); }
    int top() const { return data_.back(); }
    bool empty() const { return data_.empty(); }
};

vector 尾部增删 O(1) 均摊，缓存友好。

链表实现

头插作 push，删头作 pop——也是 O(1)，但每个节点多一个指针，缓存局部性差。

STL

#include <stack>
std::stack<int> s;
s.push(10); s.push(20);
s.top();    // 20
s.pop();
s.size(); s.empty();

std::stack 默认底层是 deque（也可指定 vector），是容器适配器——只暴露栈接口，不支持下标遍历。

应用：括号匹配、函数调用栈、DFS 深度优先、逆序输出。

三、队列：循环数组优化

朴素数组队列：front 前移后前面空间浪费 → 循环数组：

      rear
        ↓
[ _ ][20][30][10][ _ ]
        ↑
      front
index = (index + 1) % capacity

实现	push	pop	说明
链表队列	O(1)	O(1)	维护 head/tail
循环数组	O(1)	O(1)	固定容量或扩容
`std::deque`	O(1)	O(1)	分段连续，两端快

STL

#include <queue>
std::queue<int> q;
q.push(10); q.push(20);
q.front();  // 10（队首）
q.back();   // 20（队尾，deque 底层时可用）
q.pop();

应用：BFS 广度优先、任务调度、消息缓冲、第 14 篇线程池任务队列。

四、链表：单链表与双链表

demo linked_list_demo.cpp 实现单链表：

struct Node {
    int data;
    Node* next;
    Node(int v) : data(v), next(nullptr) {}
};

void insertAtHead(int v) { /* 新节点 → head */ }
void insertAtTail(int v)  { /* 遍历到尾再挂 */ }
void deleteNode(int v)    { /* 找前驱，unlink，delete */ }

操作	单链表	双链表
头插	O(1)	O(1)
尾插	O(n)	O(1)（有 tail）
按值删除	O(n)	O(n)
随机访问	❌	❌

双链表：prev + next，可双向遍历，删除已知节点 O(1)（有指针时）。

现代 C++ 优先 std::list（双向链表）或 std::forward_list（单向）：

std::list<int> lst = {1, 2, 3};
lst.push_front(0);
lst.push_back(4);
lst.remove(2);           // 按值删
auto it = lst.begin();
++it;
lst.insert(it, 99);      // 在迭代器位置插入

注意：list 迭代器在插入/删除后不失效（除被删元素）；vector 插入可能全部失效。

五、STL 容器对比

容器	底层	特点
`stack<T>`	默认 `deque`	适配器，LIFO
`queue<T>`	默认 `deque`	适配器，FIFO
`deque<T>`	分段数组	两端 O(1)，可随机访问
`list<T>`	双向链表	中间插入 O(1)，无连续内存
`forward_list<T>`	单向链表	更省内存

需求	选型
只要栈语义	`stack`
只要队列语义	`queue` 或 `deque`
频繁中间插删	`list`
两端操作 + 下标	`deque`

六、应用场景

表达式求值（栈）

中缀 3 + 4 * 2 → 后缀 3 4 2 * +：数字入栈，运算符弹出计算。编译器、计算器内核。

BFS（队列）

图/树层序遍历：起点入队，每次出队扩展邻居并入队。最短路径（无权图）。

LRU Cache（哈希表 + 双向链表）

unordered_map 存 key → 链表迭代器；链表按访问时间排序，满则删尾。O(1) get/put（经典面经 + 工程缓存）。

七、实现时注意什么？

点	建议
RAII	demo 手写链表在析构里 `delete` 遍历；工程用 `unique_ptr<Node>` 或直接用 `list`
边界	空栈 `pop`、空队列 `front` — STL 未定义行为，先 `empty()`
所有权	裸指针链表面试常写；生产代码避免裸 `new/delete`

八、demo 运行

cd ref/cpp_demo/algorithms/stack_queue_list
./build.sh
./build/stack_demo
./build/queue_demo
./build/linked_list_demo

分别演示 std::stack、std::queue 操作与手写链表的插入/删除/查找。

九、小结

结构	核心	STL
栈	LIFO，一端进出	`std::stack`
队列	FIFO，队尾入队首出	`std::queue`
链表	节点指针，动态长	`list` / `forward_list`

现代 C++ 实战系列第 20 篇完。下一篇 树结构全家桶——BST、AVL、红黑树、B 树、堆。

系列导航

篇号	标题	状态
19	哈希表实现	✅
20	栈、队列与链表（本篇）	✅
21	树结构全家桶	下一篇

完整大纲见工作区 docs/CPP_SERIES_OUTLINE.md。