【C++】STL——stack和queue（万字详解）

🎇C++学习历程：入门

---

• 博客主页：一起去看日落吗
• 持续分享博主的C++学习历程
• 博主的能力有限，出现错误希望大家不吝赐教
• 分享给大家一句我很喜欢的话： 也许你现在做的事情，暂时看不到成果，但不要忘记，树🌿成长之前也要扎根，也要在漫长的时光🌞中沉淀养分。静下来想一想，哪有这么多的天赋异禀，那些让你羡慕的优秀的人也都曾默默地翻山越岭🐾。

---

💓 💗 💕 💞 💘 💖

---

💖1. stack的介绍和使用

💘1.1 stack的介绍

stack的文档介绍

1. stack 是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。

2. stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层，元素特定容器的尾部(即栈顶)被压入和弹出。

3. stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
   ➡ empty：判空操作
   ➡ back：获取尾部元素操作
   ➡ push_back：尾部插入元素操作
   ➡ pop_back：尾部删除元素操作

4. 标准容器 vector、deque、list 均符合这些需求，默认情况下，如果没有为 stack 指定特定的底层容器，默认情况下使用 deque。

---

💘1.2 stack的使用

• 使用演示：

#include
#include
using namespace std;

void test_stack()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
		
	while(!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;
}
int main()
{
	test_stack();
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

💘1.3 stack的题目练习

💞 最小栈

链接：最小栈

• 解题思路：

要做出这道题目，首先要理解栈结构先进后出的性质。

对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。

因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。

那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。

• 算法思想：

按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

• 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；

• 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；

• 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

代码演示：

class MinStack {
    stack<int> my_stack;
    stack<int> min_stack;
public:
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int val) {
        my_stack.push(val);
        min_stack.push(min(min_stack.top(),val));
    }
    
    void pop() {
        my_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return my_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
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

---

💞 栈的弹出压入序列

链接：栈的弹出压入序列

• 解题思路

题目要我们判断两个序列是否符合入栈出栈的次序，我们就可以用一个栈来模拟。对于入栈序列，只要栈为空，序列肯定要依次入栈。那什么时候出来呢？自然是遇到一个元素等于当前的出栈序列的元素，那我们就放弃入栈，让它先出来。

• 算法思路

step 1：准备一个辅助栈，两个下标分别访问两个序列。

step 2：辅助栈为空或者栈顶不等于出栈数组当前元素，就持续将入栈数组加入栈中。

step 3：栈顶等于出栈数组当前元素就出栈。

step 4：当入栈数组访问完，出栈数组无法依次弹出，就是不匹配的，否则两个序列都访问完就是匹配的。

代码演示：

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int n = pushV.size();
        //辅助栈
        stack<int> str;
        //遍历入栈下标
        int j = 0;
        //遍历出栈数组
        for(int i = 0;i < n;i++)
        {
            while(j < n && (str.empty() || str.top() != popV[i]))
            {
                str.push(pushV[j]);
                j++;
            }
            //栈顶等于出栈数组
            if(str.top() == popV[i])
                str.pop();
            else
                return false;
        }
        return true;
    }
};
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

---

💞 逆波兰表达式求值

链接：逆波兰表达式求值

逆波兰表达式：

• 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
  该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

---

• 解题思路

逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

如果遇到操作数，则将操作数入栈；

如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

• 代码演示

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        int n = tokens.size();
        for (int i = 0; i < n; i++) {
            string& token = tokens[i];
            if (isNumber(token)) {
                stk.push(atoi(token.c_str()));
            } else {
                long long num2 = stk.top();
                stk.pop();
                long long num1 = stk.top();
                stk.pop();
                switch (token[0]) {
                    case '+':
                        stk.push(num1 + num2);
                        break;
                    case '-':
                        stk.push(num1 - num2);
                        break;
                    case '*':
                        stk.push(num1 * num2);
                        break;
                    case '/':
                        stk.push(num1 / num2);
                        break;
                }
            }
        }
        return stk.top();
    }

    bool isNumber(string& token) {
        return !(token == "+" || token == "-" || token == "*" || token == "/");
    }
};


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

---

💞 两个栈实现队列

链接：两个栈实现队列

• 解题思路

将一个栈当作输入栈，用于压入 push\texttt{push}push 传入的数据；另一个栈当作输出栈，用于 pop\texttt{pop}pop 和 peek\texttt{peek}peek 操作。

