STL-stack栈和queue队列

stack栈和queue队列

在STL中 stack 和 queue 设计为容器适配器，容器适配器是使用特定容器类的封装对象作为其基础容器的类，提供一组特定的成员函数来访问其元素。

在我的STL系列中之前的容器 vector、list、deque 都是从底层类型一步步封装而来的，但是 stack 和 queue 没有这样，而是直接使用现有的容器并加以封装去实现功能。

1
2
template <class T, class Container = deque<T> > class stack;
template <class T, class Container = deque<T> > class queue;

这是 stack 和 queue 的类模板，可以看到它们都有一个类模板参数且缺省值都为 deque<T>，在 stack 和 queue 容器适配器中默认使用 deque 容器进行封装。为什么是封装的 deque 不是 vector 或者 list 我们得先了解 stack 和 queue 的结构和功能才能理解。

stack 栈

stack 栈是一种容器适配器，专门设计用于 LIFO 上下文（后进先出）中运行，其中元素仅从容器的一端插入和提取。这其实非常好理解，stack 的结构就像是一个木桶，最先放进去的东西往往最后才拿出来。

stack 中的元素从特定容器的 “back” 端 push / pop（压入/弹出），其中 “back” 端被称为栈的顶部。

stack 的底层容器可以是任何标准容器类模板或者其他专门设计的容器类，但是它们必须支持以下操作：

  • empty 判断是否为空
  • size 获取大小
  • back 返回尾部元素
  • push_back 尾插
  • pop_back 尾删

标准容器中 list、vector 和 deque 都可以作为 stack 的底层容器，但是如果没有指定模板容器，则默认使用 deque 作为底层容器。

stack 实现

stack 的实现非常地简单，直接使用底层容器的接口完成所有工作，相比 vector、list、deque 来说简单很多，这都得益于 stack 的容器适配器设计。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 模板参数：T表示栈中元素的类型，Container表示底层容器类型
template<class T, class Container = deque<T>>
class stack
{
public:
    // 迭代器
    typedef typename Container::iterator iterator;
    typedef typename Container::const_iterator const_iterator;
    // 反向迭代器
    typedef typename Container::reverse_iterator reverse_iterator;
    typedef typename Container::const_reverse_iterator const_reverse_iterator;

    // 构造函数
    stack()
    {
    }
    // 拷贝构造函数
    stack(const stack<T, Container>& st)
    {
        _con = st._con;
    }
    // 赋值运算符重载
    stack<T, Container>& operator=(stack<T, Container> st)
    {
        swap(st);
        return *this;
    }
    // 析构函数
    ~stack()
    {
    }

    // 入栈
    void push(const T& x)
    {
        _con.push_back(x);
    }
    // 出栈
    void pop()
    {
        _con.pop_back();
    }
    // 获取栈顶元素
    T& top()
    {
        return _con.back();
    }
    // 获取栈顶元素（常量版本）
    const T& top() const
    {
        return _con.back();
    }
    // 获取栈中元素个数
    size_t size() const
    {
        return _con.size();
    }
    // 判断栈是否为空
    bool empty() const
    {
        return _con.empty();
    }
    // 交换
    void swap(stack<T, Container>& st)
    {
        _con.swap(st._con);
    }
private:
    Container _con;
};

queue 队列

queue 队列也是一种容器适配器，专门设计用于 FIFO 上下文（先进先出）中运行，其中元素插入到容器的一端并从另一端提取。queue 的结构就像是一个水管，数据不断地被推入，并从另一侧弹出。

queue 中地元素从特定容器的 “back” 推入（push）并从其 “front” 弹出（pop）。

同样的 queue 的底层容器可以是任何标准容器类模板或者其他专门设计的容器类，但是它们必须支持以下操作：

  • empty 判断是否为空
  • size 获取大小
  • front 返回头部元素
  • back 返回尾部元素
  • push_back 尾插
  • pop_front 头删

标准容器中 list 和 deque 都可以作为 stack 的底层容器，但是如果没有指定模板容器，则默认使用 deque 作为底层容器。和 stack 不同的是 queue 并不支持 vector 作为底层容器，因为 vector 的头插头删效率太低了。

queue 实现

因为 queue 也是采用容器适配器设计，它的实现也很简单，直接使用底层容器的接口完成所有工作。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// 模板参数：T表示栈中元素的类型，Container表示底层容器类型
template<class T, class Container = deque<T>>
class queue
{
public:
    // 迭代器
    typedef typename Container::iterator iterator;
    typedef typename Container::const_iterator const_iterator;
    // 反向迭代器
    typedef typename Container::reverse_iterator reverse_iterator;
    typedef typename Container::const_reverse_iterator const_reverse_iterator;

    // 构造函数
    queue()
    {
    }
    // 拷贝构造函数
    queue(const queue<T, Container>& q)
    {
        _con = q._con;
    }
    // 赋值运算符重载
    queue<T, Container>& operator=(queue<T, Container> q)
    {
        swap(q);
        return *this;
    }
    // 析构函数
    ~queue()
    {
    }

    // 入队
    void push(const T& x)
    {
        _con.push_back(x);
    }
    // 出队
    void pop()
    {
        _con.pop_front();
    }
    // 获取队头元素
    T& front()
    {
        return _con.front();
    }
    // 获取队尾元素
    T& back()
    {
        return _con.back();
    }
    // 获取队头元素（常量版本）
    const T& front() const
    {
        return _con.front();
    }
    // 获取队尾元素（常量版本）
    const T& back() const
    {
        return _con.back();
    }
    // 获取队中元素个数
    size_t size() const
    {
        return _con.size();
    }
    // 判断队列是否为空
    bool empty() const
    {
        return _con.empty();
    }
    // 交换
    void swap(queue<T, Container>& q)
    {
        _con.swap(q._con);
    }
private:
    Container _con;
};

总结

stack 和 queue 都是 STL 中的容器适配器，它们通过封装其他容器类来实现特定的数据结构功能，而不是从底层类型一步步封装而来。它们的默认底层容器都是 deque，即如果没有指定模板参数中的底层容器类型，则默认使用 deque。

stack 的特点

stack 是一种后进先出（LIFO）的数据结构，元素只能从容器的一端（称为栈顶）进行插入和提取操作，类似于一个木桶，后放入的元素先取出。

queue 的特点

queue 是一种先进先出（FIFO）的数据结构，元素从容器的一端（称为队尾）插入，并从另一端（称为队头）提取，类似于一个水管，数据从一端推入，从另一端弹出。

为什么默认使用 deque 作为底层容器

  • stack 的原因：deque 提供了高效的尾部插入和删除操作（push_back 和 pop_back），这与 stack 的操作需求完全匹配。同时，deque 还支持其他一些操作，如 empty、size 和 back，能够满足 stack 的功能实现。
  • queue 的原因：deque 既能高效地在尾部插入元素（push_back），也能高效地在头部删除元素（pop_front），这与 queue 的操作需求一致。而 vector 的头插头删效率较低，不适合作为 queue 的底层容器。