首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
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 删除。

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
2020年终总结:美团+滴滴+网易+拼多多Java后端面经总结,最终上岸网易!
今年秋招较以往是要难了一些,但也不是那种遥不可及的地步。对于准备充分的人来说总是offer不断。我接触Java也不到1年,但是只要好好的准备,两个月完全够应付大部分的公司了。希望看到这篇文章的同学能稳住心态,踏实刷题。坚持几个月定能收获自己满意的offer。
Java程序猿
2021/01/04
1.1K0
2020年终总结:美团+滴滴+网易+拼多多Java后端面经总结,最终上岸网易!
敖丙读者字节、滴滴面经(已拿offer)
本期是读者投稿,他跟他聊的时候发现这个小伙子挺有意思的,是个校招生,全靠白嫖B站和我们一群号主的面试题复习,拿了挺多offer的,大家看看他的准备过程,校招的朋友可以看看他的学习路线。
敖丙
2020/12/08
1.4K0
敖丙读者字节、滴滴面经(已拿offer)
记录年前Java岗整个历程(附字节,阿里,百度,网易,美团等面经)
211本,985硕,女生,方向都是Java开发或者后台开发。   目前拿到了字节,百度,网易(白菜价,已拒),美团,小米的意向书,等最终结果通知的是华泰(已收到体检通知),招行信用卡,阿里   招银(资料审查中),网易互娱(二面没去),浦发(没去体检),农行(面试通过,没去笔试),腾讯(两次被捞都是一面挂,第三次还是深圳拒绝了面试),微软(笔试完),银联(笔试完),微博(拒绝了现场面试)   还有各种笔试挂的(流利说,爱奇艺,小红书,B站),后续拒绝了很多面试,再也没有精力再去了,持续躺尸中.... 实习
Java码农那些事
2020/02/15
1K0
腾讯后端面经(含答案)
经过半年的沉淀,加上对MySQL,redis和分布式这块的补齐,终于开始重拾面试信心,再次出征。
好好学java
2019/05/06
2K0
2020 字节跳动后端面经分享!已拿 offer!
本人是底层 211 本科,现在大三,无科研经历,但是有一些项目经历,在国内监控行业某头部企业做过一段时间的实习。想着投一下字节,可以积累一下面试经验和为春招做准备.投了简历之后,过了一段时间,HR 就打电话跟我约时间,在年后进行远程面。
Guide哥
2020/05/07
2.2K0
最新BAT的实习面经
6. 数据库:事务的概念,索引,B+树讲了一下。可能我回答的太不规范,然后也说了自己忘了数据库的知识了,于是就没往下问
好好学java
2019/05/06
8580
蚂蚁金服Java研发三面(电面+现场面),终获offer分享我的面经感悟
一份初得蚂蚁面试机会(本人非985/211,蚂蚁真的不是很在乎学历!!!),有了一次社招机会,前后经历三关,受益匪浅,在此与各位朋友分享经历与心得。
烂猪皮
2021/06/09
1.1K0
蚂蚁金服Java研发三面(电面+现场面),终获offer分享我的面经感悟
985硕士毕业的妹子,三面蚂蚁美团Java后端【面经分享】
本人妹子,985硕士,211本科,专业都是软件工程,一直投的是java后台开发,只投过一次网易的测试,技术不是大牛,但是比较努力。实验室没有项目,so项目经验是0,在去年这个时候看到实验室师兄找工作的艰难,因此开始复习的时间比较早。最开始先看的java基础,后面就看框架视频,都是在网上找的免费的。《剑指offer》刷了一遍,有些重点的题一定要滚瓜烂熟。关注公众号:麒麟改bug。
Java程序猿
2020/12/29
7270
985硕士毕业的妹子,三面蚂蚁美团Java后端【面经分享】
【面经】美团暑期实习Java一面二面
其他的一些不太记得了 美团的面试体验还是非常好的,让人觉得面试官对每个候选人都很重视,有不会的面试官也会引导你
后端码匠
2021/05/10
6620
对线面试官 | 字节跳动一面
面试官:看你简历上写了熟悉集合相关内容,你了解HashMap吗?讲一下HashMap的put方法?
程序员大彬
2022/07/08
4220
Java程序员秋招面经大合集(BAT美团网易小米华为中兴等)
1, 自我介绍 2, 项目介绍 3, 项目架构 4, 项目难点 5, Synchronize关键字为什么jdk1.5后效率提高了 6, 线程池的使用时的注意事项 7, Spring中autowire和resourse关键字的区别 8, Hashmap的原理 9, Hashmap的大小为什么指定为2的幂次 10, 讲一下线程状态转移图 11, 消息队列了解么 12, 分布式了解么
desperate633
2018/08/23
7260
多篇面经集合,你不容错过的干货!
  5. 写一个单例模式,答主写的是双检查锁单例,问了为什么用 Volatile,synchronize 移到 方法最外面会怎么样?
