当前位置：首页 > article >正文

C++栈与队列：数据结构的“单行道”与“流水线

article 2025/2/22 12:46:06

C++栈与队列：数据结构的“单行道”与“流水线”

开篇小故事：火车站的两条轨道

想象一个火车站有两条特殊轨道：

轨道A（栈）：火车只能从同一端进出，最后进入的车厢必须先离开。
轨道B（队列）：火车从一端进入，从另一端离开，先进入的车厢先离开。

这两条轨道代表了两种基础数据结构：栈（Stack） 和 队列（Queue）。它们看似简单，却是构建复杂算法的基石。今天，我们将探索它们在C++中的实现、差异与应用场景。

一、栈与队列的核心特性对比

特性	栈（Stack）	队列（Queue）
数据规则	后进先出（LIFO）	先进先出（FIFO）
插入位置	栈顶（`push`）	队尾（`push`）
删除位置	栈顶（`pop`）	队首（`pop`）
访问权限	仅能访问栈顶元素（`top`）	可访问队首（`front`）和队尾（`back`）
典型应用	函数调用栈、括号匹配、撤销操作	任务调度、BFS广度优先搜索、消息队列

二、C++中的栈与队列实现

1. 栈（`std::stack`）

底层容器：默认基于deque，也可使用vector或list。

核心操作：

#include <stack>
stack<int> s;
s.push(10);       // 入栈
s.pop();          // 出栈（不返回元素）
int top = s.top();// 访问栈顶
bool isEmpty = s.empty();

2. 队列（`std::queue`）

底层容器：默认基于deque，也可使用list（不可用vector，因不支持pop_front）。

核心操作：

#include <queue>
queue<int> q;
q.push(20);       // 入队
q.pop();          // 出队（不返回元素）
int front = q.front(); // 访问队首
int back = q.back();   // 访问队尾

三、栈与队列的经典应用场景

1. 栈的应用：括号匹配

bool isBalanced(string expr) {
    stack<char> s;
    for (char c : expr) {
        if (c == '(' || c == '[') s.push(c);
        else if (c == ')') {
            if (s.empty() || s.top() != '(') return false;
            s.pop();
        } else if (c == ']') {
            if (s.empty() || s.top() != '[') return false;
            s.pop();
        }
    }
    return s.empty();
}
// 示例：isBalanced("([()])") → true

2. 队列的应用：广度优先搜索（BFS）

void bfs(Node* root) {
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* current = q.front();
        q.pop();
        // 处理当前节点
        for (auto child : current->children) {
            q.push(child);
        }
    }
}

3. 栈与队列的联合应用：用队列实现栈

class MyStack {
    queue<int> q;
public:
    void push(int x) {
        q.push(x);
        // 将前n-1个元素移到队尾
        for (int i = 0; i < q.size() - 1; i++) {
            q.push(q.front());
            q.pop();
        }
    }
    int pop() {
        int val = q.front();
        q.pop();
        return val;
    }
    int top() { return q.front(); }
    bool empty() { return q.empty(); }
};

四、栈与队列的底层实现原理

1. 栈的底层实现

数组实现（顺序栈）：

class ArrayStack {
    int* data;
    int capacity;
    int topIndex;
public:
    void push(int val) {
        if (topIndex == capacity - 1) resize();
        data[++topIndex] = val;
    }
    // ...其他操作
};

链表实现（链式栈）：

class ListNode {
    int val;
    ListNode* next;
};
class LinkedStack {
    ListNode* topNode;
public:
    void push(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->next = topNode;
        topNode = newNode;
    }
    // ...其他操作
};

2. 队列的底层实现

循环数组实现：解决数组实现的“假溢出”问题。

class CircularQueue {
    int* data;
    int front, rear, capacity;
public:
    void enqueue(int val) {
        if ((rear + 1) % capacity == front) resize();
        data[rear] = val;
        rear = (rear + 1) % capacity;
    }
    // ...其他操作
};

链表实现：

class LinkedQueue {
    ListNode* front;
    ListNode* rear;
public:
    void enqueue(int val) {
        ListNode* newNode = new ListNode(val);
        if (rear) rear->next = newNode;
        else front = newNode;
        rear = newNode;
    }
    // ...其他操作
};