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

C++中stack类和queue类

news 2024/11/16 3:37:04

感谢大佬的光临各位，希望和大家一起进步，望得到你的三连，互三支持，一起进步

数据结构习题_LaNzikinh篮子的博客-CSDN博客

初阶数据结构_LaNzikinh篮子的博客-CSDN博客

收入专栏：C++_LaNzikinh篮子的博客-CSDN博客

其他专栏：c语言基础_LaNzikinh篮子的博客-CSDN博客

个人主页：LaNzikinh-CSDN博客

文章目录

前言
一.容器适配器
二.栈的实现stack
三.队列的实现queue
四.优先级队列priority_queue（）
五.deque（双向队列）
总结

前言

前面我们讲解了C++中List，Vector,和string类的使用和底层逻辑，今天我们来利用前3个类，来搭建栈和队列，在讲解前，我们先来引入一个容器适配器的概念

一.容器适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的，代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL标准库中stack和queue的底层结构中stack和queue默认使用deque。

二.栈的实现stack

接口函数

1.push()将元素val压入stack中

2.top()返回栈顶元素的引用

3.pop()将stack中尾部的元素弹出

4.size()返回stack中元素的个数

5.empty()检测stack是否为空

实现

我们之前说过，栈他是一种适配器，stack只是对其他容器的接口进行了包装，所以我们从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

#include<vector>
namespace yyz
{
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;
};
}

三.队列的实现queue

接口函数

队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

empty：检测队列是否为空

size：返回队列中有效元素的个数

front：返回队头元素的引用

back：返回队尾元素的引用

push_back：在队列尾部入队列

pop_front：在队列头部出队列

实现

标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

#include <list>
namespace yyz
{
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;
};
}

四.优先级队列priority_queue（）

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

empty()：检测容器是否为空

size()：返回容器中有效元素个数

front()：返回容器中第一个元素的引用

push_back()：在容器尾部插入元素

pop_back()：删除容器尾部元素

这里我们的实现是用堆去实现的，堆的本质是数组，所以优先级队列作为适配器，只需要通过对vector进行通用的封装即可

#include<vector>template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};namespace yyz
{// 默认是大堆template<class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{public:void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void AdjustDown(int parent){// 先假设左孩子小size_t child = parent * 2 + 1;Compare com;while (child < _con.size())  // child >= n说明孩子不存在，调整到叶子了{// 找出小的那个孩子//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

五.deque（双向队列）

我们前面说了，栈和队列在STL标准库中stack和queue的底层结构中stack和queue默认使用deque。所以我们这次来看看deque到底是什么

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与 list比较，空间利用率比较高。

在标准库里实现的stack和queue

namespace yyz
{template<class T, class Container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front() const{return _con.front();}const T& back() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

namespace yyz
{// Containerתstacktemplate<class T, class Container = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top() const{//return _con.func();return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}