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

数据结构习题_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。

<code>#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进行通用的封装即可   

​            

<code>#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

<code>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תstack

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

};

}

---

总结

这次讲解了C++中栈和队列的使用，下次对模板在做一点补充