C++stack与queue模拟实现详解

目录
  • stack与queue模拟实现
  • stack
  • queue
  • 为什么选择deque作为stack和queue的底层默认容器
  • 总结

stack与queue模拟实现

在stl中，stack(栈)与queue(队列)都是容器适配器。

什么是容器适配器呢？

适配器（adaptor）是标准库中通用的概念，包括容器适配器、迭代器适配器和函数适配器。本质上，适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。简单来说其实就是利用现有的容器来适配出来的新容器。

stack

在标准库中，stack默认使用的是deque容器来进行适配的。
当然这里也可以适配vector容器和list容器。

namespace ZJ
{
	//template<class T,class Container= ZJ::list<T>>
	//template<class T,class Container= ZJ::vector<T>>
	template<class T,class Container= ZJ::deque<T>>
	class stack
	{
	public:
		void pop()
		{
			m_stack.pop_back();
		}
		void push(const T&val)
		{
			m_stack.push_back(val);
		}
		size_t size()	const
		{
			return static_cast<size_t>(m_stack.size());
		}
		T& top()
		{
			return m_stack.back();
		}
		const T& top() const
		{
			return m_stack.back();
		}
		bool empty()	const
		{
			return m_stack.empty();
		}
	private:
		Container m_stack;
	};
}

queue

与stack一样，在标准库中默认使用的是deque容器来进行适配的。

namespace ZJ
{
	template<class T,class Container=ZJ::deque<T>>
	class queue
	{
	public:
		void pop()
		{
			m_queue.pop_front();
		}
		void push(const T& val)
		{
			m_queue.push_back(val);
		}
		size_t size()	const
		{
			return static_cast<size_t>(m_queue.size());
		}
		T& back()
		{
			return m_queue.back();
		}
		const T& back() const
		{
			return m_queue.back();
		}
		T& front()
		{
			return m_queue.front();
		}
		const T& front() const
		{
			return m_queue.front();
		}
		bool empty()	const
		{
			return m_queue.empty();
		}
	private:
		Container m_queue;
	};
}

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

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有一个致命缺陷：不适合遍历，特别是在遍历或者排序时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下。

总结

