当前位置：首页 > article >正文

你知道C++多少——栈和队列

article 2024/10/11 13:46:15

🌈个人主页：小新_-

🎈个人座右铭：“成功者不是从不失败的人，而是从不放弃的人！”🎈

🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝

🏆所属专栏：话说那些与C++的爱恨情仇 欢迎订阅，持续更新中~~~

✨让小新带着你快乐的学习吧~✨

1. stack的介绍和使用

1.1 stack的介绍

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的介绍

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的介绍

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 是大堆 。