【C++初阶】12. Stack(栈)和Queue(队列)

2024-04-07 43

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【C++初阶】12. Stack(栈)和Queue(队列)

1. 栈和队列的介绍

栈的介绍
 队列的介绍
在这里插入图片描述

2. 栈和队列的使用

最小栈

在这里插入图片描述

栈的压入、弹出序列

在这里插入图片描述

逆波兰表达式求值

在这里插入图片描述

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

在这里插入图片描述

3. 两种设计模式

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

适配器模式
迭代器模式

在日常生活中，我们常见的适配器通常为电源适配器(充电器) -- 电源电压为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;
                }
            }
        }