【C++】栈和队列法使用及实现原理

朱雀 2024-04-22 22:18 62阅读 0赞

![da4e9416b5b842699072fb7d6437a668.gif][]

> 本篇文章会对C++中的容器stack和queue用法进行详解，也包含对优先队列（priority\_queue）的讲解。同时会模拟实现stack、queue和priority\_queue底层。希望本篇文章会对你有所帮助！

> **目录**
> 
> 一、stack 栈
> 
> 1、1 什么是适配器
> 
> 1、2 stack 语法讲解
> 
> 1、3 stack 底层实现
> 
> 1、4 deque 双端队列简单介绍
> 
> 1、5 为什么选择deque作为stack和queue的底层默认容器
> 
> 二、queue or priority\_queue 队列和优先队列
> 
> 2、1 queue 队列
> 
> 2、1、1 queue 语法讲解
> 
> 2、1、2 queue 底层实现
> 
> 2、2 priority\_queue 优先队列
> 
> 2、2、1 priority\_queue 底层实现原理
> 
> 2、2、2 仿函数
> 
> 2、2、3 priority\_queue 底层代码实现
> 
> --------------------
> 
> **?♂️ 作者：@Ggggggtm ?♂️**
> 
> **? 专栏：C++ ?**
> 
> **? 标题：stack、queue和priority\_queue****讲解?**
> 
>  **❣️ 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ❣️**
> 
> ![996b7d85185442f68a545a48930698b5.png][]

## 一、stack 栈 ##

> `stack`（堆栈）是一种后进先出（Last-In-First-Out，LIFO）的数据结构。数据项只能从栈的顶部插入和删除。在C++中，stack、queue和priority\_queue是一种**容器适配器**，可以使用`<stack>`头文件来包含`stack`的定义。

### 1、1 什么是适配器 ###

> 我们在上述中说到stack是一种**容器适配器**。容器我们都知道，那什么是适配器呢？
> 
>  **适配器是一种设计模式**(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结)，**该种模式是将一个类的接口转换成客户希望的另外一个接口**。通俗来说，在C++中适配器就是一种编程模式， **用于将一个类的接口适配成另一个类的接口**，以满足不同的需求。
> 
> 我们所需要讲解stack、queue和priority\_queue底层就是有用适配器来实现的。当然，只对语法有所需求的，不了解适配器也并无太大影响。
> 
> 只有概念太过抽象。我们不妨先来学一下语法使用，再了解底层实现原理后，就可很好的理解适配器是什么了。

### 1、2 stack 语法讲解 ###

> 我们早在学C语言时就学过栈。栈是一种先进后出的数据结构。在C++中，stack是一种**容器。**所以我们在使用时**应引入相应头文件（\#include<stack>），**同时需要展开**命名空间（namespace std）**。

> 栈的操作很简单，一共就有如下几种：
> 
> 1.  top：获取尾部元素操作；
> 2.  size：获取栈中的元素个数操作；
> 3.  pop：删除栈顶元素操作；
> 4.  push：栈顶插入元素操作；
> 5.  empty：判空操作;
> 
> 我们接下来看一下实例，结合理解一下，代码如下：
> 
>     #include<iostream>
>     #include<stack>
>     
>     using namespace std;
>     
>     int main()
>     {
>     	//stack<data_type> stack_name;
>     	stack<int> st;  //声明一个stack对象，对象名为 st，存储数据类型为 int 
>     
>     	//往栈中依次插入了1 2 3 三个元素
>     	st.push(1);
>     	st.push(2);
>     	st.push(3);
>     	cout << st.size() << endl; //打印栈中的元素个数
>     
>     	cout << st.top() << endl;  //打印栈顶元素，栈顶元素为 3
>     
>     	st.pop();
>     	cout << st.top() << endl;  //删除元素后，再次打印打印栈顶元素，栈顶元素为 2
>     
>     	cout << st.empty() << endl; //判断栈是否为空，空返回 1 ，不为空返回 0。
>     
>     	cout << st.size() << endl;
>     }
> 
> 我们再看输出结果如下：
> 
> ![a1b2ad25feb94727a4d1f97460fba2b8.png][]

> 栈的使用十分简单，我们直接看底层实现原理。

### 1、3 stack 底层实现 ###

> 为了能够便利的存储各种类型，C++在底层实现中采用了类模板。通过声明或者传参，进而实例化出不同的类。
> 
> stack的底层并不是自己定义了数组进行维护，而是引用了其他容器。引用的那个容器呢？我们先看一下底层模板定义：
> 
> ![eb580ae683d84d92997171ebd26dedf7.png][]
> 
> 模板的第一个参数即为我们所要存储的类型，第二个参数为我们所想使用的容器。我们也看到，其中有缺省参数。当你不传参时，**默认为deque容器**。
> 
> stack被称为容器适配器是因为**它通过适配底层的容器实现了一种特定的接口和行为**。而所谓的**适配器**，我们可以**通俗理解就是可以根据实际需求选择适合的底层容器来实现Stack，并且可以在不影响代码的其他部分的情况下进行更改**。
> 
> 我们所选择的容器需要支持以下操作：
> 
>  *  empty：判空操作；
>  *  pop\_back：尾部删除元素操作；
>  *  push\_back：尾部插入元素操作；
>  *  back：获取尾部元素操作；

