【c++篇】：栈、队列、优先队列：容器世界里的秩序魔法 - stack，queue与priority_queue探秘
✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：c++篇–CSDN博客
文章目录
- 前言
- 一.容器stack
- 1.介绍
- 2.成员函数
- 3.模拟实现
- 4.注意事项
- 二.容器queue
- 1.介绍
- 2.成员函数
- 3.模拟实现
- 4.注意事项
- 三.容器priority_queue
- 1.介绍
- 2.使用
- 3.模拟实现
- 基本框架
- 成员函数
- 4.测试
前言
在编程的世界里，数据结构是构建高效程序的基石。而在C++等编程语言中，容器则是对数据结构的一种方便的实现与封装。其中，stack（栈）、queue（队列）和priority_queue（优先队列）是非常重要且基本的容器类型。Stack以其独特的后进先出（LIFO）的操作模式，为解决一些特定顺序相关的问题提供了简洁的方法，例如函数调用栈。Queue遵循先进先出（FIFO）的原则，如同现实生活中的排队场景，在任务调度等场景有着广泛的应用。而priority_queue则允许按照用户定义的优先级来取出元素，给具有不同重要性元素的操作提供了高效的实现。本博客旨在深入探讨这三种容器，包括它们的特性、操作方式以及各自适用的应用场景等，希望能够帮助读者更好地理解和运用这些在编程中至关重要的工具。
一.容器stack
1.介绍
在之前的数据结构学习中我们知道Stack（栈）是一种特殊的线性数据结构，其特点在于元素的插入和删除操作都只能在容器的一端进行，这一端通常被称为栈顶。Stack遵循后进先出LIFO, Last In First Out的原则，即最后插入的元素会是第一个被删除的元素。
在C++中，Stack是作为容器适配器实现的，这意味着它封装了某个具体的容器类（如vector、deque或list）作为其底层存储结构，并提供了一套特定的成员函数来访问这些元素。如果没有为Stack指定特定的底层容器，默认情况下，Stack会使用deque作为其底层容器，因为deque提供了在两端高效插入和删除元素的能力，非常适合Stack的需求。
2.成员函数
Stack提供的主要成员函数包括：
-
push(x)函数
- 将元素x压入栈顶。
-
pop()：
- 弹出栈顶元素，即删除栈顶元素。注意：这个函数没有返回值，只是简单地移除了栈顶元素。
-
top()：
- 返回栈顶元素的引用，但不删除它。这允许我们访问栈顶元素的值，注意：如果不小心修改了引用的值，将会改变栈顶元素的值。
-
empty()：
- 检查栈是否为空。如果栈为空，则返回true；否则返回false。
-
size()：
- 返回栈中元素的个数。
3.模拟实现
以下是一个容器Stack的简单模拟实现：
- 代码实现：
#include<iostream>
#include<vector>
#include<list>
using namespace std;
namespace Mystack{
template<class T,class container=vector<T>>
class stack{
public:
//构造函数
stack()
{}
void push(const T& x){
//入栈调用尾插函数
_con.push_back(x);
}
void pop(){
//出栈调用尾删函数
_con.pop_back();
}
T& top(){
//取栈顶元素返回最后一个元素即可
return _con[_con.size()-1];
}
const T& top()const {
return _con[_con.size()-1];
}
size_t size()const {
//获取大小调用size()函数
return _con.size();
}
bool empty()const {
//判断为空调用empty()函数
return _con.empty();
}
private:
container _con;
};
}
-
实现原理：
- 模版参数
T表示存储的数据类型，container表示适配器的类型，默认为vector<T> - 成员变量
_con是适配器的实例化对象 - 构造函数为空即可，成员变量会调用对应容器的构造函数完成初始化
top()函数分为普通对象使用的类型和const对象使用的类型，返回是引用返回
- 模版参数
-
测试用例：
void test1(){ Mystack::stack<string> st; st.push("ab"); st.push("cd"); st.push("ef"); st.push("gh"); while(!st.empty()){ cout<<st.top()<<" "; st.pop(); } cout<<endl; }
4.注意事项
- Stack不支持随机访问，即不能通过下标访问元素。
- Stack内的元素是无法直接遍历的，但可以通过while循环和pop()/top()的组合来遍历（但这种方法会改变Stack的状态，因为每读取一个元素就需要弹出这个元素）。
- 在使用pop()函数之前，需要确保栈不为空，否则会导致未定义行为。
二.容器queue
1.介绍
Queue（队列）是一种先进先出FIFO, First In First Out的数据结构，它有两个主要操作：入队（enqueue）和出队（dequeue）。入队操作将元素添加到队列的尾部，而出队操作则移除队列头部的元素。Queue在多种场景中都有广泛的应用，如任务调度、消息传递、广度优先搜索等。
在C++中，Queue是作为容器适配器（Container Adapter）实现的，它依赖于某个具体的容器类（如deque、list）作为其底层存储结构。默认情况下，C++标准库中的Queue使用deque作为其底层容器，但也可以通过模板参数指定其他支持双端操作的容器，如list。
2.成员函数
Queue提供的主要成员函数包括：
-
push(x)：
- 将元素x添加到队列的尾部。
-
pop()：
- 移除队列头部的元素。注意，这个函数没有返回值，只是简单地移除了队列头部的元素。
-
front()：
- 返回队列头部元素的引用，但不删除它。这允许我们访问队列头部元素的值。
-
back()：
- 返回队列尾部元素的引用，但不删除它。这允许我们访问队列尾部元素的值。
-
empty()：
- 检查队列是否为空。如果队列为空，则返回true；否则返回false。
-
size()：
- 返回队列中元素的个数。
3.模拟实现
以下是一个容器Queue的简单模拟实现(注意，c++标准库中使用的是deque做默认适配器，这里为了方便直接使用list做默认适配器：
- 代码实现：
#include<iostream>
#include<vector>
#include<list>
using namespace std;
namespace Myqueue{
template<class T,class container=list<T>>
class queue{
public:
//构造函数
queue()
{}
//入队调用尾插函数
void push(const T& x){
_con.push_back(x);
}
//出队调用头删函数
void pop(){
_con.pop_front();
}
//取队头元素返回迭代器begin()位置的元素
T& front(){
return *(_con.begin());
}
const T& front()const {
return *(_con.begin());
}
//取队尾元素返回迭代器end()位置的元素
T& back(){
return *(_con.end()--);
}
const T& back()const {
return *(_con.end()--);
}
//获取队长调用size()函数
size_t size()const {
return _con.size();
}
//判断为空调用empty()函数
bool empty()const {
return _con.empty();
}
private:
container _con;
};
}
-
实现原理：
- 模版参数
T表示存储的数据类型，container表示适配器的类型，默认为list<T> - 成员变量
_con是适配器的实例化对象 - 构造函数为空即可，成员变量会调用对应容器的构造函数完成初始化
back()和front函数分为普通对象使用的类型和const对象使用的类型，返回是引用返回
- 模版参数
-
测试用例：
void test2(){
Myqueue::queue<string> q;
q.push("ab");
q.push("cd");
q.push("ef");
q.push("gh");
while(!q.empty()){
cout<<q.front()<<" ";
q.pop();
}
cout<<endl;
}
4.注意事项
- Queue不支持随机访问，即不能通过下标访问元素。
- 在使用
pop()函数之前，需要确保队列不为空，否则会导致未定义行为。同样地，在使用front()或back()函数之前，也需要确保队列不为空。 - Queue的底层容器默认是deque，但也可以通过模板参数指定为其他支持双端操作的容器，如list。然而，由于vector只支持在尾部进行高效的插入和删除操作，因此它不能作为Queue的底层容器。
通过本文的介绍，相信你已经对C++中的Queue容器有了基本的了解，并掌握了其使用方法。希望这些信息能对你有所帮助！
三.容器priority_queue
容器priority_queue（优先级队列）是C++标准库中的一个容器适配器，它根据严格的弱排序标准为元素提供排序，使得队列的第一个元素总是当前元素中优先级最高的（默认是大堆，即最大元素位于堆顶）。
1.介绍
-
基本概念：
- 优先队列类似于堆，可以随时插入元素，并且只能检索最大堆元素（即队首元素）。
- 优先队列被实现为容器适配器，将特定的容器类封装作为其底层容器。
-
底层容器：
- 底层容器可以是任何标准容器类模板，如
vector和deque，这些容器应该可以通过随机访问迭代器访问。 - 默认情况下，如果没有为特定的
priority_queue类实例化指定容器类，则使用vector作为底层容器。
- 底层容器可以是任何标准容器类模板，如
-
比较函数：
- 优先队列使用比较函数来确定元素的优先级。默认情况下，使用
std::less作为比较函数，创建最大堆。 - 若要使用最小堆，可以指定
std::greater作为比较函数。
- 优先队列使用比较函数来确定元素的优先级。默认情况下，使用
2.使用
-
包含头文件：
在使用priority_queue之前，需要包含<queue>头文件。 -
定义优先队列：
priority_queue<int> pq; // 默认最大堆 priority_queue<int, vector<int>, greater<int>> pq_min; // 最小堆 -
成员函数：
push(x)：在优先队列中插入元素x。pop()：删除优先队列中最大（或最小）元素。top()：返回优先队列中最大（或最小）元素。empty()：检测优先队列是否为空。size()：返回优先队列中有效元素的个数。
3.模拟实现
基本框架
-
代码实现：
#include<iostream> #include<vector> #include<algorithm> using namespace std; namespace Mypriority_queue{ //仿函数/函数对象 //这个类可以像函数一样使用 //用来控制建大堆 template<class T> class less{ public: bool operator()(const T& x,const T& y){ return x<y; } }; //用来控制建小堆 template<class T> class greater{ public: bool operator()(const T& x,const T& y){ return x>y; } }; //类模版 template<class T,class container=vector<T>,class comapre=less<T>> class priority_queue{ private: //向上调整建堆 //向下调整建堆 public: //....其他成员函数 private: //成员变量 container _con; }; } -
实现原理：
- 定义两个类，这两个可以像函数一样使用，也叫做仿函数，用来控制建大堆还是建小堆
priority_queue类中，模版参数T表示存储的数据类型，模版参数container表示适配器，默认适配器为vector<int>，模版参数comapre表示用来控制建堆
成员函数
-
向下调整建堆代码实现：
void AdjustDown(size_t parents){ comapre com; //向下调整，由父节点找子节点，父节点乘2再加1 size_t child=parents*2+1; if(child+1<_con.size()&&com(_con[child],_con[child+1])){ child++; } while(child<_con.size()){ if(com(_con[parents],_con[child])){ swap(_con[parents],_con[child]); parents=child; child=parents*2+1; } else{ break; } } } -
实现原理：
- 由传过来的父节点找子节点，子节点是父节点的下标乘以2再加1
- 创建com对象，这个对象可以像使用函数一样用来比较大小
-
向下调整建堆代码实现：
void AdjustUp(size_t child){ comapre com; //向上调整，由子节点找父节点，子节点先-1再除2 size_t parents=(child-1)/2; while(child>0){ if(com(_con[parents],_con[child])){ swap(_con[parents],_con[child]); child=parents; parents=(child-1)/2; } else{ break; } } } -
实现原理：
- 由传过来的子节点找父节点，父节点下标是子节点下标先减1再除以2
- 创建com对象，这个对象可以像使用函数一样用来比较大小
-
构造函数代码实现：
template<class InputIterator> priority_queue(InputIterator first,InputIterator last){ while(first!=last){ _con.push_back(*first); first++; } //向下调整建堆 //注意，for循环中，i最好不要用size_t,如果出现i小于0时，会死循环 for(int i=(_con.size()-1-1)/2;i>=0;i--){ AdjustDown(i); } } -
实现原理：
- 构造函数是模版函数，将区间中的数据依次插入到优先队列中
- 插入完数据后循环调用向下调整建堆
-
其他成员函数代码实现：
void pop(){ swap(_con[0],_con[_con.size()k-1]); _con.pop_back(); AdjustDown(0); } void push(const T& x){ _con.push_back(x); AdjustUp(_con.size()-1); } T& top(){ return _con[0]; } const T& top()const { return _con[0]; } size_t size()const { return _con.size(); } bool empty()const { return _con.empty(); } -
实现原理：
pop()函数先交换第一个和最后一个元素，在删除最后一个元素相当于删除堆顶的元素，再调用向下调整push()函数将需要插入的数据插入到最后位置，再调用向上调整top()函数相当于获取堆顶也就是第一个元素- 获取大小调用对应的
size()函数 - 判断为空调用对应的empty()函数
4.测试
-
测试代码：
void test1(){ vector<int> v={3,2,6,1,8,7,0}; Mypriority_queue::priority_queue<int> q(v.begin(),v.end()); q.push(4); q.push(5); while(!q.empty()){ cout<<q.top()<<" "; q.pop(); } cout<<endl; } int main(){ test1(); return 0; } -
测试结果：
以上就是关于容器stack,queue,priority_queue的基本使用和模拟实现的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
