前言

STL 中，stack 及 queue 均以底部容器完成其所有工作，而具有这种 “修改某物接口，形成另一种风貌” 之性质者，称为 adapter（配接器），因此，STL stack 与 STL queue 往往不被归类为 container（容器），而被归类为 container adapter。
———— 《STL源码剖析》侯捷

本节将会分析 STL 中的 stack 及 queue 的实现。

stack

stack 是一种先进后出 (First In Last Out，FILO) 的数据结构。它只有一个出口。stack 允许新增元素、移除元素、取得最顶端元素。但除了最顶端外，没有任何其它方法可以存取 stack 的其它元素。换言之，stack不允许有遍历行为，因此 stack 不具有迭代器。将元素推人stack的操作称为push，将元素推出stack 的操作称为pop。

以某种既有容器作为底部结构，将其接口改变，使之符合 “先进后出” 的特性，形成一个stack，是很容易做到的。deque是双向开口的数据结构，若以deque为底部结构并封闭其头端开口，便轻而易举地形成了一个stack。因此，SGI STL 便以 deque作为缺省情况下的 stack 底层结构，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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/// @brief 模板类 stack
/// @tparam T 数据类型
/// @tparam Container 底层容器类型，默认为 tinystl::deque<T>
template <class T, class Container = tinystl::deque<T>>
class stack {

public:
    typedef Container                           container_type;
    // 使用底层容器的型别
    typedef typename Container::value_type      value_type;
    typedef typename Container::size_type       size_type;
    typedef typename Container::reference       reference;
    typedef typename Container::const_reference const_reference;

    static_assert(std::is_same<T, value_type>::value, "the value_type of Container should be same with T");

private:
    container_type c_;  // 底层容器

public:  // 构造、复制、移动、析构函数

    stack() = default;  // 默认构造函数
    // 构造一个有 n 个元素的 stack
    explicit stack(size_type n) : c_(n) {}  
    // 构造一个有 n 个元素的 stack，每个元素都是 value
    stack(size_type n, const value_type& value) : c_(n, value) {}  

    template <class InputIterator>
    stack(InputIterator first, InputIterator last) : c_(first, last) {}

    stack(std::initializer_list<value_type> ilist) : c_(ilist.begin(), ilist.end()) {}

    stack(const Container& c) : c_(c) {}
    // 见 stack.md
    stack(Container&& c) noexcept(std::is_nothrow_move_constructible<Container>::value) : c_(std::move(c)) {}
    
    stack(const stack& rhs) : c_(rhs.c_) {}
    stack(stack&& rhs) noexcept(std::is_nothrow_move_constructible<Container>::value) : c_(std::move(rhs.c_)) {}

    stack& operator=(const stack& rhs) {
        c_ = rhs.c_;
        return *this;
    }

    stack& operator=(stack&& rhs) noexcept(std::is_nothrow_move_assignable<Container>::value) {
        c_ = std::move(rhs.c_);
        return *this;
    }

    stack& operator=(std::initializer_list<value_type> ilist) {
        c_ = ilist;
        return *this;
    }

    ~stack() = default;

public:  // 元素相关操作

    reference       top()                  { return c_.back(); }
    const_reference top() const            { return c_.back(); }

    bool            empty() const noexcept { return c_.empty(); }
    size_type       size() const noexcept  { return c_.size(); }

    template<class... Args>
    void emplace(Args&&... args) { c_.emplace_back(tinystl::forward<Args>(args)...); }

    void push(const value_type& value) { c_.push_back(value); }
    void push(value_type&& value)      { c_.push_back(std::move(value)); }

    void pop() { c_.pop_back(); }

    void clear() {while (!empty()) pop();}

    void swap(stack& rhs) noexcept(noexcept(tinystl::swap(c_, rhs.c_))) { tinystl::swap(c_, rhs.c_); }

public: 
    // 为了访问 private 的 c_，声明为友元
    friend bool operator==(const stack& lhs, const stack& rhs) { return lhs.c_ == rhs.c_; }
    friend bool operator< (const stack& lhs, const stack& rhs) { return lhs.c_ <  rhs.c_; }

};

// ====================================== 重载比较操作符 ====================================== //

template <class T, class Container>
bool operator==(const stack<T, Container>& lhs, const stack<T, Container>& rhs) {
    return lhs.c_ == rhs.c_;
}

template <class T, class Container>
bool operator!=(const stack<T, Container>& lhs, const stack<T, Container>& rhs) {
    return !(lhs == rhs);
}

template <class T, class Container>
bool operator< (const stack<T, Container>& lhs, const stack<T, Container>& rhs) {
    return lhs.c_ < rhs.c_;
}

template <class T, class Container>
bool operator<=(const stack<T, Container>& lhs, const stack<T, Container>& rhs) {
    return !(rhs < lhs);
}

template <class T, class Container>
bool operator>=(const stack<T, Container>& lhs, const stack<T, Container>& rhs) {
    return !(lhs < rhs);
}

template <class T, class Container>
bool operator> (const stack<T, Container>& lhs, const stack<T, Container>& rhs) {
    return rhs < lhs;
}

// ====================================== 重载 swap ====================================== //

template <class T, class Container>
void swap(stack<T, Container>& lhs, stack<T, Container>& rhs) noexcept(noexcept(lhs.swap(rhs))) {
    lhs.swap(rhs);
}

这里需要注意的是 operator== 与 operator< 被声明为友元函数，因此可以访问 private 成员变量，关于这里为什么要使用友元的形式会放在下一篇文章中详细分析。

为什么缺省使用 deque？

