【C++】Stack Queue 仿函数

📝前言：
这篇文章我们来讲讲STL中的stack和queue。因为前面我们已经有了string、vector和list的学习基础，所以这篇文章主要关注一些stack和queue的细节问题，以及了解一下deque（缝合怪）和priority_queue ，并且模拟实现priority_queue。

🎬个人简介：努力学习ing
📋个人专栏：C++学习笔记
🎀CSDN主页愚润求学
🌄其他专栏：C语言入门基础，python入门基础，python刷题专栏

文章目录

一，Stack && queue
- 1. 用vector 适配 Stack
- 2. 用list模拟实现queue
- 3. 简单认识deque
二，priority_queue
- 1. 认识优先级队列
- 2. 仿函数
- 3. 模拟实现priority_queue

一，Stack && queue

stack和queue其实是container adaptor（容器适配器）

在STL里面他们是用deque来适配的。也就是通过deque来封装，内部实际上用的是deque的接口。
stack.top()返回的是栈顶元素的引用，queue.front()一样
stack.pop()并不会返回值，而是直接pop掉栈顶元素，queue.pop()一样

除了deque能做适配器以外，其他的容器也都可以，比如vector和list

1. 用vector 适配 Stack

对于Stack而言，要实现的是同一边删除与插入的操作，而vector里面正好有pop_back和push_back 这样的接口。

#include<vector>namespace tr
{template<typename T>class stack{public:stack(){}void push(const T& x) { _a.push_back(x); }void pop() { _a.pop_back(); }const T& top() const { return _a.back(); }T& top() { return _a.back(); }size_t size() { return _a.size(); }bool empty() { return _a.empty(); }private:std::vector<T> _a; // 栈的底层用数组};
}

测试代码：

#include<iostream>
#include<vector>
#include"Stack.h" using namespace std;void test_Stack() {tr::stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);while (!st.empty()){cout << st.top() << endl;st.pop();}cout << st.empty() << st.size() << endl;
}int main() {test_Stack();return 0;
}

注意头文件和using namespace std;的位置问题：头文件展开时会向上找标识符，比如“Stack.h”用了一个cout，但是using namespace std;在下面，向上找不到就会报错编译错误：“未定义标识符”

2. 用list模拟实现queue

list要满足的要求是一边插入一边删除，由于vector没有头删，所以这时候选择list是更好的

模拟实现：

#pragma once
#include<list>namespace tr
{template<typename T>class queue{public:queue() {}void push(const T& x) { _a.push_back(x); }const T& front() const { return _a.front(); }T& front() { return _a.front(); }void pop() { _a.pop_front(); } // 头删size_t size() { return _a.size(); }bool empty() { return _a.empty(); }private:std::list<T> _a;};}

测试代码：

#include<iostream>
#include"Queue.h" using namespace std;void test_Queue() {tr::queue<int> ls;ls.push(1);ls.push(2);ls.push(3);ls.push(4);ls.push(5);while (!ls.empty()){cout << ls.front() << endl;ls.pop();}cout << "empty: " << ls.empty() << endl << "size: " << ls.size() << endl;
}int main() {test_Queue();return 0;
}

运行结果：
在这里插入图片描述

3. 简单认识deque

deque是双端队列，即两边都可以插入和删除

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个
动态的二维数组，其底层结构如下图所示：
在这里插入图片描述
map中控是一个指针数组，每个指针指向一个数组（每个数组大小一样），这些数组才是存储数据真正的地方。
迭代器由四个部分组成：

给定一个“下标” x 找到容器中对应的数据：先 x / n：找到对应的数组编号，再 x % n 找到在组内的位置
判断是否到达一个数组的尾部：cur == last

deque 和 vector 以及 list 的比较：

头插尾插效率更高
下标随机访问比vector差一点
中间插入数据效率低，因为要移动数据

由因为：

stack和queue没有迭代器，不需要访问
实现stack时：deque的扩容效率比vector高
实现queue时：一次性申请一块数组，在queue元素个数增长时，不需要想list一样一个个申请，效率更高，且内存利用率更高

所以，stack和queue用了deque做适配器。

二，priority_queue

1. 认识优先级队列

priority_queue：优先队列，也在头文件< queue > 里面
意思是：在使用top()和pop()的时候会取优先级高的，默认是大的元素优先级高。（简单来说就是降序）
底层实现时堆，而堆的底层是数组。
在这里插入图片描述

简单使用一下：

int main() {priority_queue<int> pq;pq.push(3);pq.push(2);pq.push(6);pq.push(1);pq.push(8);while (!pq.empty()){cout << pq.top();pq.pop();}return 0;
}

运行结果：
在这里插入图片描述

2. 仿函数

仿函数是一个类，但是可以像调用函数一样去调用这个类，作为回调函数使用。通过重载()来实现

仿函数使用示例：

class Adder {
public:// 重载 () 运算符int operator()(int a, int b) const {return a + b;}
};int main() {Adder adder;// 像调用函数一样调用仿函数对象int result = adder(3, 4); // 或者用匿名对象：Adder()(3, 4) Adder()——创建匿名对象，(3 ,4)调用重载的()std::cout << "Result: " << result << std::endl;return 0;
}

3. 模拟实现priority_queue

priority_queue头文件：

#pragma once
#include<iostream>
#include<vector>
using namespace std;template<class T>
class Less
{
public:bool operator()(const T& a, const T& b){return a < b;}
};template<class T>
class Greater
{
public:bool operator()(const T& a, const T& b){return a > b;}
};namespace tr
{template<class T, class Container = vector<T>, class Compare = Less<T>>// Compare 就是比较方法class priority_queue{public:void Adjustup(size_t child){Compare com; // 构造仿函数对象size_t parent = (child - 1) / 2;while (child > 0){if (com(_a[child], _a[parent])) // 用仿函数对象调用仿函数{std::swap(_a[child], _a[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}}void Adjustdown(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _a.size()){if (child + 1 < _a.size() && com(_a[child + 1], _a[child])){child++;}if (com(_a[child], _a[parent])) // 相当于孩子节点小于父亲{std::swap(_a[child], _a[parent]);parent = child;child = parent * 2 + 1;}else {break;}}}priority_queue(){}void push(const T& x){_a.push_back(x);Adjustup(_a.size() - 1);}T& top(){return _a[0];}const T& top() const{return _a[0];}void pop(){std::swap(_a[0], _a[_a.size() - 1]);_a.pop_back();Adjustdown(0);}size_t size() { return _a.size(); }bool empty() { return _a.empty(); }private:Container _a;};};

测试代码：

#include"priority_queue.h"
int main() {tr::priority_queue<int, vector<int>, Greater<int>> pq; // 传入的不是less，而是Less<int>，类模板传的是类型，函数模板传才是参数pq.push(3);pq.push(2);pq.push(6);pq.push(1);pq.push(8);while (!pq.empty()){cout << pq.top();pq.pop();}cout << endl;return 0;
}