首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【C++】stack and queue的介绍和模拟实现

【C++】stack and queue的介绍和模拟实现

作者头像
六点半就起.
发布于 2024-10-16 07:59:28
发布于 2024-10-16 07:59:28
11800
代码可运行
举报
运行总次数:0
代码可运行
【C++】stack and queue的介绍和模拟实现

一. stack的介绍和模拟实现

1. stack的介绍

  1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。
  2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素从特定容器的尾部(即栈顶)被压入和弹出
  3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作: empty:判空操作 back:获取尾部元素操作 push_back:尾部插入元素操作 pop_back:尾部删除元素操作
  4. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque。

2. stack的常用接口

常用接口及说明:

3 stack的模拟实现

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

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include<vector>
#include<iostream>
using std::cout;
using std::endl;

template <class T>
class stack
{
public:

	stack(){}

	//参数传引:用减少拷贝开销
	//加const:不期望其被修改
	void push(const T& x)
	{
		_c.push_back(x);
	}
	void pop()
	{
		_c.pop_back();
	}
	T& top()//按道理这里也是可以加上const的,但是与const T& top() const未构成函数重载(参数列表完全相同)
		//导致调用不明确
	{
		return _c.back();
	}
	const T& top() const
	{
		return _c.back();
	}
	bool empty() const
	{
		return _c.empty();
	}
	size_t size() const
	{
		return _c.size();
	}

private:
	//未完全展开std
	std::vector<T> _c;
};

int main()
{
	stack<int> s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

	cout << s.size() << endl;

	s.pop();
	cout << s.size() << endl;

	while (!s.empty())
	{
		cout << s.top() << ' ';
		s.pop();
	}

	return 0;
}

二. queue的介绍和使用

1. queue的介绍

  1. 队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
  2. 队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。
  3. 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty:检测队列是否为空 size:返回队列中有效元素的个数 front:返回队头元素的引用 back:返回队尾元素的引用 push_back:在队列尾部入队列 pop_front:在队列头部出队列
  4. 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。

2. queue的常用接口

3 queue的模拟实现

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

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include<list>
#include<iostream>
using std::cout;
using std::endl;

template <class T>
class queue
{
public:

	queue(){}

	void push(const T& x)
	{
		_c.push_back(x);
	}
	void pop()
	{
		_c.pop_front();
	}

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

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

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

	size_t size()
	{
		return _c.size();
	}
private:
	std::list<T> _c;
};
int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

	cout << q.size() << endl;

	cout << q.front() << endl;
	cout << q.back() << endl;


	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;

	cout << q.size() << endl;

	return 0;
}

