C++数据结构入门：栈与队列的工程实现与标准库选型指南

不少来问C++数据结构怎么学的初学者，我基本都是先让他们别碰那些花哨的树和图，踏踏实实把栈和队列吃透。这两个结构是数据结构里最基础、最贴近工程实际、也是面试笔试出场率最高的两块内容。用C++学栈和队列这件事，难的不是“看懂数组+指针怎么摆”，而是理解为什么限制那么多，以及什么时候该自己实现、什么时候直接用标准库。这篇文章我准备按自己带项目时的思路走一遍：先讲清楚这两个结构解决什么问题，再给出可以直接跑的C++实现代码，最后把标准库容器、常见坑、选型依据一次聊透。

1. 栈和队列到底解决了什么问题

1.1 先从最朴素的需求说起：为什么数组和链表不够用

很多人学完数组和链表后，会产生一个疑问：我要实现一个“后进先出”或“先进先出”的容器，用数组或者链表也能做啊，为什么要单独定义栈和队列？

这个问题问得其实很关键。数组能随机访问任意位置，链表能在任意位置插入删除，能力比栈和队列强得多。但能力的过剩，恰恰是问题所在。拿函数调用来说，调用链是一层一层压入、再一层一层返回的，操作系统在管理调用栈时，需要的就是“只能从一头进、只能从一头出”这种受限结构。如果这里给你一个能随便插入删除的数组，反而容易出乱子：你没办法保证每一次递归返回时，弹出的就是最近一次压入的那个状态。

栈和队列的本质，是对线性表进行“操作限制”：栈只允许在同一端插入和删除，队列只允许在一端插入、另一端删除。这种限制不是缺陷，而是一种向系统承诺的约束。就像一摞盘子，你只会从顶上拿，也只会往顶上放，这样任何人都不用关心最底下的盘子在哪儿，因为这个结构的操作规则把可能性收敛了。

1.2 栈和队列的工程价值：从函数调用到事件循环

栈在真实系统里最典型的例子，就是函数调用栈。你写过递归就应该有体会：每次调用子函数，系统会把返回地址、局部变量、实参压入调用栈，子函数执行完再从栈顶弹回来。这个机制严格执行后进先出，保证了程序能在任何嵌套深度下正确返回。

队列的典型场景是消息队列和任务调度。事件循环里，一个请求来了排到队尾，处理完一个再从队头取出下一个，先来先服务，谁也别插队。CPU的任务调度、网络请求的缓冲、键盘输入流的缓冲，本质都是队列模型。

用一个生活化的说法：栈是“走回头路”，你撤销一次操作，撤销的是最近一次；队列是“排队办事”，先到先得，公平。理解到这一层，后面学什么顺序栈、链栈、循环队列就都不会觉得抽象了。

2. C++实现栈：先手写一遍再谈标准库

2.1 顺序栈的实现思路与top指针约定

顺序栈，说穿了就是用一块连续内存存元素，再用一个整型变量记录栈顶位置。写代码前必须先把top指针的语义定清楚：top到底是指向栈顶元素，还是指向栈顶元素的下一个位置？

我建议把手写版本里的top初始化为-1，它表示“栈顶元素的下标”。这样栈空判断是top == -1，压栈是data[++top] = value，弹栈是return data[top--]，非常顺。另一种约定是top初始化为0，表示“下一个可放元素的下标”，栈空判断变成top == 0，压栈是data[top++] = value，弹栈是return data[--top]。两种都能用，但混用的话代码会非常难看。

下面是核心实现，这个版本可以当作模板记下来：

cpp复制class ArrayStack {
private:
    int* data;
    int capacity;
    int topIdx;  // 栈顶元素下标，初始为 -1
public:
    ArrayStack(int cap = 16) {
        data = new int[cap];
        capacity = cap;
        topIdx = -1;
    }
    ~ArrayStack() { delete[] data; }
    
    bool empty() const { return topIdx == -1; }
    bool full() const { return topIdx == capacity - 1; }
    
    void push(int val) {
        if (full()) {
            // 扩容，这里先给一个最简单的写法
            int newCap = capacity * 2;
            int* newData = new int[newCap];
            for (int i = 0; i <= topIdx; ++i) newData[i] = data[i];
            delete[] data;
            data = newData;
            capacity = newCap;
        }
        data[++topIdx] = val;
    }
    
    int pop() {
        if (empty()) throw std::runtime_error("stack underflow");
        return data[topIdx--];
    }
    
    int top() const {
        if (empty()) throw std::runtime_error("stack is empty");
        return data[topIdx];
    }
};

这里最关键的一点是扩容时机。很多新手容易在push里忘记判断满了就硬写data[++topIdx] = val，结果越界写到相邻内存，表现就是数据偶尔错乱、偶尔崩溃，排查起来很费劲。另外扩容这块，我这个示例用的是最直接的搬移写法，实际工程中建议用std::vector管理底层数组，或者用std::unique_ptr，把内存管理的细节交给库。

