1. 栈和队列的介绍
2. 栈和队列的使用
最小栈
栈的压入、弹出序列
逆波兰表达式求值
拓展：如何从中缀变为后缀
3. 两种设计模式
设计模式目前分为26种，这里就只介绍两种
- 适配器模式
- 迭代器模式
在日常生活中，我们常见的适配器通常为电源适配器(充电器) -- 电源电压为220v，但是我们的设备并不需要这么高的电压(起保护作用) 需要将电源电压适配到我们所需的电压:50v/36v...
==适配器模式：将已有的东西通过封装转换成我们所需的东西==
==迭代器模式：不暴露底层的实现细节，经过封装后提供统一的方式来访问容器==
4. 栈的模拟实现
gitee提交代码：栈的模拟实现
栈遵循"先入后出"的原则，我们是否需要重新实现一个数据结构呢？--能不能采用之前学习的数据结构进行转换呢？
加上缺省值
template <class T,class Container = vector<T>>
5. 队列的模拟实现
6. deque的介绍(双端队列)
双端队列的结构：中控+buffer
在日常的使用场景比较少见，不像vector和list极致
使用场景 ：既支持头插头删，又支持尾插尾删 对于随机访问和中间插入比较少
那么就是栈和队列了
所以，deque适合作为栈和队列的适配器
7. 优先级队列
7.1 优先级队列的介绍和使用
数组中的第K个最大元素
思路1：建大堆 + pop K次
思路2：建K个数小堆
7.2 优先级队列的模拟实现
1. 基本框架的搭建
#include <iostream>
#include <vector>
using namespace std;
namespace hx
{
template<class T,class Container = vector<T>>
class priority_queue
{
public:
// 建堆
// 拿迭代器区间初始化
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first,last)
{
// 从最后一个非叶子结点开始向下调整 -- O(N)
for (int i = (_con, size() - 1 - 1) / 2; i >= 0; i--)
{
adjust_down(i);
}
// 也可以采用向上调整建堆的方式
// 但是时间复杂度是O(N*logN) -- 移动的路径更长
}
void adjust_down()
{
}
void adjust_up()
{
}
void push(const T& x)
{
// vector的尾插
_con.push_back(x);
// 将刚刚尾插的元素进行向上调整
adjust_up(_con.size()-1);
}
void pop()
{
// 将堆顶的元素和最后一个元素交换
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;
};
}
2. 向上/下调整算法
不管是向上还是向下调整算法都面临建大堆还是建小堆的问题(都可以 -- 无非就是改个判断条件)
假设我们构建的是大堆
// 孩子结点 -- 往上调整
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
// 循环结束条件 拿child判断 当child = 0时循环结束 -- child到堆顶
// 因为是size_t 所以不能用>=来判断(不然就是死循环)
while (child > 0)
{
//大堆 -- 父 > 子
if (_con[parent] < _con[child])
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
3. 验证实现成功
8. 仿函数/函数对象
1. 实现仿函数
2. 仿函数的用处
从实现完成的代码来看感觉仿函数没啥作用，要实现一个operator()干啥，咱们举例说明
例一：冒泡排序控制升降序
例二：优先级队列
优先级队列中也存在建大堆小堆(升降序)的问题
例三：Date类型
==解决奇葩报错：只能说使用模板时，还是要小心注意==
那么对于 Date* 类型呢？
9. 反向迭代器
其实反向迭代器也是一种设计模式，在STL源码当中是通过使用正向迭代器来构造的反向迭代器
9.1 反向迭代器的模拟实现
9.2 反向迭代器的应用场景
