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

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

1. 栈和队列的介绍

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

2. 栈和队列的使用

最小栈

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

栈的压入、弹出序列

在这里插入图片描述

逆波兰表达式求值

在这里插入图片描述
在这里插入图片描述

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

在这里插入图片描述

3. 两种设计模式

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

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

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

4. 栈的模拟实现

gitee提交代码:栈的模拟实现
栈遵循"先入后出"的原则,我们是否需要重新实现一个数据结构呢?--能不能采用之前学习的数据结构进行转换呢?
在这里插入图片描述
加上缺省值

    template <class T,class Container = vector<T>>
AI 代码解读

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;
    };
}
AI 代码解读

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;
                }
            }
        }
AI 代码解读

3. 验证实现成功

在这里插入图片描述

8. 仿函数/函数对象

1. 实现仿函数

在这里插入图片描述

2. 仿函数的用处

从实现完成的代码来看感觉仿函数没啥作用,要实现一个operator()干啥,咱们举例说明

例一:冒泡排序控制升降序

在这里插入图片描述
在这里插入图片描述

例二:优先级队列

优先级队列中也存在建大堆小堆(升降序)的问题
在这里插入图片描述
在这里插入图片描述

例三:Date类型

==解决奇葩报错:只能说使用模板时,还是要小心注意==
在这里插入图片描述
在这里插入图片描述
那么对于 Date* 类型呢?
在这里插入图片描述

9. 反向迭代器

其实反向迭代器也是一种设计模式,在STL源码当中是通过使用正向迭代器来构造的反向迭代器

9.1 反向迭代器的模拟实现

在这里插入图片描述

9.2 反向迭代器的应用场景

在这里插入图片描述
在这里插入图片描述

目录
打赏
0
3
3
0
39
分享
相关文章
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
46 1
|
2月前
|
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
65 21
|
2月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
158 77
|
2月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
43 7
|
2月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
52 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
【C++篇】深度解析类与对象(中)
在上一篇博客中,我们学习了C++类与对象的基础内容。这一次,我们将深入探讨C++类的关键特性,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载、以及取地址运算符的重载。这些内容是理解面向对象编程的关键,也帮助我们更好地掌握C++内存管理的细节和编码的高级技巧。
【C++篇】深度解析类与对象(上)
在C++中,类和对象是面向对象编程的基础组成部分。通过类,程序员可以对现实世界的实体进行模拟和抽象。类的基本概念包括成员变量、成员函数、访问控制等。本篇博客将介绍C++类与对象的基础知识,为后续学习打下良好的基础。