栈 队列 优先级队列 深入浅出讲解
I.前言
本章我们来探讨stack，queue以及priority_queue的使用以及实现
II.Stack类
0x00 stack介绍
栈（Stack）是一种特殊的数据结构，也是一种容器适配器，主要特点是：先进后出（LIFO），
进行插入和删除的一端，叫做栈顶，另一端为栈底。 栈在原则上不允许进行中部和底部的操作，这样会破坏栈结构的完整性，栈是遍历不是由迭代器来实现的
栈（Stack）是作为容器适配器被实现的，容器适配器是对特定类封装作为其底层容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层
如图所示，我们可以看到，栈有两个模板参数
参数1：T栈中的元素类型，同时也是底层容器中的元素类型
参数2：Container实现栈时用到的底层容器，这里为缺省参数，缺省结构为双端队列deque，也就是说，Stack的底层容器可以是任何标准的容器类模板或者一些特定的容器类
这些容器应该支持一下操作：
empty ：判空操作
back ：获取尾部元素操作
push_back ：尾部插入元素操作
pop_back ：尾部删除元素操作
0x01 Stack使用
| 函数说明 | 接口说明 |
| Stack() | 构造空栈 |
| empty() | 检测Stack是否为空 |
| size() | 返回Stack中元素个数 |
| top() | 返回栈顶元素 |
| push() | 压栈 |
| pop() | 出栈 |
#include <iostream>
#include <stack>
using namespace std;
void test_stack() {
/* 创建一个存储整型的栈 */
stack<int> st;
/* 入栈 */
st.push(1);
st.push(2);
st.push(3);
st.push(4);
/* 打印栈 */
while (!st.empty()) { // 如果栈不为空则进入循环
cout << st.top() << " "; // 打印栈顶元素
st.pop(); // 出栈
}
cout << endl;
}III. queue类
0x01 队列介绍
队列 （queue）是一种特殊的数结构，同时也是一种 容器适配器，遵循先进先出FIFO原则，其中从容器一端插入元素，另一端提取元素。队列在原则上 是不允许进行 中部 的操作，这样会破坏队列的完整性。
队列（queue）也是作为容器适配器被实现的，容器适配器是对特定类封装作为其底层容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层。元素从队尾入列，队头出列
可以看出，队列也有两个模板参数
参数1：T栈中的元素类型，同时也是底层容器的元素类型
参数2：Container实现栈是用到的底层容器，这里为缺省参数，缺省结构为双端队列 deque，queue的底层容器可以是任何标准的容器类模板或i这一些其特定的容器类
- empty ：检查队列是否为空
- size ：返回队列中的有效元素个数
- front ：返回队头元素的引用
- back ：返回队尾元素的引用
- psuh_back ：在队列尾部入队列
- pop_front ：在队列头部出队列
0x02 queue使用
| 函数声明 | 接口说明 |
| queue() | 构造空的队列 |
|
empty() |
检测队列是否为空 |
| size() | 返回队列中的元素个数 |
| back() |
返回队尾元素 |
| front() | 返回队头元素 |
| push() | 入队 |
| pop() | 出队 |
#include <iostream>
#include <queue>
using namespace std;
void test_queue() {
/* 创建一个存储整型的队列 */
queue<int> Q;
/* 入队 */
Q.push(1);
Q.push(2);
Q.push(3);
Q.push(4);
/* 打印队列 */
while (!Q.empty()) { // 如果队列不为空则进入循环
cout << Q.front() << " "; // 打印队头元素
Q.pop(); // 出队
}
cout << endl;
}IV.适配器
从应用角度来看，STL中的适配器分为三类：
- 容器适配器
container adapters - 迭代器适配器
iterator adapters - 仿函数适配器
functor adapters
其中，容器适配器 可修改底层为指定容器，如由 vector 构成的栈、由 list 构成的队列；迭代器适配器可以 实现其他容器的反向迭代器（后续介绍）；最后的仿函数适配器就厉害了，几乎可以 无限制的创造出各种可能的表达式
V.Stack和queue的底层结构
虽然 【stack】和 【queue】中也可以存放元素，但是在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器 ，这是因为【stack】和 【queue】只是对其它容器的接口进行了包装，STL 中【queue】和 【stack】默认使用 【deque】比如：
注意： 容器支持 迭代器，但是容器适配器不支持迭代器，因为栈和队列这种数据结构不能随便去遍历，不然会导致发生变化，不易维护
VI.deque 原理介绍
双端队列 deque：是一种双开口“连续“空间的数据结构，双开口的含义：可以在队尾端进行插入和删除的操作，且时间复杂度为O（1），与vector相比，头插效率高，不需要移动元素，与list相比，空间利用率比较高
0x01 deque的底层结构
deque 的底层结构通常是由多个固定大小的缓冲区组成，每个缓冲区是一个连续的存储块。这些缓冲区通过一个指向前一个缓冲区和一个指向后一个缓冲区的指针进行连接，形成一个双向链表
deque的双向链表由一个或多个缓冲区组成，每个缓冲区都包含一个指向前一个缓冲区和一个指向后一个缓冲区的指针。第一个缓冲区的指向前一个缓冲区的指针为空指针，最后一个缓冲区的指向后一个缓冲区的指针也为空指针。
当需要在deque的头部或尾部插入或删除元素时，只涉及到相关缓冲区的操作，而不会涉及其他缓冲区。这种设计使得deque的插入和删除操作时间复杂度为常数级别（O(1)）。
我们需要了解的是如果在队列头部插入元素，首先插入的是现在7占据的位置，而在队尾插入，会先占据16的位置，里面会有一个代码为：cur-first+start，是为了确定插入的相对位置
0x02 deque的缺陷
| 维度 | 优点 | 缺点 |
|---|---|---|
| 两端操 作效率 | 极高，头部 / 尾部添加、删除元素（appendleft/popleft/append/pop）均为 O(1) 时间复杂度 |
不支持高效的中间元素操作，中间插入 / 删除为 O(n) 时间复杂度 |
| 内存与扩容 | 基于链表结构实现，无需预先分配固定内存，动态扩容无性能损耗 | 内存占用略高于列表，元素存储不连续，内存局部性差 |
| 随机访问 | 支持通过索引访问元素（dq[i]），基础查询可用 |
随机访问效率远低于列表，为 O(n) 时间复杂度 |
| 功能特性 | 内置线程安全、旋转操作（rotate）、长度限制（maxlen），适合队列 / 栈场景 |
功能聚焦于双端操作，不支持切片等列表的灵活便捷操作 |
| 适用场景 | 高频两端增删、线程间数据通信、固定长度缓存、滑动窗口 | 需要大量随机访问、中间增删、切片处理的场景 |
❓ 那什么场景适合用 deque 呢？
虽然不够极致但是还是有用武之地的：大量头尾插入删除，偶尔随机访问的情况可以使用 deque。
0x03 deque，stack 和 queue 的底层默认容器
❓ 思考：为什么选择 deque 作为 stack 和 queue 的底层默认容器？
① stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以
② queue 是先进先出的特殊线性数据结构，只要具有 push_back() 和 pop_front() 操作的线性结构，都可以作为 queue 的底层容器，比如 list
但 STL 最终选择用 deque 作为 stack 和 queue 的底层容器，其主要原因是如下：
stack 和 queue 不需要遍历（因此 stack 和 queue 没有迭代器），只需要在固定的一端或者两端进行操作。
在 stack 中元素增长时，deque 比 vector 的效率高（扩容时不需要搬移大量数据）；queue 中的元素增长时，deque 不仅效率高，而且内存使用率高。 结合了 deque 的优点，而完美的避开了其缺陷。
#include<iostream>
namespace zzz
{
template<class T,class Container = deque<T>>
class Queue
{
public:
//入队
void push(const T& x)
{
_con.push_back(x);
}
//出队
void pop()
{
_con.pop_front();
}
//获取队头元素
T& front()
{
return _con.front();
}
const T& front()const
{
return _con.front();
}
//获取队尾元素
T& back()
{
return _con.back();
}
const T& back() const
{
return _con.back();
}
//获取队列中有效元素个数
size_t size() const
{
return _con.size();
}
//判空
bool empty() const
{
return _con.size() == 0;
}
//交换元素
void swap(Queue<T, Container>& q)
{
_con.swap(q._con);
}
private:
Container _con;
};
}#include<iostream>
namespace zzz
{
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
{
retunr _con.back();
}
//获取有效元素个数
size_t size() const
{
return _con.size();
}
//判空
bool empty() const
{
reutrn _con.empty();
}
//交换元素
void swap(Stack<T, Container>& st)
{
_con.swap(st._con);
}
private:
Container _con;
};
}VII.优先级队列
0x00 介绍
优先级队列 priority_queue是容器适配器的一种，常用来进行队数据的优先级处理，比如优先级高的值在前面，这其实就是数据结构的堆，它俩本质上是i相同的，底层都是以数组存储的完全二叉树，不过优先级队列priority_queue中 加入 泛型编程 的思想，且属于STL中的一部分
priority_queue是C++标准库中的一个容器适配器（container adapter），用于实现优先队列（priority queue）的数据结构。优先队列是一种特殊的队列，其中的元素按照一定的优先级进行排序，每次取出的元素都是优先级最高的。它的底层实现通常使用堆（heap）数据结构。
在C++中，priority_queue模板类定义在<queue>头文件中，可以通过指定元素类型和比较函数来创建不同类型的优先队列。比较函数用于确定元素的优先级，可以是函数指针、函数对象或Lambda表达式。
priority_queue被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类。元素从特定容器的”尾部“弹出，其称为优先级队列的顶部
0x01 区分 优先级队列 和 队列
队列是一种先进先出（FIFO）的数据类型，每次元素的入队都只能在队尾操作，出队在队头操作
优先级队列并不满足先进先出的条件，它更像是数据类型的堆，优先级队列每次出队的元素是队列中优先级最高的元素，而不是队头元素。这个优先级可以通过元素的大小进行定义。
0x02 priority_queue 构造
优先级队列 默认使用 vector 作为底层存储数据的容器，在 vector 上又使用了 堆算法 将 vector 中的元素构造成堆的结构，因此 priority_queue 就是 ---- 堆，所以在需要用到 堆 的地方，都可以考虑使用 priority_queue
0x03 priority_queue 常用接口
VIII.模拟实现priority_queue
据我所知，在优先级队列中，插入数据和删除数据的时间复杂度 为 。
默认情况下的优先级队列是大堆，我们先不考虑用仿函数去实现兼容大堆小队排列问题，
我们先去实现大堆，先把基本的功能实现好，带着讲解完仿函数后再去进行优化实现
优先级队列相较于普通的队列，其区别主要是在 push 和 pop 上，
即需要在插入 / 删除数据的同时，增添调整的功能，并且 STL 的优先级队列是由堆来维护的：
void push(const T& x) {
_con.push_back(x);
AdjustUp(_con.size() - 1);
}入队时将数据推入后，从最后一个元素开始进行上调。
出队时采用堆的删除手法，将根元素（即队头）和最后一个元素进行交换，并调用尾删掉队头。
既然用了头尾交换法，我们就不得不对队列重新调整，所以从根位置进行下调，即可完成出队。
void pop() {
assert(!_con.empty());
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}既然需要上调和下调操作，我们不可避免地需要实现上调和下调的算法。
我们这里暂时写死，设计成大堆的 AdjustUp 和 AdjustDown：
#include<iostream>
/*向上调整算法*/
void AdjustUp(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_con[parent] < _con[child])
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
/*向下调整算法*/
void AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < n && _con[child] < _con[child + 1])
{
child++;
}
if (_con[parent] < _con[child])
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}我们把_con转换的接口实现一下
const T& top() {
return _con[0];
}
size_t size() {
return _con.size();
}
bool empty() {
return _con.empty();
}0x01 仿函数
我们先来看我们写的大堆优先级队列code
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
namespace foxny {
template<class T, class Container = vector<T>>
class priority_queue {
public:
/* 向上调整算法 */
void AdjustUp(size_t child) {
size_t father = (child - 1) / 2;
while (child > 0) {
if (_con[father] < _con[child]) {
swap(_con[father], _con[child]);
child = father;
father = (child - 1) / 2;
}
else {
break;
}
}
}
/* 向下调整算法 */
void AdjustDown(size_t father) {
size_t child = father * 2 + 1; // 默认认为左孩子大
while (child < _con.size()) {
// 判断右孩子是否存在，并且是否比左孩子大？
if (child + 1 < _con.size() && _con[child] < _con[child + 1]) {
child += 1;
}
if (_con[father] < _con[child]) {
swap(_con[father], _con[child]);
father = child;
child = father * 2 + 1;
}
else {
break;
}
}
}
/* 入数据 */
void push(const T& x) {
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
/* 出数据 */
void pop() {
assert(!_con.empty());
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
/* 返回堆顶数据 */
const T& top() {
return _con[0];
}
/* 返回大小 */
size_t size() {
return _con.size();
}
/* 判断是否为空 */
bool empty() {
return _con.empty();
}
private:
Container _con;
};
}我们发现的问题是——如果之后想按升序排列，就没办法用这个代码实现了
我们这里写的是排降序的大堆，排升序的话需要再写一个小堆
C++ 在这里有一种叫仿函数的东西，可以控制这些东西，我们下面先来介绍一下仿函数
概念：使一个类的使用看上去像一个函数。可以像函数一样使用的对象，称为函数对象
其实现就是在类中重载 operator()，使得该类具备类似函数的行为，就是一个仿函数类了。
先来看一个最简单的仿函数
struct less
{
//仿函数（函数对象）——对象可以像调用函数一样去使用
bool operator()(int x,int y)
{
return x<y;
}
};
void test_functor()
{
less lessCmp;
cout<< lessCmp(10,20) <<endl;
}
我们还可以使其能够支持泛型，我们加一个 template 模板:
// 支持泛型
template<class T> struct less {
bool operator()(const T& x, const T& y) const {
return x < y;
}
};
void test_functor() {
less<int> lessCmp;
cout << lessCmp(10, 20) << endl;
}less 是用来比较谁小的，对应的，我们再实现一个比较谁大的 greater：
// less: 小于的比较
template<class T> struct less {
bool operator()(const T& x, const T& y) const {
return x < y;
}
};
// greater: 大于的比较
template<class T> struct greater {
bool operator()(const T& x, const T& y) const {
return x > y;
}
};
void test_functor() {
less<int> lessCmp;
cout << lessCmp(10, 20) << endl;
greater<int> GreaterCmp;
cout << GreaterCmp(10, 20) << endl;
}0x02加入仿函数后的priority_queue
我们现在用仿函数去比较那些数据，这样就不会写死了
#include <iostream>
#include <vector>
#include <functional> // 这里放的是一些仿函数
#include <assert.h>
using namespace std;
namespace foxny {
// less: 小于的比较
template<class T>
struct less {
bool operator()(const T& x, const T& y) const {
return x < y;
}
};
// greater: 大于的比较
template<class T>
struct greater {
bool operator()(const T& x, const T& y) const {
return x > y;
}
};
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue {
public:
/* 向上调整算法 */
void AdjustUp(size_t child) {
Compare cmpFunc;
size_t father = (child - 1) / 2;
while (child > 0) {
// if (_con[father] < _con[child]) {
if (cmpFunc(_con[father], _con[child])) {
swap(_con[father], _con[child]);
child = father;
father = (child - 1) / 2;
}
else {
break;
}
}
}
/* 向下调整算法 */
void AdjustDown(size_t father) {
Compare cmpFunc;
size_t child = father * 2 + 1; // 默认认为左孩子大
while (child < _con.size()) {
// if (child + 1 < _con.size() && _con[child] < _con[child + 1]) {
if (child + 1 < _con.size() && cmpFunc(_con[child], _con[child + 1])) {
child += 1;
}
// if (_con[father] < _con[child]) {
if (cmpFunc(_con[father], _con[child])) {
swap(_con[father], _con[child]);
father = child;
child = father * 2 + 1;
}
else {
break;
}
}
}
/* 入数据 */
void push(const T& x) {
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
/* 出数据 */
void pop() {
assert(!_con.empty());
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
/* 返回堆顶数据 */
const T& top() {
return _con[0];
}
/* 返回大小 */
size_t size() {
return _con.size();
}
/* 判断是否为空 */
bool empty() {
return _con.empty();
}
private:
Container _con;
};
}
// 大于比较，搞小堆
void test_priority_queue2() {
priority_queue<int, vector<int>, greater<int>> pQ;
pQ.push(2);
pQ.push(5);
pQ.push(1);
pQ.push(6);
pQ.push(8);
while (!pQ.empty()) {
cout << pQ.top() << " ";
pQ.pop();
}
cout << endl;
}
// 小于比较，搞大堆
void test_priority_queue1() {
priority_queue<int> pQ;
pQ.push(2);
pQ.push(5);
pQ.push(1);
pQ.push(6);
pQ.push(8);
while (!pQ.empty()) {
cout << pQ.top() << " ";
pQ.pop();
}
cout << endl;
}
0x03 迭代器实现
// 创造空的优先级队列
priority_queue()
: _con()
{}
// 迭代器
template<class InputIterator>
priority_queue (InputIterator first, InputIterator last)
: _con(first, last)
{
while (first != last) {
_con.push_back(*first++);
}
for (int father = (_con.size()-1-1) / 2; father >= 0; father++) {
AdjustDown(father);
}
}IX priority_queue面试题
优先级队列（堆）可以用来进行排序和解决 Top-K 问题，比如 查找第 k 个最大的值 就比较适合使用优先级队列
思路：利用数组建立大堆，数组从大到小排序，删除前K-1个元素，选出队头即可
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();
}
};
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
24
0- 0
已为社区贡献2条内容
所有评论(0)