> 底层代码的实现原理就比较简单了，代码如下：
> 
>     template<class T, class Container=deque<T> >
>           class stack
>           {
>           public:
>               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();    
>               }
>           
>               bool empty() const
>               {
>                   return _con.empty();
>               }
>           
>               int size() const
>               {
>                   return _con.size();
>               }
>           private:
>               Container _con;
>           };

### 1、4 deque 双端队列简单介绍 ###

>  **deque(双端队列)：是一种双开口的"连续"空间的数据结构**，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
> 
> ![2e8ffe5b630b49d98a0fe98bef4840fb.png][] **deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。**
> 
>  **双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落 在了deque的迭代器身上，**因此deque的迭代器设计就比较复杂其底层结构如下图所示：
> 
> ![ac9e0ee67842438f9b9bd49213228656.png][]

> 当然，deque有其优势，也有其劣势。**与vector比较**，deque的优势是：头部插入和删除时，**不需要搬移元素，效率特别高**，而且在**扩容时，也不 需要搬移大量的元素**，因此其效率是必vector高的。**与list比较**，其底层是连续空间，**空间利用率比较高**，不需要存储额外字段。 
> 
>  但是，**deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下**，而序列式场景中，可能需要经常遍历，因此**在实际中，需要线性结构时，大多数情况下优先考虑vector和list**，deque的应用并不多，而**目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。**

### 1、5 为什么**选择****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的优点，而完美的避开了其缺陷。

## 二、queue or priority\_queue 队列和优先队列 ##

### 2、1 queue 队列 ###

#### 2、1、1 queue 语法讲解 ####

> queue队列是一种先进先出的数据结构。在C++中，也是一个容器适配器。其底层定义如下：
> 
> ![4d58c1e4574b4821968c6a124daecd75.png][]

> 其主要的操作有如下几种：
> 
> 1.  front：获取对列头部（第一个元素）操作；
> 2.  back：获取队列尾部（最后一个元素）操作；
> 3.  size：获取队列中的元素个数操作；
> 4.  pop：删除队列头部元素操作；
> 5.  push：队列尾部插入元素操作；
> 6.  empty：判空操作;
> 
> 我们来看实际例子，代码如下：
> 
> ![dd8b7975b31b48fdb77a5733fcda85bb.png][]

#### 2、1、2 queue 底层实现 ####

> queue底层实现与stack大同小异。当我们学完stack的底层实现后，我们就很容易构思出queue的底层实现了。我们直接看代码：
> 
>     template<class T, class Container=deque<T>>                                
>           class queue                                                                                            
>           {                                                                                   
>           public:                                                                                                   
>               void push(const T& x)                                                           
>               {                                                                      
>                   _con.push_back(x);                                                                           
>               }                                                                               
>                                                                                                                      
>               void pop()                                                                      
>               {                                                                      
>                   _con.pop_back();                                                                           
>               }                                                                               
>                                                                                                                     
>               T& front()                                                                      
>               {                                                                                  
>                   return _con.fornt();                                                                                                                           
>               }                                                                            
>                                                                                       
>               T& back()                                                           
>               {                                                                   
>                   return _con.back(); 
>               }
>       
>               const T& front() const
>               {                                                                                                                                                  
>                   return _con.fornt();
>               }
>               
>               const T& back() const
>               {
>                   return _con.back();
>               }
>       
>               bool empty() const
>               {
>                   return _con.empty();
>               }
>           
>               size_t size() const
>               {
>                   return _con.size();
>               }
>           private:
>               Container _con;
>           };
> 
> 我们接下俩重点看一下优先队列priority\_queue的底层实现。

### 2、2 priority\_queue 优先队列 ###

> 优先队列（priority\_queue）也是队列的一种，priority\_queue的接口是和queue的接口是相同的。所以两者的使用语法也是相同的。我们直接看优先队列（priority——queue）的底层实现原理。

#### 2、2、1 priority\_queue 底层实现原理 ####

> 优先队列中顾名思义：优先级高的元素在队列中的位置靠前，优先级低的元素在队列中的位置靠后。优先级就是指的元素大小。
> 
>  **优先队列被实现为容器适配器**，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
> 
> 1.  empty()：检测容器是否为空；
> 2.  size()：返回容器中有效元素个数；
> 3.  front()：返回容器中第一个元素的引用；
> 4.  push\_back()：在容器尾部插入元素；
> 5.  pop\_back()：删除容器尾部元素
> 
>  标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority\_queue类实例化指定容器类，则使用vector。

