栈和队列

ZaynPei Lv6
  2025-09-29 15:00 2025-09-29 15:00 Created   2025-11-13 22:33:52 2025-11-13 22:33:52 Updated      3.2k Words  13 Mins

“栈和队列是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的”

这句话描述的是一种经典的设计模式————适配器模式 (Adapter Pattern)。在 C++ 标准库中，std::stack 和 std::queue 正是这种模式的绝佳范例，它们并不是底层容器, 而被称为“容器适配器 (Container Adapters)”。

适配器模式 (Adapter Pattern)

适配器模式是一种结构型设计模式，它允许将一个类的接口转换成客户端所期望的另一个接口。通过这种方式，原本由于接口不兼容而无法一起工作的类可以协同工作。

回到标题, std::stack 和 std::queue 类本身并不真正存储数据。它们内部包含了一个底层容器的对象（比如一个 std::deque 对象），并将所有的数据操作委托（Delegate）给这个内部对象来完成。

  • 当你对一个 std::stack 执行 push() 操作时，std::stack 内部实际上调用的是其底层容器的 push_back() 方法。
  • 当你执行 pop() 操作时，它内部调用的是底层容器的 pop_back() 方法。
  • 当你执行 top() 操作时，它内部调用的是底层容器的 back() 方法来获取最后一个元素的引用。

因此, stack 类的实现就像一个“中间人”或“代理”: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 概念伪代码
template<class T, class Container>
class stack {
protected:
    Container c; // 内部包含一个底层容器对象 c, 可以是 std::vector, std::deque 等

public:
    void push(const T& val) {
        c.push_back(val); // 将 push 操作委托给底层容器的 push_back
    }
    void pop() {
        c.pop_back(); // 将 pop 操作委托给底层容器的 pop_back
    }
    T& top() {
        return c.back(); // 将 top 操作委托给底层容器的 back
    }
    // ... 其他接口如 empty(), size() 也都委托给 c
};

当然, 底层容器（如 std::vector）的功能非常强大，它提供了在任意位置插入 (insert())、删除 (erase())、随机访问 (operator[]) 等多种操作。但是，一个“栈”的逻辑是严格的后进先出 (Last-In, First-Out, LIFO)。你不应该能在栈的中间插入或删除元素。

因此，std::stack 适配器屏蔽了底层容器的大部分接口，只暴露出符合栈逻辑的几个关键接口(限制和简化接口): - push(): 在栈顶添加元素。 - pop(): 从栈顶移除元素。 - top(): 查看栈顶元素。 - empty(): 判断栈是否为空。 - size(): 获取栈中元素的数量。

通过这种方式，std::stack 强制保证了其 LIFO 的行为特性，使得代码更安全、逻辑更清晰。你无法意外地对一个栈执行不符合其数据结构逻辑的操作。std::queue（先进先出, First-In, First-Out, FIFO）也是同理。

与此同时, 底层容器是可插拔的. 这体现了设计的灵活性和复用性。C++ 通过模板 (Templates) 机制实现了这一点。std::stack 和 std::queue 的定义如下： 

1
2
3
4
5
6
7
8
9
template<
    class T,
    class Container = std::deque<T>
> class stack;

template<
    class T,
    class Container = std::deque<T>
> class queue;
可以看出, T是存储元素的类型; Container是选择的底层容器类型。它有一个默认值 std::deque, 我们可以显式指定为 std::vector 或 std::list。 
1
2
3
4
5
6
7
8
9
10
11
12
#include <stack>
#include <vector>
#include <list>
#include <deque> // 默认使用它

std::stack<int> s1; // 底层是 std::deque<int>

// 显式指定 std::vector<int> 作为底层容器
std::stack<int, std::vector<int>> s2;

// 显式指定 std::list<int> 作为底层容器
std::stack<int, std::list<int>> s3;

不是任何容器都可以作为 stack 的底层容器。它必须满足一定的接口要求，比如必须提供 back(), push_back(), pop_back() 这几个函数。

还要注意, stack和queue并不支持迭代器 (Iterators), 你无法像遍历 vector 或 deque 那样遍历 stack 或 queue。因为它们的设计初衷就是提供一种受限的访问方式，以符合栈和队列的逻辑。

栈 (Stack)

栈是一种严格遵循“后进先出”（Last-In, First-Out）原则的数据结构。

头文件: 要使用 std::stack，你需要包含以下头文件: 

1
#include <stack>

定义和初始化: std::stack 是一个模板类，你需要指定存储的元素类型。你也可以选择性地指定底层容器。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <stack>
#include <vector>
#include <list>
#include<string>

// 1. 使用默认的底层容器 std::deque
std::stack<int> s1;

