⭐️STL⭐️之deque，stack，queue全解，❤️算法必备❤️＜中＞

秋名山码神

发布于 2022-12-13 14:14:32

2740

发布于 2022-12-13 14:14:32

文章被收录于专栏：码神随笔

文章目录

前言

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;
}