牛客网
2018/07/24
1.1K0
多篇面经集合,你不容错过的干货!
字节跳动后端实习面经,一面+二面
本来约的今天下午2点一面,一面完面试官让我直接等二面,然后就连着面了,二面完面试官又让我等着直接三面,然后等了一会儿说三面面试官不在,下次约时间。。。。看来是打算三面连着来,真的难顶
烂猪皮
2020/12/29
1.3K0
字节跳动后端实习面经,一面+二面
三面字节跳动后面试总结-(研发端面经)
算法题:binary tree 每层找最大值:level order traversal(BFS)
烂猪皮
2020/11/10
7930
三面字节跳动后面试总结-(研发端面经)
社招两年半10个公司28轮面试面经
还有一个点是,看书的时候可以尝试记一下笔记,这样效率会高一些,不至于看完就忘记了。
CoderW
2022/07/13
9610
社招两年半10个公司28轮面试面经
江浙沪的java春招实习综合面经
最近也是每天刷牛客看了很多大家的帖子,自己结束春招,把之前的记录分享给大家把。 投递公司 搜狐焦点 爱奇艺散招,快手,金陵科技, 地平线, 有赞,YuxiSoft,搜狐,科大讯飞,腾讯微信,趋势,酷家乐,旷世Face++,携程,爱奇艺内推,去哪儿,阿里,京东,美团点评,网易, 百度,ebay , 今日头条,追一科技,小米 , 招商银行信用卡中心,腾讯,,途牛,58同城,旷世Face++,拼多多,,远景能源,CVTE,华为,微众银行 做一个走到的状态汇总吧: 没有消息: 搜狐焦点,快手,科大讯飞,腾讯微信
牛客网
2018/05/30
1K0
社招一年半面经分享(含阿里美团头条京东滴滴)
最近一段时间面试了几家互联网公司,陆续通过了阿里、头条、美团,滴滴,京东的面试,基本上面试的公司都通过了,所以在这里想分享一些自己面试的经验给大家,希望能帮助大家拿到心仪的offer
捡田螺的小男孩
2021/04/23
2K0
JAVA面试解析(有赞一面)
本文的题目出自博客 http://www.54tianzhisheng.cn/2018/07/12/youzan/ 但是作者没有给出答案,博主斗胆来制作答案版。
乔戈里
2019/09/03
7170
JAVA面试解析(有赞一面)
快手Java开发面经(2技术面)
如果你要做一件事,请不要炫耀,也不要宣扬,只管安安静静的去做。因为那是你自己的事,别人不知道你的情况,也不可能帮你去实现。千万不要因为虚荣心而炫耀。也不要因为别人的一句评价而放弃自己的梦想。值不值,时间是最好的证明。
牛客网
2018/10/11
2.1K0
我的奇葩面试经历分享:喊价25K,HR 却给了30K
本文是楼主前两个月 N 家公司的面试经历,总结复盘了面试现场,个人认为干货还是不少,在此和大家分享。
美的让人心动
2019/06/21
9640
我的奇葩面试经历分享:喊价25K,HR 却给了30K
推荐阅读
相关推荐
2020年终总结:美团+滴滴+网易+拼多多Java后端面经总结,最终上岸网易!
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档