C++效率掌握之STL库：stack && queue函数全解

本篇是 STL 库专题之 stack 和 queue，本质就是栈和队列，关于该数据结构在初阶数据结构专栏里有详细的解释分析，本篇文章主要针对 stack 和 queue 的使用及拓展进行练习和介绍，建议熟悉好相关的数据结构知识再进行本篇学习

传送门：【初阶数据结构】先来后到的秩序：栈和队列

1.stack

stack 的主要特征可总结为：

1. stack 是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作
2. stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出
3. stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

• empty：判空操作
• back：获取尾部元素操作
• push_back：尾部插入元素操作
• pop_back：尾部删除元素操作

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

🔥值得注意的是： 什么是容器适配器？简单来讲，就是它把一些普通的容器包装起来，给它们增加一些新的功能或者改变它们原来的一些行为方式，让这些容器能更好地适应某些特定的需求，让 vector，list 这样的容器也能以这种数据结构进行

1.1 stack函数

C++ 的 STL 库将我们在 C 语言阶段需要手撕出来的数据结构进行封装，以容器适配器的形式供我们直接使用

💻代码测试示例：

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> st;
	st.push(10);
	st.push(20);
	st.push(30);
	st.push(40);

	cout << "empty:" << st.empty() << endl;
	cout << "size:" << st.size() << endl;
	cout << "top:" << st.top() << endl;

	st.push(50);
	cout << "pop、push:";
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
}

⌨️代码输出示例：

1.2 stack常见OJ

1.2.1 最小栈

✏️题目描述：

✏️示例：

传送门： 最小栈

题解:

既然题目的意思是要求能取到各种时刻下栈的最小值，那么一个栈来实现显然是不可取的，因为栈的遍历只能通过 top 和 pop 的循环来实现，这就破坏了原本的栈

所以我们设置两个栈，一个栈 _st 用于存储入栈的值，一个栈 _minst 用于存储栈各种时刻的最小值，每次存储的时候和此时 _minst 栈顶比较一下（栈顶即最小值），不断把每个时刻的最小值入栈 _minst

再优化的版本就是把重复的最小值去掉，直到遇到更小的值才选择入栈 _minst

出栈的操作也是同理，遇到相同的值 _minst 就出栈

💻代码实现：

class MinStack 
{
public:
    MinStack() 
    {}
    
    void push(int val) 
    {
        _st.push(val);
        if(_minst.empty() || val <= _minst.top())
        {
            _minst.push(val);
        }
    }
    
    void pop() 
    {
        if(_st.top() == _minst.top())
        {
            _minst.pop();
        }
        _st.pop();
    }
    
    int top() 
    {    
        return _st.top();
    }
    
    int getMin() 
    {
        return _minst.top();
    }

private:
    stack<int> _minst;
    stack<int> _st;
};

1.2.2 用栈实现队列

✏️题目描述：

✏️示例：

传送门： 用栈实现队列

题解:

依然是用 inst 和 outst 两个栈，调转头尾在栈顶的位置实现队列的功能

💻代码实现：

class MyQueue 
{
public:
    MyQueue() 
    {}
    
    void push(int x) 
    {
        inst.push(x);
    }
    
    int pop() 
    {
        if(outst.empty())
        {
            while(!inst.empty())
            {
                outst.push(inst.top());
                inst.pop();
            }
        }
        int val = outst.top();
        outst.pop();
        return val;
    }
    
    int peek() 
    {
        if(outst.empty())
        {
            while(!inst.empty())
            {
                outst.push(inst.top());
                inst.pop();
            }
        }
        return outst.top();
    }
    
    bool empty() 
    {
        return outst.empty() && inst.empty();
    }

private:
    stack<int> outst;
    stack<int> inst;
};

1.3 stack的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的容器，因此使用 vector等容器完全可以模拟实现 stack

#pragma once
#include <vector>
#include <list>
using namespace std;

namespace bit
{
	template<class T, class Container = vector<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

		T& top()
		{
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

2.queue

queue 的主要特征可总结为：

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

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

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

2.1 queue函数

C++ 的 STL 库将我们在 C 语言阶段需要手撕出来的数据结构进行封装，以容器适配器的形式供我们直接使用

💻代码测试示例：

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	queue<int> q;
	q.push(10);
	q.push(20);
	q.push(30);
	q.push(40);

	cout << "empty:" << q.empty() << endl;
	cout << "size:" << q.size() << endl;
	cout << "front:" << q.front() << endl;
	cout << "back:" << q.back() << endl;

	q.pop();
	cout << "pop:";
	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
}

⌨️代码输出示例：

2.2 queue常见OJ

2.2.1 用队列实现栈

✏️题目描述：

✏️示例：

传送门： 用队列实现栈

题解:

使用一个队列时，为了满足栈的特性，即最后入栈的元素最先出栈，同样需要满足队列前端的元素是最后入栈的元素

入栈操作时，首先获得入栈前的元素个数 n，然后将元素入队到队列，再将队列中的前 n 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底

💻代码实现：

class MyStack {
public:
    MyStack()
    {}

    void push(int x) 
    {
        int n = q.size();
        q.push(x);
        for (int i = 0; i < n; i++)
        {
            q.push(q.front());
            q.pop();
        }
    }

    int pop() 
    {
        int top = q.front();
        q.pop();
        return top;
    }

    int top() 
    {
        return q.front();
    }

    bool empty() 
    {
        return q.empty();
    }

private:
    queue<int> q;
};

2.3 queue的模拟实现

queue 的底层不好以 vector 的形式实现，因为 vector 没有提供头删的操作，虽然可以使用 erase+begin 的操作实现，但还是太麻烦了，所以用 list 来实现

#pragma once

#pragma once
#include <vector>
#include <list>
using namespace std;

namespace bit
{
	template<class T, class Container = list<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

		T& front()
		{
			return _con.front();
		}

		T& back()
		{
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！