C++适配器——stack queue

栈和队列

本章思维导图：
在这里插入图片描述注：本章思维导图对应的.xmind和.png文件都已同步导入至资源，可免费查看

文章目录

  • 栈和队列
  • 1. 适配器
  • 2. 栈 stack
    • 2.1 概念及结构
    • 2.2 使用
    • 2.3 模拟实现
  • 3. 队列 queue
    • 3.1 普通队列 queue
      • 3.1.1 概念及结构
      • 3.1.2 使用
      • 3.1.3 模拟实现
    • 3.2 优先队列 priority_queue
      • 3.2.1 概念及结构
      • 3.2.2 使用
      • 3.2.3 模拟实现
  • 4. 双端队列 deque
    • 4.1 概念及结构
    • 4.2 使用
    • 4.3 优缺点和适用情况

1. 适配器

和以往的vector、string等容器不同，我们今天所要讲的stack、queue等并不是所谓的容器，而是适配器

适配器是一种设计模式，它可以将类的接口处理转换为用户希望得到的另一种接口

在这里插入图片描述

2. 栈 stack

在这里插入图片描述

2.1 概念及结构

  • 栈：是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶，另一端为栈底。

  • 栈中的数据元素遵守后进先出原则

  • 压栈：栈的插入操作称为进栈/压栈/入栈，其位置在栈顶

  • 出栈：栈的删除操作称为出栈，其位置也在栈顶

在这里插入图片描述

2.2 使用

栈的使用需要包含头文件：

<stack>

stack是一个模板类，其具体声明如下：

template <class T, class Container = deque<T> > class stack;
  • T即为stack存储数据的具体类型
  • 而Container则为stack所适配的容器，deque为stack默认的适配容器

其包含如下的常见操作：

函数接口接口说明
void push (const value_type& val);数据val入栈
void pop();出栈顶数据
value_type& top();
const value_type& top() const;		返回栈顶元素
size_type size() const;返回栈的大小
bool empty() const;判断栈是否为空

我们可以用一道经典例题来对stack栈的使用进行熟悉：👉最小栈

在这里插入图片描述

参考代码：

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        _st.push(val);

        if (_minst.empty() || val <= _minst.top())
            _minst.push(val);
    }
    
    void pop() {
        int pop_val = _st.top();
        _st.pop();

        if (pop_val == _minst.top())
            _minst.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }

    stack<int> _st;	//普通栈
    stack<int> _minst;	//存储最小元素的栈
};

2.3 模拟实现

stack栈是一个适配器，因此和以往我们模拟实现vector等容器不同，并不需要从头到尾全部自己实现一遍，只需要利用现有的容器复用适配就好了。

由于stack是一个先入后出（FILO）的结构，因此进行适配的容器也必须要满足以下的操作：

  • push_back()，尾插
  • pop_back()，尾删
  • size()，返回数据个数
  • empty()，判断是否为空
  • back()，返回尾部数据
namespace TEST
{
	template<class T, class container = deque<T>>
	class stack
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		
		void pop()
		{
			_con.pop_back();
		}

		T& top()
		{
			return _con.back();
		}

		const T& top() const
		{
			return _con.back();
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}
	private:
		container _con;
	};
}

3. 队列 queue

3.1 普通队列 queue

在这里插入图片描述

3.1.1 概念及结构

  • 队列：只允许在一端进行入数据操作，在另一端进行删除数据操作的特殊线性表
  • 遵循先进先出的原则FIFO
  • 入队列：进行插入操作的一段叫做队尾
  • 出队列：进行删除操作的一段叫做队头

在这里插入图片描述

3.1.2 使用

使用时需要包含头文件

<queue>

queue是一个模板类，其具体的声明如下

template <class T, class Container = deque<T> > class queue;
  • T即为queue存储数据的具体类型
  • 而Container则为queue所适配的容器，deque为queue默认的适配容器

其包含如下的常见操作：

函数接口接口说明
void push (const value_type& val);队尾入队
void pop();队头出队
value_type& front();
const value_type& front() const;		返回队头数据
value_type& back();
const value_type& back() const;		返回队尾数据
bool empty() const;判断队列是否为空
size_type size() const;返回队列大小

