[STL --stack_queue详解]stack、queue,deque,priority_queue

2024-09-02 22:20

本文主要是介绍[STL --stack_queue详解]stack、queue,deque,priority_queue,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

stack

stack介绍

1、stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。
2、stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。

 stack的使用

常用操作:

push尾部插入
pop尾部删除元素
top取栈顶元素
empty判空操作

stack的模拟实现

从stack的接口中,我们发现stack是一种特殊的vector,因此可以用vector完全模拟实现stack;

namespace bit {/*template<class T>class stack {private:T* _a;int _top;int _capacity;};*///可维护性//设计模式//适配器  -- 转换template<class T,class Container =vector<T>>class stack {public:void push(const T&x) {_con.push_back(x);}void pop() {_con.pop_back();}bool empty() {return _con.empty();}const T& top() {return _con.back();}size_t size() {return _con.size();}private:Container _con;};
}

当然用list,deque也可以模拟实现栈;

bit::stack<int, list<int>>s;
bit::stack<int, vector<int>>s;
bit::stack<int, deque<int>>s;

queue

queue介绍

1. 队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
2. 队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。

queue的使用

push队尾插入
pop对头删除
front返回对头元素的引用
back返回队尾元素的引用
empty队列是否为空
size队列元素有效个数

priority_queue 

这里的priority_queue是按照优先级出的,底层实现是堆结构;

这里补充一下要用到的堆的知识点:

堆向上调整:

		void AdjustUp(int child) {int parent = (child - 1)/2;while (child>0) {if (_con[parent]< _con[child]) {swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else {break;}}}

堆向下调整:

void AdjustDown(int parent) {int child = parent * 2 + 1;while (child < _con.size()) {if (child+1<_con.size() && _con[child] < _con[child + 1]) {child++;}if (_con[parent] < _con[child]) {swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else {break;}}}

在模拟实现优先队列前,我们先了解一下仿函数:

 仿函数是什么?

看一段代码:

class Func {
public:
    //operator()就是函数名
    void operator()() {
        cout << "func调用" << endl;
    };
};

调用:

    Func f;
    f();
    f.operator()();

 仿函数(Functor) 是一种行为类似函数的对象,它可以被用作函数并接受参数。在C++中,仿函数通常是重载了函数调用运算符operator()的类对象。通过重载operator(),仿函数可以像函数一样被调用,并且可以保存状态信息。

这样利用仿函数,我们就可以把向上调整和向下调整修改调用仿函数:

这样我们需要大堆或者小堆的话就不要每次都修改<,>了,

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

 只需要:

默认是大堆;

小堆: 

   bit::priority_queue<int, vector<int>, bit::mygreater<int>>q1(v.begin(), v.end());

下面让我们来模拟实现优先队列:

namespace bit {//仿函数template<class T>class myless {public:bool operator()(const T& x, const T& y) {return x < y;}};//仿函数template<class T>class mygreater {public:bool operator()(const T& x, const T& y) {return x > y;}};template<class T,class Container = vector<T>,class Compare=myless<T>>class priority_queue {public:template <class InputIterator>priority_queue(InputIterator first, InputIterator last) {while (first != last) {_con.push_back(*first);first++;}//建堆(从倒数第一个非叶子节点开始向下调整)for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) {AdjustDown(i);}}void AdjustUp(int child) {Compare comfunc;int parent = (child - 1)/2;while (child>0) {if (comfunc(_con[parent], _con[child])) {swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else {break;}}}void AdjustDown(int parent) {Compare comfunc;int child = parent * 2 + 1;while (child < _con.size()) {if (child+1<_con.size() && comfunc(_con[child] , _con[child + 1])) {child++;}if (comfunc(_con[parent] , _con[child])) {swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else {break;}}}void push(const T& x) {_con.push_back(x);AdjustUp(_con.size()-1);}void pop() {swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top() {return _con[0];}bool empty() {return _con.empty();}size_t size() {return _con.size();}private:Container _con;//底层核心};
}

queue的模拟实现

由于queue是一个双端操作,这里最后不要使用vector在模拟实现,如果用的话反而会比较麻烦。

可以选择list和deque来模拟实现;

    bit::queue<int, list<int>>s;
    bit::stack<int, deque<int>>s;

namespace bit {template<class T,class Container = list<T>>class queue {public:void push(const T& x) {_con.push_back(x);}void pop() {_con.pop_front();}bool empty() {return _con.empty();}size_t size() {return _con.size();}const T&top() {return _con.front();}private:Container _con;};
}

deque简单介绍

deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。

简单的说,deque在功能上就是vector和list的结合。

deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组。
 

这篇关于[STL --stack_queue详解]stack、queue,deque,priority_queue的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1131226

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

K8S(Kubernetes)开源的容器编排平台安装步骤详解

K8S(Kubernetes)是一个开源的容器编排平台,用于自动化部署、扩展和管理容器化应用程序。以下是K8S容器编排平台的安装步骤、使用方式及特点的概述: 安装步骤: 安装Docker:K8S需要基于Docker来运行容器化应用程序。首先要在所有节点上安装Docker引擎。 安装Kubernetes Master:在集群中选择一台主机作为Master节点,安装K8S的控制平面组件,如AP

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现

嵌入式Openharmony系统构建与启动详解

大家好,今天主要给大家分享一下,如何构建Openharmony子系统以及系统的启动过程分解。 第一:OpenHarmony系统构建      首先熟悉一下,构建系统是一种自动化处理工具的集合,通过将源代码文件进行一系列处理,最终生成和用户可以使用的目标文件。这里的目标文件包括静态链接库文件、动态链接库文件、可执行文件、脚本文件、配置文件等。      我们在编写hellowor

LabVIEW FIFO详解

在LabVIEW的FPGA开发中,FIFO(先入先出队列)是常用的数据传输机制。通过配置FIFO的属性,工程师可以在FPGA和主机之间,或不同FPGA VIs之间进行高效的数据传输。根据具体需求,FIFO有多种类型与实现方式,包括目标范围内FIFO(Target-Scoped)、DMA FIFO以及点对点流(Peer-to-Peer)。 FIFO类型 **目标范围FIFO(Target-Sc

019、JOptionPane类的常用静态方法详解

目录 JOptionPane类的常用静态方法详解 1. showInputDialog()方法 1.1基本用法 1.2带有默认值的输入框 1.3带有选项的输入对话框 1.4自定义图标的输入对话框 2. showConfirmDialog()方法 2.1基本用法 2.2自定义按钮和图标 2.3带有自定义组件的确认对话框 3. showMessageDialog()方法 3.1

脏页的标记方式详解

脏页的标记方式 一、引言 在数据库系统中,脏页是指那些被修改过但还未写入磁盘的数据页。为了有效地管理这些脏页并确保数据的一致性,数据库需要对脏页进行标记。了解脏页的标记方式对于理解数据库的内部工作机制和优化性能至关重要。 二、脏页产生的过程 当数据库中的数据被修改时,这些修改首先会在内存中的缓冲池(Buffer Pool)中进行。例如,执行一条 UPDATE 语句修改了某一行数据,对应的缓

ActiveMQ—Queue与Topic区别

Queue与Topic区别 转自:http://blog.csdn.net/qq_21033663/article/details/52458305 队列(Queue)和主题(Topic)是JMS支持的两种消息传递模型:         1、点对点(point-to-point,简称PTP)Queue消息传递模型:         通过该消息传递模型,一个应用程序(即消息生产者)可以