本片文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • c++中stack、queue和vector的基本操作示例

    前言 这几天在接触搜索的题目,用bfs时基本都用到队列,就顺便学习了数据结构的栈.队列.本文将详细给大家介绍关于c++中stack.queue和vector的基本操作,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. stack 的基本操作有: 入栈,如例:s.push(x); 出栈,如例:s.pop();注意,出栈操作只是删除栈顶元素,并不返回该元素. 访问栈顶,如例:s.top() 判断栈空,如例:s.empty() ,当栈空时,返回true. 访问栈中的元素个数,如例:s.

  • C++ STL容器stack和queue详解

    stack是一个比较简单的容器,它的使用也很简单,stack是LIFO容器,就是后进先出,最后添加进去的元素,第一个取出来 stack初始化 std::stack<int> first; std::stack<int> second(first); std::stack<int, std;:vector<int>> third; //使用vector初始化stack ### stack常用方法### empty();//判断是否为空 push(Elem e)

  • C++中stack、queue、vector的用法详解

    C++中stack、queue、vector的用法详解

    一.栈(stack) 引入头文件 #include<stack> 常用的方法 empty() 堆栈为空则返回真 pop() 移除栈顶元素 push() 在栈顶增加元素 size() 返回栈中元素数目 top() 返回栈顶元素 3.实例代码 #include<iostream> #include<stack> using namespace std; int main(){ //创建栈 s stack<int> s; //将元素压入栈 for(int i=0;

  • C++stack与queue模拟实现详解

    目录 stack与queue模拟实现 stack queue 为什么选择deque作为stack和queue的底层默认容器 总结 stack与queue模拟实现 在stl中,stack(栈)与queue(队列)都是容器适配器. 什么是容器适配器呢? 适配器(adaptor)是标准库中通用的概念,包括容器适配器.迭代器适配器和函数适配器.本质上,适配器是使一事物的行为类似于另一事物的行为的一种机制.容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现.简单来说其实就是利用现有的容

  • Java集合框架之Stack Queue Deque使用详解刨析

    目录 1. Stack 1.1 介绍 1.2 常见方法 2. Queue 2.1 介绍 2.2 常见方法 3. Deque 3.1 介绍 3.2 常见方法 1. Stack 1.1 介绍 Stack 栈是 Vector 的一个子类,它实现了一个标准的后进先出的栈.它的底层是一个数组. 堆栈只定义了默认构造函数,用来创建一个空栈.堆栈除了包括由 Vector 定义的所有方法,也定义了自己的一些方法. 1.2 常见方法 方法 描述 E push(E item) 压栈 E pop() 出栈 E pee

  • C语言常用库函数的使用及模拟实现详解例举

    目录 1.strlen 1.计数法 2.递归法 3.指针减指针 2.strcpy 3.strcmp 4.strcat 5.strstr 6.strtok 7.字符分类函数 8.memcpy&memmove 9.memcmp 经历了C语言基础篇的学习,让我们来简单了解几个C语言的库函数! 1.strlen 字符串已经 '\0' 作为结束标志,strlen函数返回的是在字符串中 '\0' 前面出现的字符个数(不包 含 '\0' ). 函数的模拟实现 1.计数法 int my_strlen(dest)

  • C++Stack栈类模版实例详解

    C++Stack栈类模版实例详解

    目录 1.栈的介绍 2.栈实现 3.代码测试 总结 1.栈的介绍 栈的实现方式分为3种 基于静态数组实现,内部预设一个很大的数组对象, 实现简单,缺点是空间受限. 基于动态数组实现,内部预设一个容量值,然后分配一段内存空间数组,如果入栈大于默认容量值时,则再次扩大分配新的内存数组,并将旧数组拷贝至新数组及释放旧数组. 基于双向循环链表实现 栈的函数需要实现如下所示: T pop() : 出栈并返回栈顶元素 void  push(const T &t) : 入栈 const T & top(

  • Python进程间通信 multiProcessing Queue队列实现详解

    一.进程间通信 IPC(Inter-Process Communication) IPC机制:实现进程之间通讯 管道:pipe 基于共享的内存空间 队列:pipe+锁的概念--->queue 二.队列(Queue) 2.1 概念-----multiProcess.Queue 创建共享的进程队列,Queue是多进程安全的队列,可以使用Queue实现多进程之间的数据传递. Queue([maxsize])创建共享的进程队列. 参数 :maxsize是队列中允许的最大项数.如果省略此参数,则无大小限制

  • python中利用队列asyncio.Queue进行通讯详解

    前言 本文主要给大家介绍了关于python用队列asyncio.Queue通讯的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. asyncio.Queue与其它队列是一样的,都是先进先出,它是为协程定义的 例子如下: import asyncio async def consumer(n, q): print('consumer {}: starting'.format(n)) while True: print('consumer {}: waiting for i

  • Java 队列 Queue 用法实例详解

    队列是一种特殊的线性表,它只允许在表的前端进行删除操作,而在表的后端进行插入操作. LinkedList类实现了Queue接口,因此我们可以把LinkedList当成Queue来用. 以下实例演示了队列(Queue)的用法: /* author by w3cschool.cc Main.java */ import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(S

  • Golang继承模拟实例详解

    本文实例讲述了Golang继承模拟实现方法.分享给大家供大家参考,具体如下: 问题由一个需求引起: web的controller,希望创建一个基类,然后在子类的controller中定义action方法,基类有一个run函数能根据字符串自动找到子类的action方法. 如何解决呢? -- 用继承 示例分析继承 首先这个需求是很普遍的,由于脑中有继承概念,所以想当然地以为这个很容易实现: 复制代码 代码如下: package main import(     "reflect" ) ty

  • java 多线程交通信号灯模拟过程详解

    java 多线程交通信号灯模拟过程详解

    这学期我们java课程的课程设计项目----交通信号灯的线程设计 实验目的:多线程设计,同步机制 题意 设计一个交通信号灯类: 变量:位置.颜色(红.黄.绿).显示时间(秒). 方法:切换信号灯. 创建并启动两个线程(东西向.南北向)同时运行. 实验要求 设计线程. 设计路口信号灯示意图界面. 进一步将每个方向的信号灯分成3种车道灯:左转.直行和右转. 根据车流量进行时间的模糊控制. 在课程设计的开始并没有仔细看老师的要求,只知道是交通信号灯.然后就开始各种找资料,百度,网上大量的关于红绿灯的设

  • python进程间通信Queue工作过程详解

    Process之间有时需要通信,操作系统提供了很多机制来实现进程间的通信. 1. Queue的使用 可以使用multiprocessing模块的Queue实现多进程之间的数据传递,Queue本身是一个消息列队程序,首先用一个小实例来演示一下Queue的工作原理: import multiprocessing q = multiprocessing.Queue(3) # 初始化的Queue对象,最多能put三条消息 q.put("消息1") q.put("消息2")

随机推荐