🌈 个人主页：白子寰
🔥 分类专栏：重生之我在学Linux，C++打怪之路，python从入门到精通，数据结构，C语言，C语言题集👈 希望得到您的订阅和支持~
💡 坚持创作博文(平均质量分82+)，分享更多关于深度学习、C/C++，python领域的优质内容！（希望得到您的关注~）
目录
C++为什么要学习stack、queue和优先级队列
stack类
stack类的介绍
stack的基本操作
stack的模拟实现
queue类
queue类的介绍
queue的基本操作
queue的模拟实现
优先级队列
优先级队列的介绍
仿函数
什么是仿函数
为什么要有仿函数
优先级队列的使用
成员函数
排序准则
优先级队列的模拟实现
关于容器适配器
C++为什么要学习stack、queue和优先级队列
学习C++中的栈（stack）、队列（queue）和优先级队列（priority queue）对开发者来说非常重要，因为它们是常用的数据结构，在解决各种编程问题时提供了高效的方法。
以下是它们的核心作用和特点：
1. 栈（Stack）：
特点：后进先出（LIFO），即最后入栈的元素最先出栈。
应用：适用于函数调用、表达式求值、撤销操作等场景。例如，程序在执行递归调用时会用栈来存储函数状态。2. 队列（Queue）：
特点：先进先出（FIFO），即最先进入队列的元素最先被处理。
应用：适用于任务调度、消息处理、广度优先搜索等需要按顺序处理数据的场景。3. 优先级队列（Priority Queue）：
特点：元素按优先级排序，每次取出的是优先级最高的元素，而不是按插入顺序。
应用：适用于任务管理（例如操作系统中的任务调度）、最短路径算法（如Dijkstra算法）、数据流中找出Top K元素等场景。这些数据结构在C++中有标准库支持（如`<stack>`、`<queue>`和`<priority_queue>`），可以帮助开发者更高效地处理特定类型的问题，提高程序的可读性和性能。
stack类
stack类的介绍
stack是 C++ 标准模板库（STL）中的一个容器适配器，用于实现后进先出（LIFO）数据结构。它基于其他序列容器（如
deque、vector或list）构建，默认使用deque作为底层容器stack<int, vector<int>> st;注：
1、定义了一个名为 st 的栈（stack）
其中包含 int 类型的元素，并使用 vector<int> 作为其底层容器
2、
stack默认使用deque作为底层容器，但可以通过这种方式替换成其他容器3、特点 & 好处
- 该栈
st仍然保持stack的 后进先出 特性。- 使用
vector作为底层容器意味着栈的元素实际上存储在一个vector中，但只能通过stack提供的接口（如push()、pop()、top()等）访问。这样做的优势在于，如果对底层容器的特性（如内存管理或其他特定操作）有特殊需求，可以灵活选择适合的容器
stack的基本操作
push()：将元素压入栈顶。pop()：移除栈顶元素。top()：返回栈顶元素的引用。只能访问栈顶元素（通过top()），无法直接访问其他位置的元素empty()：判断栈是否为空。size()：返回栈中元素的个数
stack的模拟实现
namespace sky
{
template<class T, class Container = vector<int>>
class Stack
{
public:
void push(const T& val)
{
_con.push_back(val); // 压栈插入数据
}
void pop()
{
_con.pop_back(); // 删除用尾删
}
const T& top()
{
return _con.back(); // 后进先出
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
int main()
{
sky::Stack<int,vector<int>> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
cout << st.size() << endl;
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
return 0;
}queue类
queue类的介绍
1、queue是标准库容器适配器，用于实现先进先出（FIFO）队列。它基于底层容器（如
deque或list）进行封装2、默认使用
deque作为存储容器，也可以指定其他符合双端操作要求的容器。
queue适用于需要按顺序处理数据的场景，如任务调度或广度优先搜索等
queue的基本操作
push()：向队尾添加元素。pop()：移除队头元素。front()：返回队头元素的引用。back()：返回队尾元素的引用。empty()：检查队列是否为空。size()：返回队列中元素的数量
queue的模拟实现
namespace sky
{
template<class T, class Container = list<int>>
class Queue
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
T& front()
{
return _con.front();
}
T& back()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
int main()
{
sky::Queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
cout << q.back() << endl;
cout << q.size() << endl;
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
return 0;
}优先级队列
优先级队列的介绍
priority_queue是标准库容器适配器，用于实现优先级队列，其元素根据优先级自动排序。默认情况下，它使用最大堆结构，使得队头元素总是优先级最高的元素
priority_queue适用于需要动态维护最大（或最小）元素的场景，如任务调度、路径规划等注：需要包头文件<queue>
仿函数
什么是仿函数
priority_queue的函数原型比queue和stack多了一个参数，用于指定比较函数，这个参数决定了元素在priority_queue中的排序方式。比较函数（仿函数）：
priority_queue需要一个比较函数（通常是仿函数）来定义元素之间的优先级顺序。默认情况下，它使用std::less<T>，这意味着它将按照从小到大的顺序排列，形成一个最大堆这是
priority_queue与queue和stack最显著的区别，因为priority_queue需要根据元素的优先级来组织数据，而queue和stack仅需要遵循基本的先进先出或后进先出原则
为什么要有仿函数
- 自定义比较逻辑：优先级队列默认情况下是一个最大堆，即最大的元素具有最高的优先级。但有时我们可能需要根据不同的标准来排序元素，比如最小堆或者基于对象的某个成员函数。通过使用仿函数，我们可以自定义比较逻辑，使得优先级队列能够按照我们期望的顺序排列元素。
- 状态保持：仿函数可以保持状态，这意味着它们可以在调用之间保留信息，这在某些复杂的比较逻辑中非常有用。
- 类型安全：使用仿函数可以保证类型安全，因为编译器会在编译时检查传递给仿函数的参数类型是否正确。
优先级队列的使用
成员函数
push()：插入元素，并自动调整位置。pop()：移除优先级最高的元素（队头）。top()：访问优先级最高的元素。empty()：检查队列是否为空。size()：返回元素的数量
排序准则
默认使用 std::less（大顶堆），可以通过自定义比较函数来实现小顶堆或其他排序
优先级队列的模拟实现
namespace sky
{
template<class T>
class less
{
public:
bool operator()(const T& x, const T& y)
{
// 在构建堆时，x < y 的意思是：如果 x 比 y 小，
// 那么 x 的优先级低于 y，所以 y 应该排在 x 前面
return x < y;
}
};
template<class T>
class greater
{
public:
// 当使用 greater 作为比较器时，较小的元素会排在前面，因此可以创建一个"最小优先队列"
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template<class T, class Container = vector<int>, class Compare = less<T>>
class priority_queue
{
public:
void adjust_up(int child)
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0)
{
// 如果父节点的值比子节点的值小，则交换（基于比较器的定义）
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(int parent)
{
Compare com;
int 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]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 插入元素并调整堆
void push(const T& val)
{
_con.push_back(val);
adjust_up(_con.size() - 1);
}
// 删除堆顶元素并调整堆
void pop()
{
if (!_con.empty())
{
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;
};
}
int main()
{
sky::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(5);
pq.push(4);
pq.push(2);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}
关于容器适配器
***********************************************************分割线*****************************************************************************
完结！！！
感谢浏览和阅读。
等等等等一下，分享最近喜欢的一句话:“把自己活出一道光”。
我是白子寰，如果你喜欢我的作品，不妨你留个点赞+关注让我知道你曾来过。
你的点赞和关注是我持续写作的动力！！！
好了划走吧。
