1. 栈和队列的介绍

栈的介绍
队列的介绍

2. 栈和队列的使用

最小栈

栈的压入、弹出序列

逆波兰表达式求值

拓展：如何从中缀变为后缀

3. 两种设计模式

设计模式目前分为26种，这里就只介绍两种

1. 适配器模式
2. 迭代器模式

在日常生活中，我们常见的适配器通常为电源适配器(充电器) -- 电源电压为220v，但是我们的设备并不需要这么高的电压(起保护作用) 需要将电源电压适配到我们所需的电压:50v/36v...
==适配器模式：将已有的东西通过封装转换成我们所需的东西==
==迭代器模式：不暴露底层的实现细节，经过封装后提供统一的方式来访问容器==

4. 栈的模拟实现

gitee提交代码：栈的模拟实现
栈遵循"先入后出"的原则，我们是否需要重新实现一个数据结构呢？--能不能采用之前学习的数据结构进行转换呢？

加上缺省值

    template <class T,class Container = vector<T>>

5. 队列的模拟实现

gitee代码提交：队列的实现

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 反向迭代器的应用场景