栈与队列：原理详解与 C++ 实现-菜鸟笔记

栈（Stack）和队列（Queue）是计算机科学中最基础、也最常用的两种数据结构。无论是浏览器的”后退”功能、编译器的括号匹配，还是操作系统的任务调度，背后都少不了它们的身影。本文将带你从概念出发，一步步用 C++ 手动实现这两种数据结构，并结合 STL 标准库的使用方法，帮助你真正掌握它们。

一、栈（Stack）

什么是栈？

栈是一种 后进先出（LIFO，Last In First Out） 的线性数据结构。你可以把它想象成一摞盘子——最后放上去的盘子，一定是最先被取走的。

        ┌──────┐
  TOP → │  40  │  ← 最后入栈，最先出栈
        ├──────┤
        │  30  │
        ├──────┤
        │  20  │
        ├──────┤
BOTTOM  │  10  │  ← 最先入栈，最后出栈
        └──────┘

栈只允许在 栈顶（Top） 进行操作：

push：压栈，将元素放入栈顶
pop：弹栈，移除栈顶元素
top / peek：查看栈顶元素但不移除
empty：判断栈是否为空
size：返回栈中元素个数

栈的典型应用

函数调用栈：程序运行时，每次调用函数都会将栈帧压入调用栈，函数返回时弹出
括号匹配：编译器检查 {[()]} 是否合法
表达式求值：逆波兰表达式（后缀表达式）的计算
撤销/重做（Undo/Redo）：文本编辑器的历史记录

C++ 手动实现栈（基于数组）

#include <iostream>
#include <stdexcept>

template <typename T>
class Stack {

private:
    T* data;        // 存储数据的数组
    int topIndex;   // 栈顶索引
    int capacity;   // 容量

public:
    // 构造函数
    Stack(int cap = 100) : capacity(cap), topIndex(-1) {

        data = new T[capacity];
    }

    // 析构函数，释放内存
    ~Stack() {

        delete[] data;
    }

    // 扩容（容量翻倍）
    void resize() {

        capacity *= 2;
        T* newData = new T[capacity];
        for (int i = 0; i <= topIndex; i++) {

            newData[i] = std::move(data[i]); // 移动语义，避免深拷贝
        }
        delete[] data;
        data = newData;
    }

    // 压栈（满时自动扩容）
    void push(const T& val) {

        if (topIndex + 1 >= capacity) {

            resize();
        }
        data[++topIndex] = val;
    }

    // 弹栈
    void pop() {

        if (empty()) {

            throw std::underflow_error("Stack is empty!");
        }
        topIndex--;
    }

    // 查看栈顶元素
    T& top() {

        if (empty()) {

            throw std::underflow_error("Stack is empty!");
        }
        return data[topIndex];
    }

    // 判断是否为空
    bool empty() const {

        return topIndex == -1;
    }

    // 返回元素个数
    int size() const {

        return topIndex + 1;
    }
};

int main() {

    Stack<int> st;

    st.push(10);
    st.push(20);
    st.push(30);

    std::cout << "栈顶元素: " << st.top() << std::endl; // 30
    st.pop();
    std::cout << "弹出后栈顶: " << st.top() << std::endl; // 20
    std::cout << "栈的大小: " << st.size() << std::endl;  // 2

    return 0;
}

C++ 手动实现栈（基于链表）

基于链表实现的栈不需要预先指定容量，更加灵活：

#include <iostream>
#include <stdexcept>

template <typename T>
class LinkedStack {

private:
    struct Node {

        T val;
        Node* next;
        Node(T v, Node* n = nullptr) : val(v), next(n) {
  }
    };

    Node* topNode;
    int cnt;

public:
    LinkedStack() : topNode(nullptr), cnt(0) {
  }

    ~LinkedStack() {

        while (!empty()) pop();
    }

    void push(const T& val) {

        topNode = new Node(val, topNode);
        cnt++;
    }

    void pop() {

        if (empty()) throw std::underflow_error("Stack is empty!");
        Node* tmp = topNode;
        topNode = topNode->next;
        delete tmp;
        cnt--;
    }

    T& top() {

        if (empty()) throw std::underflow_error("Stack is empty!");
        return topNode->val;
    }

    bool empty() const {
   return topNode == nullptr; }
    int size() const {
   return cnt; }
};

使用 STL 的 std::stack

C++ 标准库已经内置了栈，直接使用即可：

#include <iostream>
#include <stack>

int main() {

    std::stack<int> st;

    st.push(1);
    st.push(2);
    st.push(3);

    while (!st.empty()) {

        std::cout << st.top() << " "; // 3 2 1
        st.pop();
    }
    return 0;
}

二、队列（Queue）

什么是队列？

队列是一种 先进先出（FIFO，First In First Out） 的线性数据结构。就像超市排队结账——先排队的人先结账。

  入队 →  [ 10 | 20 | 30 | 40 ]  → 出队
  (rear/尾)                      (front/头)

队列的基本操作：

enqueue / push：入队，在队尾添加元素
dequeue / pop：出队，移除队头元素
front：查看队头元素
back：查看队尾元素
empty：判断队列是否为空
size：返回队列元素个数

队列的典型应用