同样，我们用一道例题来熟悉队列queue的操作：👉两个队列实现栈

示例代码：

class MyStack {
public:
    MyStack() {

    }
    
    void push(int x) {
        q_in.push(x);
    }
    
    int pop() {
        //将入队队列数据导入至辅助队列，留下最后一个数据，即出队数据
        while (q_in.size() > 1)
        {
            int val = q_in.front();
            q_in.pop();
            q_out.push(val);
        }
        int ret = q_in.front();
        q_in.pop();
		//将辅助队列的数据导回入队队列
        while (!q_out.empty())
        {
            int val = q_out.front();
            q_out.pop();
            q_in.push(val);
        }

        return ret;
    }
    
    int top() {
        return q_in.back();
    }
    
    bool empty() {
        return q_in.empty();
    }

    queue<int> q_in;	//入队队列
    queue<int> q_out;	//辅助出队队列
};

3.1.3 模拟实现

同样，queue也是一个适配器，只需要对符合条件的容器进行复用适配即可

适配容器需要满足以下接口：

  • push_back()，尾插
  • pop_front()，头删
  • size()，返回数据个数
  • empty()，判断是否为空
  • back()，返回尾部数据
  • front()，返回头部数据

所以我们知道，容器vector不能作为queue的适配容器

namespace TEST
{
	template<class T, class container = deque<T>>
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_front();
		}

		T& back()
		{
			return _con.back();
		}

		T& front()
		{
			return _con.front();
		}

		const T& back() const
		{
			return _con.back();
		}

		const T& front() const
		{
			return _con.front();
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}
	private:
		container _con;
	};
}

3.2 优先队列 priority_queue

在这里插入图片描述

3.2.1 概念及结构

优先队列实际上就是数据结构中的堆，如果对堆的结构性质及其用法不太了解，强烈建议先看看👉数据结构——堆

3.2.2 使用

使用时需要包含头文件：

<queue>

priority_queue是一个模板类，其具体的声明如下：

template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;

  • T即为priority_queue存储数据的具体类型

  • 而Container则为priority_queue所适配的容器，vector为priority_queue默认的适配容器

  • Compare是一个仿函数，确定这个堆是大堆还是小堆。priority_queue默认的是大堆

其包含如下常见操作：

函数接口接口说明
void push (const value_type& val);添加数据
void pop();删除堆顶元素
const value_type& top() const;返回堆顶元素
size_type size() const;返回堆的大小
bool empty() const;判断堆是否为空

同样，我们通过一道例题来熟悉priority_queue的使用：👉数组中第K大的元素

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //利用数组的前K个数构建小堆
        priority_queue<int, vector<int>, greater<int> > pq(nums.begin(), nums.begin() + k);

        //遍历剩下的数据
        //如果数据比堆顶元素大，就删除堆顶元素，再将新的数据入堆
        for (int i = k; i < nums.size(); i++)
        {
            if (nums[i] > pq.top())
            {
                pq.pop();
                pq.push(nums[i]);
            }
        }
		
        //最后大小为K的小堆最大的K个数字
        //堆顶就是第K大的数据
        return pq.top();
    }
};

3.2.3 模拟实现

这里我们先来讲一讲什么是仿函数

通俗的来讲，仿函数其实就是重载了运算符()的类对象

因为这个类对象重载了()，所以我们可以像调用函数一样来调用这个类的某个功能。所以我们称其为仿函数

举个例子：

template <class T>
struct Less
{
	bool operator() (const T& a, const T& b)
	{
		return a < b;
	}
};

int main()
{
	Less<int> le;
	cout << le(1, 4) << endl;

	return 0;
}

这里我们定义了一个类模板Less，在这个里面重载了运算符()用来确定两个数的大小关系

之后我们就可以用Less实例化出的对象来调用()的重载，也就可以像使用函数一样来使用这个类了。

priority_queue是一个适配器，进行适配的容器需要满足以下条件：

  • push_back()，尾插
  • pop_back()，尾删
  • size()，返回数据个数
  • empty()，判断是否为空
  • back()，返回尾部数据