> **优先队列的底层是由堆来维护的**。也就是我们所操作的元素都是在堆的基础上进行操作的。提到堆，我们就知道堆分为大根堆和小根堆。**优先队列的底层默认是由大根堆来维护的**。为了更好的去控制优先队列底层维护的是大根堆还是小根堆，这里就引入了仿函数。我们先来了解一下什么是仿函数，再来看一下底层的代码实现。

#### 2、2、2 仿函数 ####

> 仿函数就是模仿函数，但它根本上就不是一个函数。我们先看下面一个例子，代码如下：
> 
>     template<class T>
>     struct Less
>     {
>     	T l, r;
>     	bool operator()(const T& left, const T& right)
>     	{
>     		return left < right;
>     	}
>     };
>     int main()
>     {
>     	test_priority_queue();
>     
>     	//仿函数
>     	Less<int> com;
>     
>         // com.operator() (1,2)
>     	cout << com(1, 2) << endl;
>     	cout << com(2, 1) << endl;
>     	return 0;
>     }
> 
> 我们看到上面的代码定义了一个结构体 Less，我们同时定义了一个com（Compare）对象。com（1，2）直接就对 1 和 2 进行了比较大小。是不是很像函数调用。但实际上是定义了一个结构体（或者类），该结构体（或者类）中**重载了操作符 （)**。从而达到了函数的效果。这就是所谓了仿函数。

#### 2、2、3 priority\_queue 底层代码实现 ####

> 我们通过把仿函数当作模板参数，就可以很好的控制底层是大根堆还是小根堆了。代码如下：
> 
>     template<class T, class Container = vector<T>, class Compare = less<T>>
>     	class priority_queue
>     	{
>     	public:
>     		priority_queue()
>     		{}
>     
>     		template<class InputIterator>
>     		priority_queue(InputIterator first, InputIterator last)
>     		{
>     			while (first != last)
>     			{
>     				_con.push_back(*first);
>     				first++;
>     			}
>     
>     			//建堆  向下调整算法O(n)
>     			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
>     			{
>     				adjust_down(i);
>     			}
>     		}
>     
>     		void adjust_up(size_t child)
>     		{
>     			Compare com;
>     			size_t parent = (child - 1) / 2;
>     			while (child > 0)
>     			{
>     				if (com(_con[parent] , _con[child]))
>     				{
>     					std::swap(_con[parent], _con[child]);
>     					child = parent;
>     					parent = (child - 1) / 2;
>     				}
>     				else
>     				{
>     					break;
>     				}
>     			}
>     		}
>     		void push(const T& x)
>     		{
>     			_con.push_back(x);
>     			adjust_up(_con.size() - 1);
>     		}
>     
>     		void adjust_down(size_t parent)
>     		{
>     			Compare com;
>     			size_t child = parent * 2 + 1;
>     			while (child<_con.size())
>     			{
>     				if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
>     					child++;
>     
>     				if (com(_con[parent] , _con[child]))
>     				{
>     					std::swap(_con[parent], _con[child]);
>     					parent = child;
>     					child = parent * 2 + 1;
>     				}
>     				else
>     				{
>     					break;
>     				}
>     			}
>     		}
>     		void pop()
>     		{
>     			std::swap(_con[0], _con[_con.size() - 1]);
>     			_con.pop_back();
>     			adjust_down(0);
>     		}
>     
>     		const T& top()const
>     		{
>     			return _con[0];
>     		}
>     
>     		bool empty()  const
>     		{
>     			return _con.empty();
>     		}
>     
>     		size_t size() const
>     		{
>     			return _con.size();
>     		}
>     	private:
>     		Container _con;
>     	};
> 
> 我们看到上述代码，删除元素就是删除的堆顶元素。每次删除都需要先与最后一个元素交换，再通过所引用的容器进行尾删，再向下调整算法进行维护队列。

> 当然，上述代码只是实现了一部分主要接口。priority\_queue（优先队列）的声明方式如下：
> 
>     // 底层是大根堆
>     priority_queue<int> heap1;
>     // 底层是小根堆
>     priority_queue<int, vector<int>, greater<int>> heap2；

> 到这里，希望你对优先队列有一个更好的认识。同时，对stack、queue和priority\_queue的用法有一个很好的掌握。感谢阅读ovo~

[da4e9416b5b842699072fb7d6437a668.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/788b9990ad6344828709cf9733465b5b.gif
[996b7d85185442f68a545a48930698b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/53bba30771464907b4b62b024b735267.png
[a1b2ad25feb94727a4d1f97460fba2b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/a95244572d9b4b2094f33af6179a1bbe.png
[eb580ae683d84d92997171ebd26dedf7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/f70e5faa18314868bfd2605945b721d5.png
[2e8ffe5b630b49d98a0fe98bef4840fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/347649da99204115807b976f15e9b871.png
[ac9e0ee67842438f9b9bd49213228656.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/1fbf8aa9bf7d4b8e9b90f96327c5d7ac.png
[4d58c1e4574b4821968c6a124daecd75.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/0c283a8ee961493298621242eb87f913.png
[dd8b7975b31b48fdb77a5733fcda85bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/70dd0da17d3c493d8042bca56d8dd867.png