// 2. 显式指定 std::vector 作为底层容器
std::stack<std::string, std::vector<std::string>> s2;

// 3. 显式指定 std::list 作为底层容器
std::stack<double, std::list<double>> s3;

核心成员函数: std::stack 的接口非常简洁，主要包含以下几个核心操作：

  • push(const T& value): 将元素压入栈顶。
  • pop(): 移除栈顶元素。注意：这个函数没有返回值，它只负责移除。
  • top(): 返回对栈顶元素的引用。你可以通过它读取或修改栈顶元素。
    • 如果栈为空，调用 top() 会导致未定义行为 (Undefined Behavior)。
  • empty(): 检查栈是否为空。如果为空，返回 true；否则返回 false。
  • size(): 返回栈中元素的数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <stack>

int main() {
    // 创建一个存储 int 类型的栈，底层使用默认的 std::deque
    std::stack<int> my_stack;

    // --- 压入元素 ---
    std::cout << "Pushing 10, 20, 30 onto the stack..." << std::endl;
    my_stack.push(10); // 栈: [10]
    my_stack.push(20); // 栈: [10, 20]
    my_stack.push(30); // 栈: [10, 20, 30] <- 30 是栈顶

    // --- 访问和检查 ---
    std::cout << "Stack size is: " << my_stack.size() << std::endl; // 输出: 3
    if (!my_stack.empty()) {
        std::cout << "Top element is: " << my_stack.top() << std::endl; // 输出: 30
    }

    // --- 弹出元素 ---
    std::cout << "\nPopping elements from the stack:" << std::endl;
    while (!my_stack.empty()) {
        // 步骤1：访问栈顶元素
        int top_element = my_stack.top();
        std::cout << "Popping: " << top_element << std::endl;
        
        // 步骤2：移除栈顶元素
        my_stack.pop();
    }
    // 循环结束后，栈为空

    // --- 检查栈是否为空 ---
    if (my_stack.empty()) {
        std::cout << "\nThe stack is now empty." << std::endl;
    }

    return 0;
}

队列 (Queue)

std::queue 是 C++ 标准模板库（STL）中的一个容器适配器（Container Adapter）。它提供了一种先进先出(尾进头出)（First-In, First-Out, FIFO）的数据结构。默认情况下，std::queue 使用 std::deque（双端队列）作为其底层容器。

使用前需要包含头文件: #include <queue>

std::queue 的接口非常简洁，主要包含以下几个核心操作：

  • push(const T& value): 在队列的尾部添加一个元素。这被称为“入队”（enqueue）。
  • pop(): 移除队列头部的元素。这被称为“出队”（dequeue）。
    • 此函数不返回任何值 (void)。如果想获取头部元素的值，必须在调用 pop() 之前先调用 front()。
  • front(): 返回对队列头部的第一个元素的引用。你可以通过它读取或修改头部元素，但不会将其从队列中移除。
  • back(): 返回对队列尾部的最后一个元素的引用。
  • empty(): 检查队列是否为空。如果队列中没有任何元素，返回 true；否则返回 false。
  • size(): 返回队列中元素的数量。

注意: Queue没有迭代器 (Iterators), 你无法像遍历 vector 或 deque 那样遍历 queue。如果需要遍历, 可以考虑使用 deque 代替.

双端队列 (Deque)

双端队列（Deque，全称 Double-Ended Queue）是一种允许在两端进行插入和删除操作的线性数据结构。与传统的队列（Queue）和栈（Stack）不同，双端队列既支持先进先出（FIFO）的操作，也支持后进先出（LIFO）的操作。

使用前需要包含头文件: #include <deque>

其常用函数包括： - push_back(const T& value): 在队列的尾部添加一个元素。 - push_front(const T& value): 在队列的头部添加一个元素。 - pop_back(): 移除队列尾部的元素。 - pop_front(): 移除队列头部的元素。 - front(): 返回对队列头部元素的引用。 - back(): 返回对队列尾部元素的引用。 - empty(): 检查队列是否为空。 - size(): 返回队列中元素的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <deque>
int main() {
    std::deque<int> my_deque;

    // 在尾部添加元素
    my_deque.push_back(10); // 队列: [10]
    my_deque.push_back(20); // 队列: [10, 20]

    // 在头部添加元素
    my_deque.push_front(5); // 队列: [5, 10, 20]

    // 访问头部和尾部元素
    std::cout << "Front element: " << my_deque.front() << std::endl; // 输出: 5
    std::cout << "Back element: " << my_deque.back() << std::endl;   // 输出: 20

    // 移除头部元素
    my_deque.pop_front(); // 队列: [10, 20]

    // 移除尾部元素
    my_deque.pop_back();  // 队列: [10]

    // 检查队列是否为空
    if (!my_deque.empty()) {
        std::cout << "Deque size: " << my_deque.size() << std::endl; // 输出: 1
    }

    return 0;
}