学习C++必看的网站

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-10-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
C++奇迹之旅:快速上手Stack和Queue的使用与模拟实现
stack官网文档链接:https://legacy.cplusplus.com/reference/stack/stack/?kw=stack
学习起来吧
2024/09/13
1120
C++奇迹之旅:快速上手Stack和Queue的使用与模拟实现
【c++】stack和queue使用 && stack和queue模拟实现
stack的文档介绍:https://cplusplus.com/reference/stack/stack/?kw=stack
用户10925563
2024/06/04
1660
【c++】stack和queue使用 && stack和queue模拟实现
一文了解stack和queue类的实现
优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:默认情况下priority_queue是大堆。
海盗船长
2020/08/27
5730
探密 C++ STL — 深入理解 Stack 和 Queue 的实现与应用
在计算机科学中,数据结构是存储和组织数据的方式,使得我们可以高效地进行数据的访问和修改。在众多数据结构中,stack(栈)和 queue(队列)是两种非常基础且广泛应用的线性数据结构。C++ 提供了非常方便的标准库(STL)来实现 stack 和 queue,并且它们被广泛应用于各种算法和解决方案中。
用户11289931
2024/11/24
2640
【stack】【queue】【priority_queue】【deque】详解
通过观察文档我们不难发现,接口相较于之前的 string、vector 和 list 少了很多。它甚至连拷贝构造和析构都没有自己实现,然而这些都得益于容器适配器的使用。
利刃大大
2023/04/12
1K0
【c++丨STL】stack和queue的使用及模拟实现
本篇文章,博主将介绍STL中两个比较重要的容器适配器:stack(栈)和queue(队列)以及它们的使用方法,并且尝试模拟实现它们。如果你不是很了解栈和队列这两种数据结构,可以参阅这篇文章:
ephemerals__
2024/11/26
2670
【c++丨STL】stack和queue的使用及模拟实现
C++初阶:容器适配器介绍、stack和queue常用接口详解及模拟实现
如你所见,尽管栈适配器的底层容器可能是vector,但它提供了与vector不同的操作接口。栈适配器隐藏了vector的细节,只暴露了栈的相关操作,使得我们可以更方便地使用栈这种数据结构。
是Nero哦
2024/02/19
2740
C++初阶:容器适配器介绍、stack和queue常用接口详解及模拟实现
【C++修炼之路】12. stack && queue类
对于迭代器模式,使我们所熟知的,因为对于vector和list的模拟实现,都涉及到迭代器模式,迭代器模式将内部复杂的数据结构进行了封装,从而在上层使用中更为便捷,即不暴露底层细节,封装后提供统一的方式访问容器;而对于适配器模式:现实生活中,被称为适配器的有电源等待,因此适配器本质是已有的东西,封装转换出你想要的东西。
每天都要进步呀
2023/03/28
2920
【C++修炼之路】12. stack && queue类
【C++】stack & queue
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成我们希望的另外一个接口。
YoungMLet
2024/03/01
1360
【C++】stack & queue
(超级清晰带链接)STL--stack与queue(deque)--C++
从栈的接口中可以看出,栈实际是一种特殊的vector,因此使用vector完全可以模拟实现stack。具体实现如下:
小志biubiu
2025/02/27
1270
(超级清晰带链接)STL--stack与queue(deque)--C++
C++效率掌握之STL库:stack && queue函数全解
本篇是 STL 库专题之 stack 和 queue,本质就是栈和队列,关于该数据结构在初阶数据结构专栏里有详细的解释分析,本篇文章主要针对 stack 和 queue 的使用及拓展进行练习和介绍,建议熟悉好相关的数据结构知识再进行本篇学习
DARLING Zero two
2025/03/25
1480
C++效率掌握之STL库:stack && queue函数全解
C++ STL学习之【容器适配器】
适配器(配接器)是 STL 中的六大组件之一,扮演着轴承、转换器的角色,使得 STL 中组件的使用更为灵活,比如 栈和队列 就是属于适配器而非容器,以及神秘的反向迭代器也属于适配器
北 海
2023/07/01
5720
C++ STL学习之【容器适配器】
【stack和queue的模拟实现】—— 我与C++的不解之缘(十五)
​ stack 和 queue使用起来都非常简单,现在来模拟实现一下,理解其底层的原理。
星辰与你
2024/11/21
1010
【stack和queue的模拟实现】—— 我与C++的不解之缘(十五)
【C++】queue和priority_queue
队列作为容器适配器实现,就是将特定容器封装成其底层容器类,queue提供一组特定的成员函数来访问其元素,元素从队尾入队列,队头出队列
s-little-monster
2024/09/18
2220
【C++】queue和priority_queue
C++初阶-stack/queue/priority_queue的使用和模拟
​ empty():检测容器是否为空 ​ size():返回容器中有效元素个数 ​ front():返回容器中第一个元素的引用 ​ push_back():在容器尾部插入元素 ​ pop_back():删除容器尾部元素
用户9645905
2022/11/30
3490
C++初阶-stack/queue/priority_queue的使用和模拟
【深入探索 C++ STL 容器适配器 stack 和 queue】 —— 数据战场的神秘指挥官,掌控代码节奏的幕后黑手
C++ STL系列学习参考:STL 数据结构与算法__Zwy@的博客-CSDN博客
换一颗红豆
2024/12/20
1430
【深入探索 C++ STL 容器适配器 stack 和 queue】 —— 数据战场的神秘指挥官,掌控代码节奏的幕后黑手
移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——8.stack&&queue&&priority_queue(无习题)
C++ 标准模板库(STL)提供了一系列容器,其中 stack 和 queue 是两种常用的适配器容器。它们基于底层的序列容器(如 vector、deque)实现,分别用于支持栈和队列的操作模型。栈(stack)遵循“后进先出”(LIFO)的原则,而队列(queue)遵循“先进先出”(FIFO)的原则。本文将详细介绍这两种容器的特点、使用方法、实现机制及其应用场景。
hope kc
2024/10/24
2390
【C++】 世界里的 “秩序双雄”:stack 和 queue !把 stack 想象成时光回溯胶囊,新记忆后入先取;queue 仿若忙碌流水线,任务依次稳步推进。
下面,栈为空,返回的就是true就是1,如果有元素入栈,那就是不为空,返回false就是0.
逆向-落叶
2024/12/29
1310
【C++】 世界里的 “秩序双雄”:stack 和 queue !把 stack 想象成时光回溯胶囊,新记忆后入先取;queue 仿若忙碌流水线,任务依次稳步推进。
【C++】STL:栈和队列模拟实现
C++中的stack(栈)和queue(队列)是两种常见的数据结构,用于存储和管理数据。
大耳朵土土垚
2024/06/04
2770
【C++】STL:栈和队列模拟实现
【C++】stack和queue
因为queue的接口中存在头删和尾插,因此使用vector来封装效率太低,故可以借助list来模拟实现queue,具体如下:
zxctscl
2024/04/10
1620
【C++】stack和queue
推荐阅读
相关推荐
C++奇迹之旅:快速上手Stack和Queue的使用与模拟实现
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档