一、stack的基本知识
1、什么是栈
栈（Stack）是一种常见的数据结构，它遵循后进先出（LIFO）的原则。栈是一种STL中的容器，类似于现实生活中的堆叠物体，只能在顶部进行插入和删除操作。
栈具有两个主要操作：
- 入栈（Push）：将元素添加到栈的顶部，成为新的栈顶。
- 出栈（Pop）：从栈的顶部移除元素，并返回被移除的元素。
s
由于栈遵循后进先出的原则，最后一个入栈的元素将是第一个出栈的元素，即最新的元素先被访问或移除。
栈还具有一个特殊的属性——栈顶指针（Top），它指向栈的顶部元素。当执行入栈操作时，栈顶指针上移；而在执行出栈操作时，栈顶指针下移。
栈常常用于解决与层次结构相关的问题，例如函数调用、表达式求值、括号匹配、回溯算法等。在计算机内存管理中，栈也被用于存储函数的局部变量、参数以及程序执行期间的临时数据。
需要注意的是，栈具有一定的容量限制，称为栈的大小。当栈已满时，执行入栈操作将导致栈溢出（Stack Overflow）；而当栈为空时，执行出栈操作将导致栈下溢（Stack Underflow）
2、栈的基本使用
对栈(stack)来说在C++中进行来封装，他的底层我们看做是用一个类来实现的，所以他有自己的成员函数和成员变量。通过前面我们对vector和list的学习相信大家对STL容器的都比较熟悉了，下面我们主要和大家介绍一下stack的重点接口.
栈的重要接口：
| 函数说明 | 接口说明 |
| stack() | 构造空的栈 |
| empty() | 判断栈是否为空 |
| size() | 返回栈中有多少的元素 |
| top() | 返回栈顶中的元素 |
| push() | 将元素val压入栈中 |
| pop() | 将stack中尾部弹出 |
栈代码使用演示：
在演示之前，看一个代码：
for (auto e : st) { } //代码不可用
运行之后程序会报错，这是为什么呢？ 这是因为使用aoto for循环的本质其中也运用到了迭代器，也就是要有begin（），end()的成员函数，但是stack是没有的。
那我们将怎么样去打印出stack中的数据呢？
这里我就用用到top（）获取栈顶元素，和pop（）将栈顶元素出栈就可以了。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<stack> using namespace std; int main() { stack<int> st; st.push(1); st.push(2); st.push(3); st.push(4); st.push(5); while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; return 0; }
3、栈的模拟实现
为了更好的理解栈，下面我将模拟实现栈。模拟实现栈时，我们不妨思考一下我们是用数组实现还是用链表实现栈呢？
我们知道数组有数组的好处，链表也有链表的的好处，那我们可以二个都用可以吗？
其实是可以的，这就不得不提一下适配器模式，那什么是适配器模式呢？
其实就是将以有的东西封装转化成你想要的东西。
template<class T, class Container> class stack { public: private: Container _con; };
这里我们只要多传一个模板参数，Container就可以了。
我们在用自己定义栈，创建对象时多传一个参数就可以了，这样我们就在底层上既实现用list实现的栈，又实现了vector实现的栈
stack<int，linst<int>> st;//链表实现 stack<int，vector<int>> st;//数组实现
下面我们只要完善好成员函数就可以实现自己的栈了
namespace pjb { template<class T, class Container > class stack { public: void push(const T& x) { _con.push_back(x); } 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; }; }
测试 ：
二、queue的基本知识
1、什么是队列
队列（Queue）是一种数据结构，它遵循先进先出（First-In-First-Out，FIFO）的原则。队列中的数据项按照插入的顺序排列，最先插入的数据项首先被移除。
队列可以比喻成现实生活中的排队等候的场景。新来的人必须排在队尾，而排在队头的人最先离开队列。
队列有两个基本操作：
- 入队（Enqueue）：将数据项添加到队列的末尾。
- 出队（Dequeue）：将队列的第一个数据项移除，并返回该数据项。
队列常常用于模拟系统中的排队行为，如任务调度、消息传递等。在编程中，队列可以使用数组或链表等数据结构来实现。
但是要注意并非所有队列都是先进先出的，有一个叫优先级的队列就不是这样的，后面在为大家介绍，我们先了解基本队列的用法。
2、队列的基本用法
队列我们在使用这个容器的时候，重点关注几个接口就好了
队列的重要接口：
| 函数声明 | 接口说明 |
| queue() | 构造空的队列 |
| empty() | 检测队列是否为空，是返回true，否则返回false |
| size() | 回队列中有效元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素val入队列 |
| pop() | 将队头元素出队列 |
队列代码演示：
int main() { queue<int> qe; qe.push(1); qe.push(2); qe.push(3); qe.push(5); qe.push(6); while (!qe.empty()) { cout << qe.front() << " "; qe.pop(); } }
3、队列的模拟实现
这里我们常常说，vector和list都有各自的优缺点：
vector:
缺点：头部中部插入删除效率低，扩容有消耗
list：
缺点：不支持随机访问，CPU高速缓命中低。
其实vector和list的缺点和优点是互补的，那有没有一个容器兼容二者的优点呢？
C++中有一个容器 deque（双端队列）（Double Ended Queue，简称为Deque）是一种允许从两端进行插入和删除操作的队列。它可以在队列的前端和后端同时进行插入和删除操作。
双端队列支持以下几种基本操作：
- 在队头插入元素（Insert at Front）：将一个元素插入到双端队列的前端。
- 在队尾插入元素（Insert at Rear）：将一个元素插入到双端队列的后端。
- 从队头删除元素（Delete from Front）：从双端队列的前端删除并返回一个元素。
- 从队尾删除元素（Delete from Rear）：从双端队列的后端删除并返回一个元素。
- 获取队头元素（Get Front）：返回双端队列的前端元素。
- 获取队尾元素（Get Rear）：返回双端队列的后端元素。
双端队列优缺点：
优点：
- 与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不 需要搬移大量的元素，因此其效率是必vector高的。
- 与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段
缺点：
- 不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到 某段小空间的边界，导致效率低下
所以当我们传模板的第二个参数时可以直接传deque。
namespace pjb { template<class T, class Container = deque<T>> class queue { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_front(); } const T& fornt() { return _con.front(); } const T& back() { return _con.back(); } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } private: Container _con; }; }
三、优先队列
1、优先队列的基本知识
优先队列（Priority Queue）是一种特殊的队列(是一种容器适配器)，它根据元素的优先级来确定出队的顺序。与普通队列不同，优先队列中的元素被赋予了优先级，优先级高的元素会先被出队。
优先队列的基本操作包括：
- 入队（Enqueue）：将元素插入到优先队列中，并根据其优先级进行适当的排序。
- 出队（Dequeue）：移除具有最高优先级的元素，并返回该元素。
- 获取队头元素（Get Front）：获取具有最高优先级的元素，但不从队列中移除。
优先队列可以使用不同的数据结构来实现，其中一个常见的实现方式是使用堆（Heap）。堆是一种完全二叉树，具有一些特殊的性质使得它适用于实现优先队列。在堆中，树的每个节点都比它的子节点具有更高的优先级。
优先队列的特点：
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成 堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意： 默认情况下priority_queue是大堆。
优先队列的操作函数：
| 函数声明 | 接口说明 |
| priority_queue()/priority_queue(first,last) | 构造一个空的优先级队列 |
| empty( ) | 检测优先级队列是否为空，是返回true，否则返回 false |
| top( ) | 返回优先级队列中最大(最小元素)，即堆顶元素 |
| push() | 在优先队列中插入元素 |
| pop() | 删除优先级队列中最大(最小)元素，即堆顶元素 |
注意：
- 默认情况下，priority_queue是大堆。
- 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载
2、仿函数
仿函数（Functor）是一种具有函数行为的对象，实际上是将函数行为封装在一个类或结构体中。它可以像函数一样被调用，可以作为函数参数传递，也可以作为返回值返回。
在C++中，仿函数可以通过重载operator()运算符来实现函数调用操作。通过这种方式，仿函数可以像普通函数一样被调用，而且可以带有自己的状态和行为。
class AddFunctor { public: int operator()(int a, int b) const { return a + b; } }; int main() { AddFunctor add; int result = add(3, 4); // 调用仿函数 // 结果为7 return 0; }
那我们不由的想到函数和仿函数有什么区别吗？
仿函数（Functor）实际上是一个类对象，它的对象可以像函数一样被调用。
函数是一段可执行的代码块，可以通过函数名直接调用。
区别：
- 类对象：仿函数是一个类对象，而函数是一个独立的代码块。仿函数的行为可以通过重载函数调用运算符
operator()来定义，使得它可以被像函数一样调用。- 状态保持：仿函数可以在自己的内部保留状态信息，这些信息可以在不同的函数调用之间保持，并影响后续的函数调用。而函数通常不具备状态保持的能力，每次调用都是独立的，无法直接记住之前的状态。
- 可定制性：由于仿函数是一个类对象，我们可以根据需要定制它的行为，通过它的成员变量和函数实现更复杂的逻辑。函数则相对简单，无法直接修改其内部的逻辑。
- 应用场景：仿函数常用于STL的算法中，比如排序、查找、遍历等操作，因其灵活的行为定义和可定制性。函数则广泛应用于各种编程场景，无论是简单的数学运算还是复杂的业务逻辑
3、priority_queue的模拟实现
在模拟实现优先队列，我们重点关注向上调整和向下调整的方法，来进行建堆。
这里我们也用到我们上面讲的仿函数：
template<class T> class less { public: bool operator()(const T& x, const T& y)const { return x < y; } }; template<class T> class greator { bool operator()(const T& x, const T& y)const { return x > y; } };
大家可能不由的会想，这个就不是一个简单的大小比较吗？有必要写的这么复杂吗？，这种仿函数有必要被定义出来吗？
其实不然，虽然我们在写简单大小比较时候，是会增加了代码的复杂性，但是在实际的开发中，我们经常遇到需要对数据进行复杂排序或计算等操作，此时使用仿函数就可以极大地提高程序的灵活性和可扩展性。
以排序为例，STL提供了多种排序算法，如sort、stable_sort等，这些算法均可通过传入一个比较函数来定义排序规则。使用仿函数定义排序规则时，我们可以根据自己的需要灵活地定制排序规则，从而实现更加复杂的排序操作
#pragma once #include<algorithm> namespace pjb { template<class T> class less { public: bool operator()(const T& x, const T& y)const { return x < y; } }; template<class T> class greator { 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: priority_queue() {} //建堆 template <class InputIterator> priority_queue(InputIterator first, InputIterator last) :_con(first, last) { for (int i = (_con.size() - 1 - 1) / 2;i >= 0;--i) { 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]) if (com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); 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[child], _con[parent]); 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; }; }
4、反向迭代器的模拟实现
template<class Iterator,class Ref,class Ptr> class ReverseIterator { typedef ReverseIterator<Iterator, Ref, Ptr>Self; public: ReverseIterator(Iterator it) :_it(it) {} Ref operator*() { Iterator tmp = _it; return *(--tmp); } Ptr operator->() { return &(operator*()); } Self& operator--() { ++_it; return *this; } bool operator!=(const Self& s)const { return _it != s._it; } private: Iterator _it; };
