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

2024-09-09 08:12
文章标签 c++ 实现 介绍 stack queue deque

本文主要是介绍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模拟实现

②queue模拟实现

3.3deque的缺陷


1.stack与queue的实现

1.1stack的实现

在C++入门10——stack与queue的使用中看到:stack的接口函数无非就是这些:

从栈的接口中可以看出,栈实际是一种特殊的vector,因此使用vector完全可以模拟实现stack:

#include<vector>namespace xxk
{template<class T>class stack{public://构造stack(){}//压栈void push(const T& x){_c.push_back(x);}//出栈void pop(){_c.pop_back();}//获取栈顶元素T& top(){return _c.back();}const T& top() const{return _c.back();}//获取有效元素个数size_t size() const{return _c.size();}//检测栈是否为空bool empty() const{return _c.empty();}private:std::vector<T> _c;};
}

 1.2 queue的实现

queue的接口存在这些:

因为queue的接口中存在头删和尾插,因此使用vector来封装效率太低,故可以借助list来模拟实现queue:

#include <list>namespace xxk
{template<class T>class queue{public://构造queue(){}//队尾入队列void push(const T& x){_c.push_back(x);}//队头出队列void pop()const{_c.pop_front();}//获取队尾元素T& back(){return _c.back();}const T& back() const{return _c.back();}//获取队头元素T& front(){return _c.front();}const T& front() const{return _c.front();}//获取有效元素个数size_t size() const{return _c.size();}//判断是否为空bool empty() const{return _c.empty();}private:std::list<T> _c;};
}

2.重温vector、list、stack、queue的介绍

我们在学习vector、list和stack与queue的使用时,对四者分别有这样的介绍:

①Vectors are sequence containers...——Vector是序列容器......;

②Lists are sequence containers...——List是序列容器......;

③Stacks are a type of container adaptor...——Stack是一种容器适配器......;

④queues are a type of container adaptor...——queue是一种容器适配器......;

显然前两者是容器,后两者是容器适配器,这是两种不同的表述。那为什么stack与queue不是容器呢?想要弄明白这个问题,我们就需要从stack与queue的底层结构找答案。

2.1 STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和queue只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque,比如:

关于适配器,我们可以想到平时用的插座的例子:

比如有一个三孔电源,可手机充电时却要用到两孔电源,在没有两孔电源的前提下,我们就可以增加一个电源适配器将三孔电源转换为两孔电源:

 在这里我们就可以简单理解为:三孔电源就是deque容器,电源适配器就是stack和queue容器适配器,手机充电器就是对象:

说到这里,我们就不得不了解一下deque了。

 3.deque的简单介绍

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

(注意:deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组,双端队列底层是一段假想的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了deque的迭代器身上)

3.1为什么选择deque作为stack和queue的底层默认容器

在上面我们已经用vector和list分别实现了stack与queue,既然vector和list就能实现,为什么STL中却要用deque这样一个使用频次不如vector和list的容器呢?

这是因为:

stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以;

queue是先进先出的特殊线性数据结构,只要具有 push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如list。

但是STL中对stack和 queue默认选择deque作为其底层容器,主要是因为:

1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。

2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高。

结合了deque的优点,而完美的避开了其缺陷。

 3.2 STL中对stack与queue的模拟实现

①stack模拟实现

#include<deque>
#include<vector>
#include<list>
namespace xxk
{template<class T, class Con = deque<T>>//template<class T, class Con = vector<T>>//template<class T, class Con = list<T>>class stack{public:stack() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_back(); }T& top() { return _c.back(); }const T& top()const { return _c.back(); }size_t size()const { return _c.size(); }bool empty()const { return _c.empty(); }private:Con _c;};
}

②queue模拟实现

#include<deque>#include <list>
namespace xxk
{template<class T, class Con = deque<T>>//template<class T, class Con = list<T>>class queue{public:queue() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_front(); }T& back() { return _c.back(); }const T& back()const { return _c.back(); }T& front() { return _c.front(); }const T& front()const { return _c.front(); }size_t size()const { return _c.size(); }bool empty()const { return _c.empty(); }private:Con _c;};
}

3.3deque的缺陷

①与vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不 需要搬移大量的元素,因此其效率是必vector高的;

②与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段;

③但是,deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构。

这篇关于C++——stack、queue的实现及deque的介绍的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

redis防止短信恶意调用的实现

《redis防止短信恶意调用的实现》本文主要介绍了在场景登录或注册接口中使用短信验证码时遇到的恶意调用问题,并通过使用Redis分布式锁来解决,具有一定的参考价值,感兴趣的可以了解一下... 目录1.场景2.排查3.解决方案3.1 Redis锁实现3.2 方法调用1.场景登录或注册接口中,使用短信验证码场

Redis 多规则限流和防重复提交方案实现小结

《Redis多规则限流和防重复提交方案实现小结》本文主要介绍了Redis多规则限流和防重复提交方案实现小结,包括使用String结构和Zset结构来记录用户IP的访问次数,具有一定的参考价值,感兴趣... 目录一:使用 String 结构记录固定时间段内某用户 IP 访问某接口的次数二:使用 Zset 进行

Java实现Elasticsearch查询当前索引全部数据的完整代码

《Java实现Elasticsearch查询当前索引全部数据的完整代码》:本文主要介绍如何在Java中实现查询Elasticsearch索引中指定条件下的全部数据,通过设置滚动查询参数(scrol... 目录需求背景通常情况Java 实现查询 Elasticsearch 全部数据写在最后需求背景通常情况下

使用C/C++调用libcurl调试消息的方式

《使用C/C++调用libcurl调试消息的方式》在使用C/C++调用libcurl进行HTTP请求时,有时我们需要查看请求的/应答消息的内容(包括请求头和请求体)以方便调试,libcurl提供了多种... 目录1. libcurl 调试工具简介2. 输出请求消息使用 CURLOPT_VERBOSE使用 C

C++实现获取本机MAC地址与IP地址

《C++实现获取本机MAC地址与IP地址》这篇文章主要为大家详细介绍了C++实现获取本机MAC地址与IP地址的两种方式,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实际工作中,项目上常常需要获取本机的IP地址和MAC地址,在此使用两种方案获取1.MFC中获取IP和MAC地址获取

使用PyQt实现简易文本编辑器

《使用PyQt实现简易文本编辑器》这篇文章主要为大家详细介绍了如何使用PyQt5框架构建一个简单的文本编辑器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录分析主窗口类 (MyWindow)菜单操作语法高亮 (SyntaxHighlighter)运行程序主要组件代码图示分析实现

C/C++通过IP获取局域网网卡MAC地址

《C/C++通过IP获取局域网网卡MAC地址》这篇文章主要为大家详细介绍了C++如何通过Win32API函数SendARP从IP地址获取局域网内网卡的MAC地址,感兴趣的小伙伴可以跟随小编一起学习一下... C/C++通过IP获取局域网网卡MAC地址通过win32 SendARP获取MAC地址代码#i

查询Oracle数据库表是否被锁的实现方式

《查询Oracle数据库表是否被锁的实现方式》本文介绍了查询Oracle数据库表是否被锁的方法,包括查询锁表的会话、人员信息,根据object_id查询表名,以及根据会话ID查询和停止本地进程,同时,... 目录查询oracle数据库表是否被锁1、查询锁表的会话、人员等信息2、根据 object_id查询被

Pandas中多重索引技巧的实现

《Pandas中多重索引技巧的实现》Pandas中的多重索引功能强大,适用于处理多维数据,本文就来介绍一下多重索引技巧,具有一定的参考价值,感兴趣的可以了解一下... 目录1.多重索引概述2.多重索引的基本操作2.1 选择和切片多重索引2.2 交换层级与重设索引3.多重索引的高级操作3.1 多重索引的分组聚

Spring IOC的三种实现方式详解

《SpringIOC的三种实现方式详解》:本文主要介绍SpringIOC的三种实现方式,在Spring框架中,IOC通过依赖注入来实现,而依赖注入主要有三种实现方式,构造器注入、Setter注入... 目录1. 构造器注入(Cons编程tructor Injection)2. Setter注入(Setter