namespace TEST
{
    //确定小于关系的仿函数
	template<class T>
	struct less
	{
		bool operator() (const T& a, const T& b)
		{
			return a < b;
		}
	};
	//确定大于关系的仿函数
	template<class T>
	struct greater
	{
		bool operator() (const T& a, const T& b)
		{
			return a > b;
		}
	};

	template<class T, class container = vector<T>, class compare = less<T> >
	class priority_queue
	{
	public:
        //向上调整
		void adjust_up(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (_comp(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);

					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}
		
        //向下调整
		void adjust_down(int parent)
		{
			int child = parent * 2 + 1;

			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _comp(_con[child], _con[child + 1]))
					++child;

				if (_comp(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);

					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}

		void push(const T& val)
		{
			_con.push_back(val);
			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.front();
		}

		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}
	private:
		container _con;
		compare _comp;
	};
}

注：博主模拟实现priority_queue时由于使用了运算符[]来进行数据的随机访问，从而维护堆的结构，由于list容器并没有支持[]的重载，因此博主模拟的priority_queue并不适配list。但是标准库的priority_queue实现起来更加复杂，会用make_heap、push_heap和pop_heap等算法函数，因此可以适配list容器。

4. 双端队列 deque

在这里插入图片描述

4.1 概念及结构

双端队列是一个支持从头部或尾部插入删除数据的数据结构

其底层上并不是队列，而是一段段连续的小空间拼接而成，如图所示：

在这里插入图片描述

从上图中我们可以看出：

  • deque由中控器管理着数据，其实际上是一个指针数组，其每个指针指向一段段连续的小空间
  • 缓冲区一段段的小空间存储着真实的数据，当一段小空间存满时就会开辟新的小空间
  • deque的在头部和尾部插入、删除的效率都很高，因为它不需要挪动其余元素
  • deque支持随机访问，但需要根据每一小段的长度进行计算索引所在的位置，效率较低
  • deque在遍历数据时需要不断判断是否到了每一小段的边界，效率较低

4.2 使用

使用时需要包含头文件：

<deque>

其是一个类模板，其具体声明如下：

template < class T, class Alloc = allocator<T> > class deque;

其具体使用和vector类似，但多了push_front()和pop_front()，具体的使用可以查看👉操作手册

4.3 优缺点和适用情况

优点：

  • 和vector相比，它支持数据在头部的插入和删除，而且效率高
  • 和list相比，它的空间利用率更高

缺点：

deque最致命的缺点便是它在随机访问数据时需要通过计算才能得到具体的位置，同时遍历访问数据时需要不断判断是否到了小段区域的边界，效率较低

适用情形：

  • 在实际中，如果要运用到线性结构，一般都会涉及到数据的遍历，因此一般都会使用vector和list
  • 但是在**stack和queue的实现中，由于二者都只会对数据的头部或尾部做处理**，不会对数据进行随机访问和遍历的操作，这就完美的迎合了deque的优点，并避开了其缺点，这也是为什么stack和queue的默认适配容器为deque
  • 而优先队列priority_queue由于要维护堆的结构，需要随机访问数据，因此其默认适配容器为vector

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/375299.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

vue3 watch和watchEffect

vue3 watch和watchEffect

Watch监听ref定义的数据 1.ref数据基本数据类型 let sumref&#xff08;0&#xff09; const stopWatchwatch&#xff08;sum,(new,old)>{ If(new>10){ stopWatch() } console.log(‘sum数据变化了’) }&#xff09;2.ref数据为对象类型,监听的是对象的地址值,若想监听…
阅读更多...
Android：Android Studio安装及环境配置

Android：Android Studio安装及环境配置

1开发环境搭建 Android开发需要使用java的jdk环境，所以需要下载JAVA JDK。 1.1安装配置JAVA JDK Java的JDK下载: https://www.oracle.com/technetwork/java/javase/downloads/index.html 配置java的环境变量： JAVA_HOME:java安装路径。 新增环境变量CLASSPATH 在Path环境…
阅读更多...
如何部署Linux AMH服务器管理面板并结合内网穿透远程访问

如何部署Linux AMH服务器管理面板并结合内网穿透远程访问

