一、stack（栈）：先进后出

1.栈是一种只能从表的一端存取数据且遵循 "先进后出" 原则的线性存储结构。

栈的开口端被称为栈顶；相应地，封口端被称为栈底。

? ? ? ? ? ? 向栈中添加元素，此过程被称为"进栈"（入栈或压栈）；

? ? ? ? ? ? 从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；

2.栈的实现

顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；

链栈：采用链式存储结构实现栈结构；

3.接口使用

stack(const container_type& ctnr = container_type())? ? ? ? ??构造空的栈
bool empty() const? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 检测stack是否为空
size_type size() const? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?返回stack中元素的个数
value_type& top()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 返回栈顶元素的引用
const value_type& top() const? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?返回栈顶元素的const引用
void push (const value_type& val)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 将元素val压入stack中
void pop()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?将stack中尾部的元素弹出
template <class... Args> void emplace (Args&&... args) (C+11) 在stack的栈顶构造元素
void swap (stack& x) ?(C++11)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 交换两个栈中的元素

?二、queue（FIFO先进先出）

与栈结构不同的是，队列的两端都"开口"，要求数据只能从一端进，从另一端出。

队尾入队，队头出队。

2.队列的实现

顺序队列：在顺序表的基础上实现的队列结构；

链队列：在链表的基础上实现的队列结构；

3.接口使用

queue (const container_type& ctnr =?container_type())? ? ? ? ? ? 构造空的队列
bool empty() const? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?检测队列是否为空，是返回true，否则返回false
size_type size() const? ? ? ? ? ? ? ? ? ? ? ? ? 返回队列中有效元素的个数
value_type& front()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 返回队头元素的引用
const value_type& front() const? ? ? ? ?返回队头元素的const引用
value_type& back()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 返回队尾元素的引用
const value_type& back() const? ? ? ? ?返回队尾元素的cosnt引用
void push(value_type& val)? ? ? ? ? ? ? ? 在队尾将元素val入队列
void pop()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?将队头元素出队列
template <class... Args> void emplace (Args&&...?args) (C++11)? ? ? 在队尾构造元素
void swap(queue& x)? ? ? ? ? ? ? ? ? ? ? ? ? ?交换两个队列中的元素

三、priority_queue（默认情况下创建的是大堆）底层是vector实现

? ? ? ?在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。是一种容器适配器，

string，vector，deque，list都是容器序列器。vector、deque是数组实现的容器。

优先队列具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。

priority_queue(const Compare& x = Compare(), ?const Container& y =?Container() );
构造一个空的优先级队列
template ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
priority_queue(InputIterator first, InputIterator last, const?
Compare& comp = Compare(), const Container& ctnr = Container());
用[first, last)区间中的元素构造优先级队列
bool empty( ) const? ? ? ? ? ? ? ? ? ? ? ? ? ? 检测优先级队列是否为空，是返回true，否则返回false
const value_type& top ( )?const? ? ? ? 返回优先级队列中最大(最小元素)，即堆顶元素
void push ( const T& x )? ? ? ? ? ? ? ? ? ? ?在优先级队列中插入元素x
void pop ( )? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 删除优先级队列中最大(最小)元素，即堆顶元素

四、容器适配器

stack、queue、priority_queue都是容器适配器，底层封装了其他容器。

stack底层封装了deque，queue底层封装了deque，priority_queue底层封装了vector

Stack的?模拟实现?

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

template<class T,class con=deque<T>>
class Stack
{
public:
	Stack(){}//构造栈
	void Push(const T& x)//将元素x压入栈stack中
	{
		_c.push_back(x);
	}
	void Pop()//将stack尾部元素弹出
	{
		_c.pop_back();
	}
	T& Top()//返回栈顶元素的引用
	{
		return _c.back();
	}
	const T& Top()const//返回栈顶元素的const引用
	{
		return _c.back();
	}
	size_t Size()const//返回stack中元素的个数
	{
		return _c.size();
	}
	bool Empty()const//检测stack是否为空
	{
		return _c.empty();
	}
private:
	con _c;
};
int main()
{
	Stack<int> s;
	s.Push(1);
	s.Push(2);
	s.Push(3);
	s.Push(4);
	cout << s.Size() << endl;
	cout << s.Top() << endl;
	s.Pop();
	s.Pop();
	cout << s.Size() << endl;
	cout << s.Top() << endl;
	system("pause");
	return 0;
}
//结果：4 4 2 2