容器适配器：栈、队列、优先级队列

一、容器适配器

什么是容器适配器？

：适配器底层没有自己的数据结构，它是另外一个容器的封装，它的方法全部由底层依赖的容器进行实现的；它没有实现自己的迭代器，不能使用迭代器遍历。

来看这个例子：我们使用容器适配器来实现一个栈。

template<typename T, typename Container=deque<T>>
class Stack
{
public:
	void push(const T &val);
	{
		con.push_back(val);
	}
	void pop()
	{
		con.pop_back();
	}
	T top()const
	{
		return con.back();
	}
private:
	Container con;
};

实现成功，相当于栈将deque代理了一下，也成为代理模式。push将底层容器的push_back代理了，pop将底层pop_back代理了，栈的top将容器底层的back代理了。

二、栈

我们使用库中的栈，需要加上头文件<stack>

stack常用方法： 1.push();//入栈 2.pop();//出栈 3.top();//查看栈顶元素 4.empty();//判断栈空 5.size();//返回元素个数

简单使用一下：

stack<int> s1;

for (int i=0; i<20; ++i)
{
	s1.push(rand() % 100 + 1);
}

cout << "栈中元素个数:" <<s1.size() << endl;

while (!s1.empty())
{
	cout << s1.top() << " ";
	s1.pop();
}

三、队列

我们使用库中的队列，需要加上头文件<queue>

stack常用方法： 1.push();//入队 2.pop();//出队 3.front();//查看队头元素 4.back();//产看队尾元素 5.empty();//判空 6.size();//返回队列元素个数

简单使用一下：

queue<int> que;

for (int i=0; i<20; ++i)
{
	que.push(rand() % 100 + 1);
}

cout << "队列中元素个数:" <<que.size() << endl;

while (!que.empty())
{
	cout << que.front() << " ";
	que.pop();
}

四、优先级队列

优先级队列：底层数据结构为。 我们使用库中的优先级队列，需要加上头文件<queue>；优先级队列，谁优先级大谁先出队，谁优先级小，谁后出队。

stack常用方法： 1.push();//入优先级队列 2.pop();//出优先级队列 3.top();//查看队顶元素 4.empty();//判断队空 5.size();//返回元素个数

简单使用一下：

priority_queue<int> pque;

for (int i=0; i<20; ++i)
{
	pque.push(rand() % 100 + 1);
}

cout << "优先级队列中元素个数:" <<pque.size() << endl;

while (!pque.empty())
{
	cout << pque.top() << " ";
	pque.pop();
}

执行成功：数据从大到小依次出队，数据越大优先级越高。

问题一：stack与queue第二个模板类型参数依赖deque，为什么不依赖vector？而优先级队列为什么底层依赖vector？

1. vector的，没有deque好。(需要从0开始2倍扩容)

2. 对于queue来说，需要支持，时间复杂度需要为O(1)，deque恰好符合条件，若用vector其底层效率太低。

3. vector需要大片的连续内存，而deque只需要分段的内存，当存储大量数据时，显然deuqe对于更好一些。

问题二：优先级队列为什么底层依赖vector？

优先级队列底层默认把数据组成一个大根堆结构，将大根堆结构看作一棵树，如果将大根堆结构所有元素放入数组中，使用下标计算其结点。若根节点为i，左孩子为2i+1，右孩子为2i+2；大根堆为堆顶，其元素最大，，因此底层依赖vector；而deque的第二维不是连续的，不能使用。