任务调度：操作系统按顺序处理进程请求
广度优先搜索（BFS）：图/树的层序遍历
消息队列：服务器处理请求的缓冲
打印机任务队列：按提交顺序打印文件

C++ 手动实现队列（基于循环数组）

普通数组实现队列存在”假溢出”问题（出队后头部空间浪费），循环队列能解决这个问题：

#include <iostream>
#include <stdexcept>

template <typename T>
class CircularQueue {

private:
    T* data;
    int head, tail;   // 头尾指针
    int cnt;
    int capacity;

public:
    CircularQueue(int cap = 100) : capacity(cap), head(0), tail(0), cnt(0) {

        data = new T[capacity];
    }

    ~CircularQueue() {

        delete[] data;
    }

    // 扩容（容量翻倍，同时将数据展平到新数组头部）
    void resize() {

        int newCapacity = capacity * 2;
        T* newData = new T[newCapacity];
        // 按逻辑顺序（从 head 开始）拷贝，避免循环绕圈问题
        for (int i = 0; i < cnt; i++) {

            newData[i] = std::move(data[(head + i) % capacity]); // 移动语义，避免深拷贝
        }
        delete[] data;
        data = newData;
        head = 0;
        tail = cnt;
        capacity = newCapacity;
    }

    // 入队（满时自动扩容）
    void push(const T& val) {

        if (cnt == capacity) {

            resize();
        }
        data[tail] = val;
        tail = (tail + 1) % capacity; // 循环推进
        cnt++;
    }

    // 出队
    void pop() {

        if (empty()) {

            throw std::underflow_error("Queue is empty!");
        }
        head = (head + 1) % capacity; // 循环推进
        cnt--;
    }

    // 查看队头
    T& front() {

        if (empty()) throw std::underflow_error("Queue is empty!");
        return data[head];
    }

    // 查看队尾
    T& back() {

        if (empty()) throw std::underflow_error("Queue is empty!");
        return data[(tail - 1 + capacity) % capacity];
    }

    bool empty() const {
   return cnt == 0; }
    int size() const {
   return cnt; }
};

int main() {

    CircularQueue<int> q;

    q.push(10);
    q.push(20);
    q.push(30);

    std::cout << "队头: " << q.front() << std::endl; // 10
    std::cout << "队尾: " << q.back() << std::endl;  // 30

    q.pop();
    std::cout << "出队后队头: " << q.front() << std::endl; // 20

    return 0;
}

C++ 手动实现队列（基于链表）

#include <iostream>
#include <stdexcept>

template <typename T>
class LinkedQueue {

private:
    struct Node {

        T val;
        Node* next;
        Node(T v) : val(v), next(nullptr) {
  }
    };

    Node* headNode;
    Node* tailNode;
    int cnt;

public:
    LinkedQueue() : headNode(nullptr), tailNode(nullptr), cnt(0) {
  }

    ~LinkedQueue() {

        while (!empty()) pop();
    }

    void push(const T& val) {

        Node* node = new Node(val);
        if (tailNode) tailNode->next = node;
        tailNode = node;
        if (!headNode) headNode = node;
        cnt++;
    }

    void pop() {

        if (empty()) throw std::underflow_error("Queue is empty!");
        Node* tmp = headNode;
        headNode = headNode->next;
        if (!headNode) tailNode = nullptr;
        delete tmp;
        cnt--;
    }

    T& front() {

        if (empty()) throw std::underflow_error("Queue is empty!");
        return headNode->val;
    }

    T& back() {

        if (empty()) throw std::underflow_error("Queue is empty!");
        return tailNode->val;
    }

    bool empty() const {
   return cnt == 0; }
    int size() const {
   return cnt; }
};

使用 STL 的 std::queue

#include <iostream>
#include <queue>

int main() {

    std::queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);

    while (!q.empty()) {

        std::cout << q.front() << " "; // 1 2 3
        q.pop();
    }
    return 0;
}

扩展：双端队列（deque）与优先队列（priority_queue）

C++ STL 还提供了两种特殊队列：

std::deque（双端队列）：两端都可以进行插入和删除操作。

#include <deque>
std::deque<int> dq;
dq.push_front(1); // 从头部插入
dq.push_back(2);  // 从尾部插入
dq.pop_front();   // 从头部删除
dq.pop_back();    // 从尾部删除

std::priority_queue（优先队列）：每次出队的是优先级最高（默认最大）的元素，底层基于堆实现。

#include <queue>
std::priority_queue<int> pq; // 默认大根堆
pq.push(3);
pq.push(1);
pq.push(4);
std::cout << pq.top(); // 输出 4（最大值）

三、栈与队列的对比

特性	栈（Stack）	队列（Queue）
操作原则	后进先出（LIFO）	先进先出（FIFO）
操作端	仅栈顶	队头出，队尾入
典型应用	递归、括号匹配、撤销	BFS、任务调度、消息队列
STL 容器	`std::stack`	`std::queue`

总结

栈和队列虽然结构简单，但它们是理解更复杂数据结构（如树、图）和算法（DFS、BFS）的重要基础。建议在熟悉概念之后，动手用 C++ 从零实现一遍，再结合 STL 的用法，这样才能真正做到融会贯通。

栈与队列：原理详解与 C++ 实现