其在头部或尾部插入/删除元素的时间复杂度都是 O(1)

底层实现

deque 的底层实现通常被描述为“一个指向指针的指针”或“分块数组”。它巧妙地结合了数组和链表的优点。

其结构主要由两部分组成：

中控器 (Map / Controller) 这是一个核心的指针数组（或类似的结构，比如 T** map_）。

这个“中控器”本身通常是一块连续内存（就像 vector 一样），它存储了指向各个数据块的指针。

它不直接存储元素，而是扮演一个“目录”或“索引”的角色。

数据块 (Chunks / Blocks) 这些是多个、小型的、固定大小的连续内存块。

元素就存储在这些数据块中。

每个数据块的内存是连续的，但数据块与数据块之间在内存中是不连续的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
        [ 中控器 (Map) ]
       (一块连续的指针数组)
+-------+-------+-------+-------+
| Ptr 0 | Ptr 1 | Ptr 2 | Ptr 3 |
+---+---+---+---+---+---+---+---+
    |       |       |       |
    |       |       |       +-> [ 数据块 3 (Block) ]
    |       |       |           +---+---+---+---+
    |       |       |           | E | E | E | E |  (E = 元素)
    |       |       |           +---+---+---+---+
    |       |       |
    |       |       +---------> [ 数据块 2 (Block) ]
    |       |                   +---+---+---+---+
    |       |                   | E | E | E | E |
    |       |                   +---+---+---+---+
    |       |
    |       +-----------------> [ 数据块 1 (Block) ]
    |                           +---+---+---+---+
    |                           | E | E | E | E |
    |                           +---+---+---+---+
    |
    +-------------------------> [ 数据块 0 (Block) ]
                                +---+---+---+---+
                                | E | E | E | E |
                                +---+---+---+---+

其主要优势在于头部和尾部插入/删除操作的高效性 (O(1))，因为只需要调整中控器和数据块的指针，而不需要像 vector 那样移动大量元素。

不过其劣势在于缓存局部性较差，因为数据块在内存中是不连续的，这可能导致更多的缓存未命中 (Cache Misses)。

同时其随机访问元素需要两次间接寻址（先通过中控器找到数据块，再在数据块中找到具体元素），实际访问速度可能比 vector 略慢。它的迭代器实现也相对复杂，因为需要处理跨数据块的情况。

单调队列

单调队列是一种特殊的数据结构，它在保持队列基本功能的同时，还维护了队列中元素的单调性（递增或递减）。单调队列常用于解决一些需要在滑动窗口内快速获取最大值或最小值的问题。

例如 Leetcode 239 题“滑动窗口最大值”就是单调队列的经典应用场景。

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
private:
    class Monotonicqueue{
    public:
        deque<int> que;
        void pop(int value){
            if(!que.empty()&& value==que.front()){
                que.pop_front();
            }
        }

        void push(int value){
            while(!que.empty()&&value>que.back()){
                que.pop_back();
            }
            que.push_back(value);
        }
        int front(){
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        Monotonicqueue que;
        vector<int> result;
        for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
            que.push(nums[i]);
        }
        result.push_back(que.front()); // result 记录前k的元素的最大值
        for (int i = k; i < nums.size(); i++) {
            que.pop(nums[i - k]); // 滑动窗口移除最前面元素
            que.push(nums[i]); // 滑动窗口前加入最后面的元素
            result.push_back(que.front()); // 记录对应的最大值
        }
        return result;
    }
};

这是个单调递减队列（从队头到队尾，front → back）。这意味着队列的头部是最大的元素，尾部是最小的元素

  • pop(int value): 如果队列头部的元素等于 value，则将其移除。这是为了在滑动窗口移动时，移除过期的元素。
    • 之所以要和 value 比较，是因为只有当要移除的元素正好是队列头部时，才需要将其移除; 否则，说明该元素已经被之前的 push 操作移除掉了。
  • push(int value): 将新元素 value 插入队列。插入前，会移除所有小于 value 的元素，以保持队列的单调递减性质。
    • 队列中存在的所有小于 value 的元素都不可能成为当前或未来窗口的最大值，因此可以安全地移除它们。
  • front(): 返回队列头部的最大元素。
On this page
栈和队列
  1. 适配器模式 (Adapter Pattern)
  2. 栈 (Stack)
  3. 队列 (Queue)
    1. 双端队列 (Deque)
      1. 底层实现
    2. 单调队列