文章目录 1. Linux 安装AMH 面板2. 本地访问AMH 面板3. Linux安装Cpolar4. 配置AMH面板公网地址5. 远程访问AMH面板6. 固定AMH面板公网地址 AMH 是一款基于 Linux 系统的服务器管理面板&#xff0c;它提供了一系列的功能&#xff0c;包括网站管理、FTP 管理、数据库管理、DNS 管…
阅读更多...
如何使用第三方API采集电商数据呢？

如何使用第三方API采集电商数据呢？

电商商家最常唠叨的就是店铺运营难做。每日多平台店铺数据统计汇总繁琐耗时&#xff0c;人工效率偏低&#xff0c;且工作内容有限。 特别是眼下“618&#xff0c;双十一&#xff0c;双十二&#xff0c;年底大促”将至&#xff0c;如何提高运营的效率和质量、保证产品及服务的良…
阅读更多...
vue3 使用defineAsyncComponent 动态加载组件

vue3 使用defineAsyncComponent 动态加载组件

问题场景 在项目中使用静态加载组件基本能覆盖80%的场景了&#xff0c;如下图 但是我们在需要 循环生成一些的component 的时候或者在 开发ssr服务端渲染的页面 就会遇到有些组件以静态方式导入就会报错&#xff0c;导致进程失败&#xff0c;那么这时候就需要用到动态组件。那…
阅读更多...
P1808 单词分类

P1808 单词分类

P1808 单词分类 题目描述 Oliver 为了学好英语决定苦背单词&#xff0c;但很快他发现要直接记住杂乱无章的单词非常困难&#xff0c;他决定对单词进行分类。 两个单词可以分为一类当且仅当组成这两个单词的各个字母的数量均相等。 例如 AABAC&#xff0c;它和 CBAAA 就可以…
阅读更多...
Vue中对虚拟DOM的理解

Vue中对虚拟DOM的理解

作为现代前端开发中的主流框架之一&#xff0c;Vue.js是一个非常流行的JavaScript框架&#xff0c;其核心概念之一就是虚拟DOM&#xff08;Virtual DOM&#xff09;。在本篇文章中&#xff0c;我们将深入探讨Vue中虚拟DOM的概念&#xff0c;并讨论为什么它在前端开发中如此重要…
阅读更多...
高清符合要求的SCI图片使用RStudio导出

高清符合要求的SCI图片使用RStudio导出

4.图片格式区别和常识 在计算机中&#xff0c;JPEG&#xff08;发音为jay-peg, IPA&#xff1a;[ˈdʒeɪpɛg]&#xff09;是一种针对照片视频而广泛使用的有损压缩标准方法。这个名称代表Joint Photographic Experts Group&#xff08;联合图像专家小组&#xff09;。此团队创…
阅读更多...
总结：图像生成网络

总结：图像生成网络

1、最新的几款图像生成网络 eCNN 文献&#xff1a;Bahrami A, Karimian A, Fatemizadeh E, et al. A new deep convolutional neural network design with efficient learning capability: Application to CT image synthesis from MRI[J]. Medical physics, 2020, 47(10): 515…
阅读更多...
Linux 分析指定JAVA服务进程所占内存CPU详情

Linux 分析指定JAVA服务进程所占内存CPU详情

1、获取服务进程PID [rootVM-32-26-centos ~]# service be3Service status Application is running as root (UID 0). This is considered insecure. Running [25383]2、获取进程占用详情 [rootVM-32-26-centos ~]# cat /proc/25383/status Name: java Umask: 0022 State: S…
阅读更多...
2024-2-6-复习作业

2024-2-6-复习作业

1> 要求&#xff1a; 源代码&#xff1a; #include <stdio.h> #include <stdlib.h> void output(int arr[],int len) {for(int i0;i<len;i){printf("%d ",arr[i]);}puts(""); } void bubble_sort(int arr[],int len) {for(int i1;i<…
阅读更多...
python的进程，线程、协程

python的进程，线程、协程

python进程的实现 #coding:utf-8 from multiprocessing import Process import timedef run(name):print(%s is running % name)time.sleep(3)print(%s finished his run % name)if __name__ __main__:p Process(targetrun, args(XWenXiang,)) # 创建一个进程对象p.start()…
阅读更多...
88 docker 环境下面 前端A连到后端B + 前端B连到后端A

