⭐️STL⭐️之deque,stack,queue全解,❤️算法必备❤️<中>

举报
秋名山码民 发表于 2022/03/12 12:27:16 2022/03/12
【摘要】 @TOC 前言STL有点多,码神分为了,上中下,三个部分来讲解😁,接下来我们看中,此类分为三个小部分:👍deque👍stack👍queue 一、deque对于deque容器来说,一般将其称之为双端数组,与上章的vector不同,vector是只允许在尾端插入,而deque是双端插入,如果说的浪漫一点,就是双向奔赴,但是,vector的访问速度比deque快,而vector头部的插入和...

@TOC


前言

STL有点多,码神分为了,上中下,三个部分来讲解😁,接下来我们看中,
此类分为三个小部分:
👍deque
👍stack
👍queue

一、deque

对于deque容器来说,一般将其称之为双端数组,与上章的vector不同,vector是只允许在尾端插入,而deque是双端插入,如果说的浪漫一点,就是双向奔赴,但是,vector的访问速度比deque快,而vector头部的插入和删除比deque慢

用图来表示deque就是这样的
在这里插入图片描述
从上图我们,不难看出相较于vector,多了push_front, pop_front,front,back……等函数

工作原理如下:
在这里插入图片描述
可以看出deque内部有一个中控区,维护每段缓冲区的内容,缓冲区中存放真实的数据,中控区维护的是每个缓冲区的地址,使得deque像一块连续的空间😂
同样deque的迭代器也是支持随机访问的,
实际使用起来也和vector大同小异,我们来看代码

#include<deque>
#include<iostream>
using namespace std;
void print(const deque<int> &d)//只读的迭代器
{
	for (deque<int> ::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
void test01()
{
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	print(d1);
}
int main()
{
	test01();
	return 0;
}

赋值我就不一一写了,可以参考上一个博客,
也与vector类似,,有重载“ = ”,operator =,
例如:d2=d1
d1.assign(d2.begin(),d2.end())
d3.assign(10,100)

依据vector的程序,接下来应该是deque的大小操作
比如:
💕deque的empty判断是否为空,还有size返回大小,resize重新定义大小
区别就是:没有容量,只有大小,这点我在vector中也介绍过了,就是没有
capacity
然后就是插入和删除操作
这里由于deque是双向操作,所以比vector多了个pop的操作,所以我就用代码,单独写一下pop的操作

#include<deque>
#include<iostream>
using namespace std;
void print(const deque<int> &d)//只读的迭代器
{
	for (deque<int> ::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
void test01()
{
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	print(d1);
	d1.pop_back();//尾删
	print(d1);
	d1.pop_front();//头删
	print(d1);
}
int main()
{
	test01();
	return 0;
}

访问元素,和vector一样吧,
d1.at(0),d1【i】,所以说除了迭代器外,还有这俩种方法👍

再来说一个algorithm中的算法,sort排序算法,还是用deque讲,开始吧

#include<algorithm>
sort(d.begin(),d.end());//默认从小到大
//可以使用倒序来,变为从大到小

stack栈

不知道大家有没有看过的数据结构,首先栈是一个先入后出的数据类型,进栈,和出栈,分别为push,和pop
在这里插入图片描述
由于栈有栈顶,所以又多了个top,整体下来就先入后出
注意:栈不允许有遍历的行为,只有栈顶元素才能被外界访问到

  • size:记录大小,可以在入栈的操作记录
  • empty:记录是否为空,为空返回真
  • push:栈顶加入
  • top:弹出

简单来实现一下,光说不练假把式

#include<iostream>
#include<stack>
using namespace std;
void test01()
{
	stack<int> s;
	s.push(10);
	s.push(20);
	s.push(30);
	while (!s.empty())
	{
		s.pop();
	}
	cout << s.size();

}
int main()
{
	test01();
	return 0;
}

请添加图片描述

还是和我在数据结构中所讲,栈更像一个弹夹,入子弹,和打出子弹
栈大概就这么多了,欢迎关注!

queue

队列,还有映像没有了,可以看看码神爆肝5w字数据结构,区别于栈,队列是一个先进先出的数据结构
请添加图片描述
由于队列,只有队头和对尾能被外界访问,所以它也不允许遍历(不允许改动的记录),大体函数有一下这些:

  • push—入队
  • pop—出队
  • size—大小
  • back—返回最后一个元素
  • front—返回第一个元素
  • empty—判断是否为空,为空返回真

简单实现一下,这些接口:

#include<queue>
#include<iostream>
using namespace std;
//不允许遍历
void test01()
{
	queue<int> q;
	q.push(10);
	q.push(20);
	cout << q.front ()<<" ";
	cout << q.back() << " ";

	q.pop();
	while (!q.empty())
	{
		cout << q.front();
		break;
		//不然是死循环
	}
		
}
int main()
{
	test01();
	return 0;
}

总结

大概中篇就这么多吧,记住有的容器是不允许遍历的,stack,queue等,还是老样子,原创不易,欢迎三连,感谢各位!

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。