每次 pop\texttt{pop}pop 或 peek\texttt{peek}peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

• 代码演示

class MyQueue {
private:
    stack<int> in_stack;
    stack<int> out_stack;

    void inout()
    {
        while(!in_stack.empty())
        {
            out_stack.push(in_stack.top());
            in_stack.pop();
        }
    }
public:
    MyQueue() {

    }
    
    void push(int x) {
        in_stack.push(x);
    }
    
    int pop() {
        if(out_stack.empty())
            inout();
        int n = out_stack.top();
        out_stack.pop();
        return n;
    }
    
    int peek() {
        if(out_stack.empty())
            inout();
        return out_stack.top();

    }
    
    bool empty() {
        return in_stack.empty() && out_stack.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */
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

---

💘1.4 模拟实现stack

#include 
#include 
using namespace std;

namespace byh
{
template<class T>
class stack
{
public:
    stack()
    {
        
    }
    void push(const T& x)
    {
        _c.push_back(x);
    }
    
    void pop()
    {
        _c.pop_back();
    }
    
    T& top()
    {
        return  _c.back();
    }
    
    const T& top() const
    {
        return  _c.back();
    }
    
    size_t size() const
    {
        return _c.size();
    }
    
    bool empty() const
    {
        return _c.empty();
    }
    
private:
    std::vector<T> _c;
};
void text1()
{
    stack<int> n;
    
    n.push(1);
    n.push(2);
    n.push(3);
    
    while(!n.empty())
    {
        cout << n.top() << endl;
        n.pop();
    }

    
}
}




int main()
{
   byh::text1();
}

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

---

💖2. queue的介绍和使用

💘2.1 queue的介绍

queue的文档介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端
   提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的
   成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操
   作:

• empty：检测队列是否为空
• size：返回队列中有效元素的个数
• front：返回队头元素的引用
• back：返回队尾元素的引用
• push_back：在队列尾部入队列
• pop_front：在队列头部出队列

4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标
   准容器deque。

---

💘2.2 queue的使用

• 使用演示

#include
#include
using namespace std;
void test_queue()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
		
	while(!q.empty())
	{
		//queue与stack相同的是入数据都是push,但出数据stack是top,queue是front
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
}
int main()
{
	test_queue();
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

💘2.3 queue的题目练习

💞 用队列实现栈

class MyStack {
public:
    queue<int> queue1;
    queue<int> queue2;

    MyStack() {

    }
    
    void push(int x) {
        queue2.push(x);
        while(!queue1.empty())
        {
            queue2.push(queue1.front());
            queue1.pop();
        }
        swap(queue1,queue2);
    }
    
    int pop() {
        int n = queue1.front();
        queue1.pop();
        return n;
    }
    
    int top() {
        int n = queue1.front();
        return n;
    }
    
    bool empty() {
        return queue1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */
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

---

💘2.4 queue的模拟实现

list模拟实现queue

#include

namespace byh
{
	template class<T>
	class queue
	{
	public:
		queue(){}
		//先进
		void push(const T& x)
		{
			_qu.push_back(x);
		}
		//先出
		void pop()
		{
			_qu.pop_front();
		}
		const T& front()
		{
			return _qu.front();
		}
		size_t size()
		{
			return _qu.size();
		}
		bool empty()
		{
			return _qu.empty();
		}  
	private:	
		std::list<T> _qu;
	};
}

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

---

💖3. priority_queue的介绍和使用

💘3.1 priority_queue的介绍

priority_queue文档介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元
   素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特
   定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭
   代器访问，并支持以下操作：

• empty()：检测容器是否为空
• size()：返回容器中有效元素个数
• front()：返回容器中第一个元素的引用
• push_back()：在容器尾部插入元素
• pop_back()：删除容器尾部元素

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指
   定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数
   make_heap、push_heap和pop_heap来自动完成此操作。

---

💘3.2 priority_queue的使用

优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。注意：默认情况下 priority_queue 是大堆。

• 代码演示：

#include
#include
#include //greater的头
using namespace std;

void test_priority_queue()
{
	//priority_queue pq;//默认是大堆,大的优先级高
	priority_queue<int,vector<int>, greater<int>> pq;//默认是小堆,小的优先级高。控制大小堆的是第3个参数,你要传第3个参数,必须先传第2个参数,因为它也是缺省的
	pq.push(1);
	pq.push(2);
	pq.push(3);
	pq.push(4);
	pq.push(5);
	pq.push(6);
	
	while(!pq.empty())
	{
		//取堆顶的数据
		cout << pq.top() << " ";
		//出堆顶(与最后元素交换,再删除它),向下调整
		pq.pop();
	}
	cout << endl;
}
int main()
{
	test_priority_queue();
	return 0;
}

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

---

💘3.3 在OJ中的使用

数组中的第K个最大元素

• 解题思路

建一个 k 个数的小堆，其它数依次比较，它比堆顶的数要大，那么就 pop 堆顶，再 push 这个数，最后堆顶的数据就是第 k 大的。

• 代码演示

class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
        // 将数组中的元素先放入优先级队列中
        priority_queue<int> p(nums.begin(), nums.end());
        // 将优先级队列中前k-1个元素删除掉
        for(int i= 0; i < k-1; ++i)
        {
            p.pop();
        }
        return p.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

---

💘 3.4 priority_queue的模拟实现

通过对priority_queue的底层结构就是堆，因此此处只需对对进行通用的封装即可。

• 代码演示

//
//  main.cpp
//  优先级队列的模拟实现
//
//  Created by 卜绎皓 on 2022/10/26.
//

#pragma once

#include 
using namespace std;

#include 
// priority_queue--->堆
namespace byh
{
    template<class T>
    struct less
    {
        bool operator()(const T& left, const T& right)
        {
            return left < right;
        }
    };

    template<class T>
    struct greater
    {
        bool operator()(const T& left, const T& right)
        {
            return left > right;
        }
    };

    template<class T, class Container = std::vector<T>, class Compare = less<T>>
    class priority_queue
    {
    public:
        // 创造空的优先级队列
        priority_queue() : c() {}

        template<class Iterator>
        priority_queue(Iterator first, Iterator last)
            : c(first, last)
        {
            // 将c中的元素调整成堆的结构
            int count = c.size();
            int root = ((count - 2) >> 1);
            for (; root >= 0; root--)
                AdjustDown(root);
        }

        void push(const T& data)
        {
            c.push_back(data);
            AdjustUP(c.size() - 1);
        }

        void pop()
        {
            if (empty())
                return;

            swap(c.front(), c.back());
            c.pop_back();
            AdjustDown(0);
        }

        size_t size()const
        {
            return c.size();
        }

        bool empty()const
        {
            return c.empty();
        }

        // 堆顶元素不允许修改，因为：堆顶元素修改可以会破坏堆的特性
        const T& top()const
        {
            return c.front();
        }
    private:
        // 向上调整
        void AdjustUP(int child)
        {
            int parent = ((child - 1) >> 1);
            while (child)
            {
                if (Compare()(c[parent], c[child]))
                {
                    swap(c[child], c[parent]);
                    child = parent;
                    parent = ((child - 1) >> 1);
                }
                else
                {
                    return;
                }
            }
        }

        // 向下调整
        void AdjustDown(int parent)
        {
            size_t child = parent * 2 + 1;
            while (child < c.size())
            {
                // 找以parent为根的较大的孩子
                if (child + 1 < c.size() && Compare()(c[child], c[child + 1]))
                    child += 1;

                // 检测双亲是否满足情况
                if (Compare()(c[parent], c[child]))
                {
                    swap(c[child], c[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                    return;
            }
        }
    private:
        Container c;
    };
}

void TestQueuePriority()
{
    byh::priority_queue<int> q1;
    q1.push(5);
    q1.push(1);
    q1.push(4);
    q1.push(2);
    q1.push(3);
    q1.push(6);
    cout << q1.top() << endl;

    q1.pop();
    q1.pop();
    cout << q1.top() << endl;

    vector<int> v{ 5,1,4,2,3,6 };
    byh::priority_queue<int, vector<int>, byh::greater<int>> q2(v.begin(), v.end());
    cout << q2.top() << endl;

    q2.pop();
    q2.pop();
    cout << q2.top() << endl;
}

int main()
{
    TestQueuePriority();
    return 0;
}

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

---

💖4. 容器适配器

💘4.1 什么是容器适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

---

💘4.2 STL标准库中stack和queue的底层结构

虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为 stack 和队列只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque

---

💘4.3 deque的简单介绍(了解)

💞4.3.1 deque的原理介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

那deque是如何借助其迭代器维护其假想连续的结构呢？

---

💞4.3.2 deque的缺陷

• 与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。

• 与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

• 但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

---

💘4.4 为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了其缺陷。

---