2.2 链栈实现要点：头插法就是天然的栈

链栈其实比数组栈更直观。因为单链表如果你只允许在头结点后面操作，那一头进一头出，天然就是栈的模型。你不需要尾指针，因为根本用不到尾巴；你只需要一个head指针，每次插入新结点就把head指向新结点，每次弹栈就head = head->next并释放旧头结点。

链栈的好处是几乎不会满，因为结点是从堆上动态分配的。坏处是每个结点多存一个next指针，而且频繁new/delete会有不小的开销。所以工程上做普通栈，数组版本用的是大多数。

写链栈的时候有个细节容易出错：插入新结点时，顺序必须是

cpp复制Node* newNode = new Node(val);
newNode->next = head;
head = newNode;

先让新结点的next指向原来的栈顶，再把head移到新结点上。如果反着来，先更新head再指next，那原栈顶就丢了。

实操心得：手写栈建议把数组版和链表版都写一遍，代码不用多，每个类20行左右的规模。写完之后你才会真正体会到“top指针”这个概念的不可替代性。数组版的top是个整数下标，链表版的top就是头指针，本质上它们都是在回答同一个问题：当前能操作的位置在哪。

3. C++实现队列：循环数组是避不开的坎

3.1 顺序队列的假溢出问题

队列如果也用最简单的数组实现，前几次操作会非常正常：enqueue从数组尾部追加，dequeue从头部拿走。但问题很快就会出现——出队操作如果只是把front往后移动，那前面被拿走元素的位置就永远空着，后面再想入队，tail已经到数组末尾了，明明前面有大量空闲空间，却提示满了。这就是“假溢出”。

假溢出不是内存真不够了，而是线性数组的头尾移动方式导致前半段空间无法复用。解决办法有两种：一种是把数据整体前移，出一次队搬一次家，时间复杂度O(n)，明显不行；另一种就是我接下来要重点讲的：把数组首尾相接，做成环形队列。

3.2 环形队列判空判满的两种策略

环形队列在逻辑上把数组看成一个环，front和rear都在环上移动。每入队一个元素，rear = (rear + 1) % capacity；每出队一个元素，front = (front + 1) % capacity。关键问题来了：如何区分“空”和“满”？如果只用front == rear表示空，那满的时候rear刚好转了一圈追上front，也会出现front == rear，就判不了。

常见做法是牺牲一个存储单元：让队列实际能放的元素个数是capacity - 1，判别条件变成：

• 判空：front == rear
• 判满：(rear + 1) % capacity == front

这个写法的含义是：rear永远指向下一个可放位置，但规定rear再往前走一步如果碰到front，就认为是满。牺牲一格空间，换来了清晰的判断逻辑。

下面是完整的环形队列实现，参考价值很高：

cpp复制class CircleQueue {
private:
    int* data;
    int capacity;
    int front;  // 队头下标，front指向当前队头元素
    int rear;   // 队尾下标，rear指向下一个可用位置
    int count;  // 可选：也可以额外记录元素个数，这样就不用牺牲一格
public:
    CircleQueue(int cap = 8) {
        data = new int[cap];
        capacity = cap;
        front = 0;
        rear = 0;
        count = 0;
    }
    ~CircleQueue() { delete[] data; }
    
    bool empty() const { return count == 0; }
    bool full() const { return count == capacity; }
    
    void enqueue(int val) {
        if (full()) throw std::runtime_error("queue overflow");
        data[rear] = val;
        rear = (rear + 1) % capacity;
        ++count;
    }
    
    int dequeue() {
        if (empty()) throw std::runtime_error("queue underflow");
        int val = data[front];
        front = (front + 1) % capacity;
        --count;
        return val;
    }
    
    int frontValue() const {
        if (empty()) throw std::runtime_error("queue is empty");
        return data[front];
    }
};

我这里用count字段解决了判空判满的麻烦，这是工程里最常见的做法，也比较容易理解。考研题或某些教材爱用牺牲一格空间的做法，逻辑等价，大家看得懂就行。需要注意的是，如果不用count，入队和出队时mod运算的先后顺序很容易写错，强烈建议先在纸上画一个长度为5的环，自己走一遍入队出队流程，把front、rear的移动轨迹画出来再写代码，我当年这步偷懒吃了不少亏。

4. 标准库容器：能用则用，但要明白为什么

4.1 std::stack 和 std::queue 的本质：容器适配器

手写做完之后，再看C++标准库里的std::stack和std::queue，很多设计意图就一目了然了。它们不是从零实现的容器，而是容器适配器：把某个现成底层容器（默认是std::deque）包一层皮，只暴露stack或queue该有的接口。

