你知道C++多少——栈和队列
🌈个人主页:小新_-
🎈个人座右铭:“成功者不是从不失败的人,而是从不放弃的人!”🎈
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
🏆所属专栏:话说那些与C++的爱恨情仇 欢迎订阅,持续更新中~~~
✨让小新带着你快乐的学习吧~✨
目录
1. stack的介绍和使用
1.1 stack的介绍
翻译
:
1. stack
是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行
元素的插入与提取操作。
2. stack
是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定
的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部
(
即栈顶
)
被压入和弹出。
3. stack
的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下
操作:
empty
:判空操作
back
:获取尾部元素操作
push_back
:尾部插入元素操作
pop_back
:尾部删除元素操作
4.
标准容器
vector
、
deque
、
list
均符合这些需求,默认情况下,如果没有为
stack
指定特定的底层容器, 默认情况下使用deque
。
1.2 stack的使用
1.3 stack的模拟实现
从栈的接口中可以看出,栈实际是一种特殊的
vector
,因此使用
vector
完全可以模拟实现
stack
。
#include<vector>
namespace
bite
{
template
<
class
T
>
class
stack
{
public
:
stack
() {}
void
push
(
const
T
&
x
) {
_c
.
push_back
(
x
);}
void
pop
() {
_c
.
pop_back
();}
T
&
top
() {
return
_c
.
back
();}
const
T
&
top
()
const
{
return
_c
.
back
();}
size_t
size
()
const
{
return
_c
.
size
();}
bool
empty
()
const
{
return
_c
.
empty
();}
private
:
std::vector
<
T
>
_c
};
}
2. queue的介绍和使用
2.1 queue的介绍
翻译:
1.
队列是一种容器适配器,专门用于在
FIFO
上下文
(
先进先出
)
中操作,其中从容器一端插入元素,另一端 提取元素。
2.
队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,
queue
提供一组特定的 成员函数来访问其元素。元素从队尾入队列,从队头出队列。
3.
底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty
:检测队列是否为空
size
:返回队列中有效元素的个数
front
:返回队头元素的引用
back
:返回队尾元素的引用
push_back
:在队列尾部入队列
pop_front
:在队列头部出队列
4.
标准容器类
deque
和
list
满足了这些要求。默认情况下,如果没有为
queue
实例化指定容器类,则使用标准容器deque
2.2 queue的使用
2.3 queue的模拟实现
因为
queue
的接口中存在头删和尾插,因此使用
vector
来封装效率太低,故可以借助
list
来模拟实现
queue
,
具体如下:
#include <list>
namespace
bite
{
template
<
class
T
>
class
queue
{
public
:
queue
() {}
void
push
(
const
T
&
x
) {
_c
.
push_back
(
x
);}
void
pop
() {
_c
.
pop_front
();}
T
&
back
() {
return
_c
.
back
();}
const
T
&
back
()
const
{
return
_c
.
back
();}
T
&
front
() {
return
_c
.
front
();}
const
T
&
front
()
const
{
return
_c
.
front
();}
size_t
size
()
const
{
return
_c
.
size
();}
bool
empty
()
const
{
return
_c
.
empty
();}
private
:
std::list
<
T
>
_c
;
};
}
3. 容器适配器
3.1 什么是适配器
适配器是一种设计模式
(
设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总
结
)
,
该种模式是将一个类的接口转换成客户希望的另外一个接口
。
适配器就是一种设计模式。就比如打仗,国家之间资源的争夺,我们发现打仗是有套路的。并不是人多就一定能赢。比如经典的围魏救赵,这就是兵法。兵法跟我们写代码是一样的。我们的代码需要有可维护性。所以,就有了一些通用的方法,就有了设计模式。如今,我们已经学习了俩种设计模式。
- 适配器
- 迭代器
这些数据结构我们访问十分关心底层细节,他们访问模式可能都不一样。我们通过迭代器(像指针一样的东西),我们就像封装了(通过typdey)iterator来屏蔽底层细节,来访问数据。
这就像支付宝、微信来访问银行的资源,他们屏蔽了对各银行的访问的细节,对用户只展示支付的功能。
4. deque的简单介绍(了解)
4.1 deque的原理介绍
deque(
双端队列
)
:是一种双开口的
"
连续
"
空间的数据结构
,双开口的含义是:可以在头尾两端进行插入和
删除操作,且时间复杂度为
O(1)
,与
vector
比较,头插效率高,不需要搬移元素;与
list
比较,空间利用率比较高。
dequeue的访问
4.2简单了解dequed的底层
5、prority_queue
5.1 priority_queue的介绍
翻译:
1.
优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
2.
此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素
(
优先队列中位于顶部的元素)
。
3.
优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,
queue
提供一组特定的成员函数来访问其元素。元素从特定容器的“
尾部
”
弹出,其称为优先队列的顶部。
4.
底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问,并支持以下操作:
empty()
:检测容器是否为空
size()
:返回容器中有效元素个数
front()
:返回容器中第一个元素的引用
push_back()
:在容器尾部插入元素
pop_back()
:删除容器尾部元素
5.
标准容器类
vector
和
deque
满足这些需求。默认情况下,如果没有为特定的
priority_queue
类实例化指定容器类,则使用vector
。
6.
需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、
push_heap
和
pop_heap
来自动完成此操作。
5.2 priority_queue的使用
优先级队列默认使用
vector
作为其底层存储数据的容器,在
vector
上又使用了堆算法将
vector
中元素构造成
堆的结构,因此
priority_queue
就是堆,所有需要用到堆的位置,都可以考虑使用
priority_queue
。注意:
默认情况下
priority_queue
是大堆
。
5.3简单的模拟实现
最后,感谢大家
原文地址:https://blog.csdn.net/2302_76674204/article/details/142790544
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!