1.stack

https://cplusplus.com/reference/stack/stack/?kw=stack

可通过模板使用其他类来建立stack（如vector，list）

<code>#include<vector>

namespace zone

{

template<class T,class container> //两个模板参数

class stack

{

public:

void push(const T& x)

{

it.push_back(x); //使用it的pushback

}

void pop()

{

it.pop_back(); //使用it的popback

}

const T& top()

{

return it.back(); //使用it的back取栈顶

}

bool empty()

{

return it.empty(); //使用it的empty

}

size_t size()

{

return it.size(); //使用it的size

}

private:

container it; //it可以是list，vector

};

}

注意：

 能不能使用其他类来建立新的类取决于其他类已有的函数能否满足新的类的需求（如增查删改）

2.queue 

https://cplusplus.com/reference/queue/queue/

可通过模板使用其他类来建立stack（如vector，list）

 翻译：

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元 素，另一端提取元素。

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

3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少 支持以下操作:

empty：检测队列是否为空

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

front：返回队头元素的引用

back：返回队尾元素的引用 push_back：在队列尾部入队列 pop_front：在队列头部出队列

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

<code>#include<vector>

#include<list>

namespace space

{

template<class T, class container>// 适配器！！！！！！！！！相当于用其他类（list，vector）来建立队列

class queue

{

public:

void push(const T& x)

{

it.push_back(x);

}

void pop()

{

//it.erase(it.begin()); //若container为vector或list

it.pop_front(); //若container为list，这里只能用list，因为vector 没有pop_front()函数

}

const T& top()

{

return it.front();

}

bool empty()

{

return it.empty();

}

size_t size()

{

return it.size();

}

private:

container it;

};

}

特别注意：

 void pop()

        {

            it.erase(it.begin());      //若container为vector或list

            it.pop_front();              //若container为list，这里只能用list，因为vector 没有pop_front()函数

        }

test.cpp：

#include<iostream>

#include<vector>

#include<list>

using namespace std;

#include"stack.h"

#include"queue.h"

int main()

{

/*zone::stack<int, vector<int>> arr;

arr.push(1);

arr.push(2);

arr.push(3);

arr.push(4);

arr.push(5);

int num = arr.size();

for (int i = 0; i < num; i++)

{

cout << arr.top() << ' ';

arr.pop();

}*/

space::queue<int, list<int>> arr;

arr.push(1);

arr.push(2);

arr.push(3);

arr.push(4);

arr.push(5);

int num = arr.size();

for (int i = 0; i < num; i++)

{

cout << arr.top() << ' ';

arr.pop();

}

}

3.priority_queue 

https://cplusplus.com/reference/queue/priority_queue/

3.1 priority_queue的本质

优先级队列本质为堆！！！！！！！！！！！！！！

3.2 模拟实现 

翻译：

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来自动完成此操作。

1.仿函数 

仿函数本质是类，目的是为了替代c语言中的函数指针

#include<vector>

#include<queue>

namespace zone

{

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;

}

}; //仿函数，判断大小

template<class T, class container = vector<T>,class compare=less<int>>//这里传的都是类型，不是变量，只用于构建模板

class priority_queue

{

public:

priority_queue()

{}

template<class inputiterator>

priority_queue(inputiterator first, inputiterator last)

: arr(first, last)

{

for (int i = (arr.size() - 1 - 1 )/ 2; i >= 0; i--) //向下调整原地建堆

{

adjustdown(i);

}

} //迭代器区间建堆

void adjustup(int child)

{

compare com; //这里才是建立变量

int parent = (child-1)/2;

while (child > 0)

{

if (com(arr[child],arr[parent]))

{

swap(arr[parent], arr[child]);

child = parent;

parent = (child - 1) / 2;

}

else

{

break;

}

}

}

void adjustdown(int parent)

{

int child = 2 * parent + 1;

compare com;

while (child < arr.size())

{

if (child < arr.size() - 1 && com(arr[child + 1], arr[child]))

child++;

if (com(arr[child],arr[parent]))

{

swap(arr[parent], arr[child]);

parent = child;

child = 2 * parent + 1;

}

else

{

break;

}

}

}

void pop() //删堆顶的数据

{

swap(arr[0], arr[arr.size() - 1]);

arr.pop_back();

adjustdown(0);

}

void push(const T& x)

{

arr.push_back(x);

adjustup(arr.size() - 1);

}

const T& top() //取堆顶的数据

{

return arr[0];

}

bool empty()

{

return arr.empty();

}

size_t size()

{

return arr.size();

}

private:

container arr;

};

}

test.cpp:

#include<iostream>

//#include<vector>

//#include<queue>

using namespace std;

#include"priority_queue.h"

int main()

{

//priority_queue<int> arr;

//priority_queue<int> arr; //std中的大堆

priority_queue<int,vector<int>,greater<int>> arr; //std中使用仿函数建立小堆

arr.push(1);

arr.push(5);

arr.push(4);

arr.push(7);

arr.push(2);

arr.push(8);

arr.push(6);

arr.push(3);

while (!arr.empty())

{

cout << arr.top() << ' ';

arr.pop();

}

}

4.杂谈 

sort（a，a+8，greater<int>（）)                                                    //快速排序

zone：：priority_queue<int,vector<int>,greater<int>> arr       //建立优先级队列

思考：为何调用函数用 greater<int>（）建立优先级队列用greater<int>？

 解答：

1. greater<int>（）是匿名对象，greater<int>是类型

2.函数传的是对象，可以自动实例化

3.优先级队列传的是类型，构建模板，得在类里面自己实例化

5. 容器适配器

5.1适配器

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

5.2 STL标准库中stack和queue的底层结构

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

5.3 deque的简单介绍(了解) 

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

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个 动态的二维数组，其底层结构如下图所示： 

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问 的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示