stack和queue的区别,stack queue
文章前言：栈的介绍及1.1栈的使用，1.2栈的使用，1.3栈的模拟，队列的介绍及2.1队列的使用，2.3队列的模拟，3适配器4.1的实现什么是适配器4.3的简要介绍(理解)？四。为什么选择deque作为堆栈和队列的底层默认容器？前言：距离上一篇博客已经过去20天了，剩下的暑假也在今天结束。相信很多朋友和我一样，还在家里上网络课，今天和大家聊聊C中的栈和队列，还有德格。
还有一个给大家的建议。C中的容器建议根据文档学习。很多东西是大脑记不住的。C的附加文件如下
c文档
打开后建议进入旧版本，这样更容易找到我们需要的东西。
就在箱子里找
开始发短信
1.栈的介绍和使用1.1栈的介绍。堆栈文档介绍
1.stack是作为容器适配器实现的，容器适配器是封装特定类作为其底层的容器，并提供一组特定的
成员函数来访问它的元素，特定的类作为它的底层，特定于元素的容器的尾部(即堆栈的顶部)被推入和弹出。
2.2.stack的底层容器可以是任何标准的容器类模板或其他特定的容器类。
3.Stack的底层容器可以是任何标准的容器类模板或一些其他特定的容器类。
1.2栈的使用功能描述
界面描述
堆栈()
构造一个空堆栈。
空()
检查堆栈是否为空。
大小()
返回堆栈中元素的数量。
顶部()
返回对堆栈顶部元素的引用。
推送()
val元素被压入堆栈。
流行()
弹出堆栈中的尾部元素。
1.3堆栈的模拟实现从堆栈的接口可以看出，堆栈实际上是一种特殊的向量，所以完全可以利用向量来模拟实现堆栈。
命名空间hulu
{
//模板类T，类容器=向量T
//模板类T，类容器=列表T
模板类T，类容器=队列T
类堆栈
{
公共：
无效推送(常数x)
{
_ con . push _ back(x)；
}
无效弹出()
{
_ con . pop _ back()；
}
t顶部()
{
return _ con . back()；
}
size_t size()
{
return _ con . size()；
}
布尔空()
{
return _ con . empty()；
}
私人：
Container _ con
};
}因为容器适配器使用内置的类型向量，所以不需要初始化stack，实现构造函数，编译器会帮你实现。
二、队列的引入和使用2.1队列的队列的引入。
Queue是一种容器适配器，专门用于FIFO操作，元素从容器的一端插入，从另一端取出。作为队列适配器的实现，容器适配器封装了一个特定的容器类作为它的底层容器类，队列提供了一组特定的
函数来访问其元素。元素从队列的末尾进入队列，从队列的开头退出队列。底部容器可以是标准容器类模板或其他专门设计的容器类之一。底层容器应该至少支持以下操作
品牌：
Empty:检查队列是否为空。
Size:返回队列中有效元素的数量。
Front:返回对队列头元素的引用。
返回尾部元素的引用。
Push_back:队列末尾的队列
Pop_front:在队列头部退出队列的标准容器类deque和list满足这些要求。默认情况下，如果没有为队列实例化指定容器类，则使用标志。
准集装箱码头。
2.2队列使用功能的声明
界面描述
队列()
构建一个空队列。
空()
检查队列是否为空，如果是，返回真，否则，返回假。
大小()
返回队列中有效元素的数量。
正面()
返回对队列头元素的引用。
后退()
返回对尾部元素的引用。
推送()
将元素val排在队列的末尾。
流行()
将队列头元素出队。
2.3队列的模拟实现因为队列的接口存在头删除和尾插入，用向量来封装效率太低，所以可以用list来模拟队列的实现。
如下所示：
命名空间hulu
{
//列表
模板类T，类容器=列表T
类别队列
{
公共：
无效推送(常数x)
{
_ con . push _ back(x)；
}
无效弹出()
{
_ con . pop _ front()；
}
t前部()
{
return _ con . front()；
}
t形背部()
{
return _ con . back()；
}
size_t size()
{
return _ con . size()；
}
布尔空()
{
return _ con . empty()；
}
私人：
Container _ con
};
} 3.容器适配器4.1什么是适配器adapter？适配器是一种设计模式(设计模式是一套被反复使用、被大多数人所知、被分类编目的代码设计经验。
Knot)，就是把一个类的接口转换成客户想要的另一个接口。
让我们首先看看这个库用什么来实现堆栈和队列容器适配器。
可以看出，库对栈和队列的实现使用了deque，这是一个deque。
4.3德雀(理解)德雀(deque)简介：是一种双开的‘连续’空间的数据结构。双开的意思是：可以插在头尾两端。
删除，时间复杂度为O(1)。与vector相比，第一次插入效率高，不需要移动元素；与列表相比，空间利用率
更高。
但并不是真正意义上的连续空间，而是由指针连接的小块空间组成的空间。
实际上，deque类似于一个动态的二维空间。
德雀的底部是一个假想的连续空间，但实际上是分段连续的。为了保持它的“整体连续性”和随机存取的假象，它下降了
在deque的迭代器上，deque的迭代器设计更加复杂，如下图所示：
4.为什么选择deque作为堆栈和队列的底层默认容器？stack是一种特殊的线性数据结构，有后进先出，所以只要它有一个带push_back()和pop_back()操作的线性结构，就可以
作为栈的底层容器，比如vector和list队列是一种特殊的线性数据结构，只要它具有FIFO
push_back和pop_front操作的线性结构可以作为队列的底层容器，比如list。但是在STL中，堆栈和
默认情况下，Queue选择deque作为它的底层容器，这主要是因为：
1.stack和queue不需要遍历，所以本身没有迭代器，只有容器一端或两端的操作数。
2 .元素增长中可能需要扩展stack和deque，但deque不需要。容量满了，继续打开一个空头空间就不错了。
结合了德雀的优点，却完美的避免了它的缺点。
(本章结束)
版权归作者所有：原创作品来自博主，转载授权请联系作者，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。