这里需要思考一个问题：既然任何支持新增元素、移除元素、取得最顶端元素的序列式容器均可以作为 stack 的底层结构 ( vector、list、deque 均可以 )，为什么 STL 会缺省使用 deque？个人认为主要有以下原因：

  1. 在 STL 中，vector 的 push_back() 平均时间复杂度虽然也是常数，但在到达了容量上限时会进行 “扩容”，即复制所有元素并移动过去，这一行为是线性复杂度，开销很大，相对来说 deque 的 push_back() 操作要简单许多，不涉及移动所有元素的问题，性能更好。

  2. list 的 push_back() 操作虽然也是常数复杂度，但每一次 push_back() 都需要创建一个新的节点，即每一次 push_back() 都需要申请内存，因此相较于 deque 的开销还是较大。

所以，STL 默认的 deque 是个不错的选择，它介于 vector 和 list 之间，并且很好的综合了两者的优势。

queue

queue 是一种先进先出 ( First In First Out，FIFO ) 的数据结构。它有两个出口。queue 允许新增元素、移除元素、从最底端加入元素、取得最顶端元素。但除了最底端可以加入、最顶端可以取出外，没有任何其它方法可以存取 queue 的其它元素。换言之，queue 不允许有遍历行为，因此 queue 不具有迭代器。

与 stack 类似，queue 底层容器也缺省使用 deque 来实现，经过了上文的分析，这一做法就比较好理解了。首先，vector 弹出头部元素的开销过大 ( 线性复杂度 )，而 list 还是会有相对较大的内存开销，因此采用 deque 作为缺省容器，十分合理。

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// 模板类 queue
// 参数一代表数据类型，参数二代表底层容器类型，缺省使用 deque 作为底层容器
template <class T, class Container = tinystl::deque<T>>
class queue {

public:
    typedef Container                           container_type;
    // 使用底层容器的型别
    typedef typename Container::value_type      value_type;
    typedef typename Container::size_type       size_type;
    typedef typename Container::reference       reference;
    typedef typename Container::const_reference const_reference;

    static_assert(std::is_same<T, value_type>::value, "the value_type of Container should be same with T");

private:
    // 用底层容器的型别来定义一个底层容器对象
    container_type c_;

public:  // 构造、复制、移动、析构函数
    queue() = default;
    explicit queue(size_type n) : c_(n) {}
    queue(size_type n, const value_type& value) : c_(n, value) {}

    template <class InputIterator>
    queue(InputIterator first, InputIterator last) : c_(first, last) {}

    queue(std::initializer_list<value_type> ilist) : c_(ilist.begin(), ilist.end()) {}

    queue(Container& c) : c_(c) {}

    queue(Container&& c) noexcept(std::is_nothrow_move_constructible<Container>::value) : c_(tinystl::move(c)) {}
 
    queue(const queue& rhs) : c_(rhs.c_) {}

    queue(queue&& rhs) noexcept(std::is_nothrow_move_constructible<Container>::value) : c_(tinystl::move(rhs.c_)) {}

    queue& operator=(const queue& rhs) {
        c_ = rhs.c_;
        return *this;
    }

    queue& operator=(queue&& rhs) noexcept(std::is_nothrow_move_assignable<Container>::value) {
        c_ = tinystl::move(rhs.c_);
        return *this;
    }

    queue& operator=(std::initializer_list<value_type> ilist) {
        c_ = ilist;
        return *this;
    }

    ~queue() = default;

public:  // 元素相关操作
    reference       front()        { return c_.front(); }
    const_reference front() const  { return c_.front(); }
    reference       back()         { return c_.back(); }
    const_reference back() const   { return c_.back(); }

    bool            empty() const noexcept { return c_.empty(); }
    size_type       size()  const noexcept { return c_.size(); }

    template <class... Args>
    void emplace(Args&&... args) { c_.emplace_back(tinystl::forward<Args>(args)...); }

    void push(const value_type& value) { c_.push_back(value); }
    void push(value_type&& value)      { c_.push_back(tinystl::move(value)); }

    void pop() { c_.pop_front(); }

    void clear() { while (!empty()) pop(); }

    void swap(queue& rhs) noexcept(noexcept(tinystl::swap(c_, rhs.c_))) { tinystl::swap(c_, rhs.c_); }

public: 
    friend bool operator==(const queue& lhs, const queue& rhs) { return lhs.c_ == rhs.c_; }
    friend bool operator< (const queue& lhs, const queue& rhs) { return lhs.c_ <  rhs.c_; }
};

// ========================== 重载比较操作符 ========================== // 

template <class T, class Container>
bool operator==(const queue<T, Container>& lhs, const queue<T, Container>& rhs) {
    return lhs == rhs;
}

template <class T, class Container>
bool operator!=(const queue<T, Container>& lhs, const queue<T, Container>& rhs) {
    return !(lhs == rhs);
}

template <class T, class Container>
bool operator<(const queue<T, Container>& lhs, const queue<T, Container>& rhs) {
    return lhs < rhs;
}

template <class T, class Container>
bool operator>(const queue<T, Container>& lhs, const queue<T, Container>& rhs) {
    return rhs < lhs;
}

template <class T, class Container>
bool operator<=(const queue<T, Container>& lhs, const queue<T, Container>& rhs) {
    return !(rhs < lhs);
}

template <class T, class Container>
bool operator>=(const queue<T, Container>& lhs, const queue<T, Container>& rhs) {
    return !(lhs < rhs);
}

// 重载 tinystl 的 swap
template <class T, class Container>
void swap(queue<T, Container>& lhs, queue<T, Container>& rhs) noexcept(noexcept(lhs.swap(rhs))) {
    lhs.swap(rhs);
}