88 docker 环境下面 前端A连到后端B + 前端B连到后端A

前言 呵呵 最近出现了这样的一个问题, 我们有多个前端服务, 分别连接了对应的后端服务, 前端A -> 后端A, 前端B -> 后端B 但是 最近的时候 却会出现一种情况就是, 有些时候 前端A 连接到了 后端B, 前端B 连接到了 后端A 我们 前端服务使用 nginx 提供前端 html, js…
阅读更多...
字符集JAVA

字符集JAVA

举例&#xff1a; 我们之前在读取文件的时候&#xff0c;文件中都是用英文举例&#xff0c;如果文件内有中文&#xff0c;读取会发生什么 举例&#xff1a;进行读取&#xff0c; //创建字节输入流对象 FileInputStream fisnew FileInputStream("..\\ioDemo\\a.txt"…
阅读更多...
市场复盘总结 20240206

市场复盘总结 20240206

仅用于记录当天的市场情况&#xff0c;用于统计交易策略的适用情况&#xff0c;以便程序回测 短线核心&#xff1a;不参与任何级别的调整&#xff0c;采用龙空龙模式 一支股票 10%的时候可以操作&#xff0c; 90%的时间适合空仓等待 今日梯队&#xff1a; 二进三&#xff1a…
阅读更多...
11_树莓派_树莓派外设板_PWM_彩虹灯

11_树莓派_树莓派外设板_PWM_彩虹灯

目录 1.树莓派外设集成板总体介绍 2.第二部分 PWM 树莓派_树莓派外设板_PWM_RGB彩虹灯 3.代码及实现 1.树莓派外设集成板总体介绍 1&#xff09;前言&#xff1a;这是一块为了验证树莓派【兼容树莓派多个型号】的40pins的外设接口的外接板&#xff0c;告别复杂的面包板外设…
阅读更多...
macOS的设置与常用软件（含IntelliJ IDEA 2023.3.2 Ultimate安装，SIP的关闭与开启）

macOS的设置与常用软件（含IntelliJ IDEA 2023.3.2 Ultimate安装，SIP的关闭与开启）

目录 1 系统设置1.1 触控板1.2 键盘 2 软件篇2.1 [科学上网](https://justmysocks5.net/members/)2.1 [安装Chrome浏览器](https://www.google.cn/chrome/index.html)2.2 [安装utools](https://www.u.tools)2.3 [安装搜狗输入法](https://shurufa.sogou.com/)2.4 [安装snipaste…
阅读更多...
读分布式稳定性建设指南文档

读分布式稳定性建设指南文档

最近还是在做一些和稳定性建设相关的事情&#xff0c;找到一份《分布式稳定性建设指南》文档&#xff0c;摘抄了其中的重点&#xff0c;以便后续回顾方便&#xff0c;一直没上传好资源&#xff0c;我之后再试试&#xff0c;原文内容质量非常高。 大家可以先看一级目录即可&…
阅读更多...
《Git 简易速速上手小册》第4章：Git 与团队合作（2024 最新版）

《Git 简易速速上手小册》第4章：Git 与团队合作（2024 最新版）

文章目录 4.1 协作流程简介4.1.1 基础知识讲解4.1.2 重点案例&#xff1a;为 Python Web 应用添加新功能4.1.3 拓展案例 1&#xff1a;使用 CI/CD 流程自动化测试4.1.4 拓展案例 2&#xff1a;处理 Pull Request 中的反馈 4.2 使用 Pull Requests4.2.1 基础知识讲解4.2.2 重点案…
阅读更多...
《Python 网络爬虫简易速速上手小册》第10章：未来展望与新兴技术（2024 最新版）

《Python 网络爬虫简易速速上手小册》第10章：未来展望与新兴技术（2024 最新版）

文章目录 10.1 机器学习在爬虫中的应用10.1.1 重点基础知识讲解10.1.2 重点案例&#xff1a;使用机器学习进行自动化内容抽取10.1.3 拓展案例 1&#xff1a;利用深度学习识别复杂的网页结构10.1.4 拓展案例 2&#xff1a;机器学习辅助的动态反反爬虫策略 10.2 处理 JavaScript …
阅读更多...
最新文章

Copyright @ 2022~2023