std::stack只给你push、pop、top、empty、size；std::queue只给你push、pop、front、back、empty、size。也就是说，你手里明明有一个拥有完整能力的deque，但适配器硬是只开几个口子给你用，这正好呼应了开头说的“操作限制”思想。

日常开发中，除非题目明确要求手写，否则直接用标准库是更合理的选择。比如一个临时需要后进先出、元素个数不确定的场景：

cpp复制#include <stack>
std::stack<int> st;
st.push(1);
st.push(2);
while (!st.empty()) {
    std::cout << st.top() << " ";
    st.pop();
}

4.2 为什么默认底层是deque而不是vector

很多人问过这个问题：std::stack默认容器是std::deque，为什么不是vector？因为stack只需要在一端操作，vector完全够用啊。

这里要分清“能用”和“适合”。vector在尾部增加元素时，如果容量不够，要做整体搬移，虽然摊还下来也是O(1)，但偶尔一次copy的代价比较大。deque的策略是分段连续：逻辑上是连续的，物理上是多段缓冲区拼起来的，尾部插入时不需要整体搬移，而是按需分配新的缓冲区段，扩容成本比vector平滑得多。stack操作集中在尾部，deque的push_back和pop_back天然就是O(1)且避免大规模拷贝。std::queue就更明显了，它需要在两端操作——队尾进、队头出，deque两端操作都很快，vector在头部插入的速度是灾难级别的。

所以标准库选deque当默认适配器，不是随手选的，是权衡过数据访问模式后的结果。做容器适配器，底层容器要求接口匹配、复杂度合适，deque是最均衡的选择。

4.3 什么时候不该用标准库适配器

标准库的stack和queue很好用，但也有力所不能及的时候，最典型的就是你需要遍历内部的全部元素。std::stack不提供迭代器，你没法从头到尾把所有元素看一遍，只能不停地top再pop，看完还得想办法恢复原栈，很别扭。

实际工作里有个经典场景：设计一个能在O(1)时间拿到最小值的栈。标准stack做不到，因为它只给你看栈顶。我自己做模拟项目时，这种需求就直接用一个std::vector当栈用，同步再维护一个std::vector作为最小栈记录，自己控制push和pop操作，自由度一下就高了很多。

另一个常见判断依据是：如果你需要从底部访问元素，或者需要访问栈中第几个元素，那说明这个数据结构已经不该用stack抽象了，直接使用vector或deque这类通用容器更匹配需求。不要让适配器的“限制”反过来变成绊脚石。

5. 实操过程里最常踩的坑，一个速查表解决

5.1 边界条件问题

手写栈和队列时，九成bug集中在边界条件上。我梳理了几个特别典型的，每个都踩过或者帮别人调试过：

• 栈顶指针的初始值没定好。top初始化成-1还是0，直接决定判空、判满、压栈、弹栈四处的写法。混用就会出现“压一个元素进去，判空还是true”这种毛病。
• 队列判空判满搞混。如果不使用count而是用牺牲一格的方案，判满的mod运算里front和rear谁加一是最容易写反的。(rear + 1) % capacity == front是满；front == rear是空。写成(rear + 1) % capacity == rear那基本没救了。
• 弹栈/出队前忘了判空。栈和队列的空操作属于未定义行为，直接访问越界内存。好一点的实现应该用异常处理，工程里宁可多写一个if也不要省。

5.2 C++特有的资源管理问题

这可能是C++写数据结构与C语言最大的区别点，也是新手最容易懵的地方。如果你在类里用new开辟了数组或结点内存，你就必须认真处理拷贝构造和赋值操作。

默认的拷贝构造是浅拷贝：一个栈对象拷贝到另一个栈对象时，两个对象里的data指针指向同一块内存。析构的时候第一个对象把这个内存释放了，第二个对象再去释放就变成了双重释放，直接崩溃。

解决思路有两种：一种是写“深拷贝”的拷贝构造和赋值运算符，把底层数据完整复制一份；另一种更省事，直接用std::vector、std::string这类自带内存管理的容器作为成员，把new和delete交给标准库来管。

避坑提醒：如果你在写数据结构练习代码，建议一开始就养成“类里出现裸指针就要想拷贝控制”的条件反射。只写析构函数而不管拷贝，等于在代码里埋了一颗不知道什么时候爆的雷。

5.3 标准库容器使用排查速查

学栈和队列这件事，我个人经验是三个阶段不能跳：先手写数组版和链表版，每个细节都弄清楚；再对照标准库的适配思想，搞清楚它帮你优化了什么、隐藏了什么；最后用几道经典题目练手，比如括号匹配、表达式求值、层次遍历这种，感受这两个结构在实际场景中怎么发挥作用的。等你把这一步走完，后续学二叉树、图、堆，分析问题的思路都会顺很多。