stack的基本使用

#include<stack>
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
while(!st.empty())
{
  cout << st.top() << " ";
  st.pop();
}
cout << endl;

queue的基本使用

#include<queue>
queue<int> q;
q.push();
while(!q.empty())
{
	cout << q.front() << " ";
	q.pop();
}
cout << endl;

priority_queue

priority_queue<int> pq;
pq.push(10);
pq.push(1);
pq.push(15);
pq.push(20);
pq.push(2);
pq.push(4);
pq.push(19);
while(!pq.empty())
{
  cout << pq.top() << " ";
  pq.pop();
}
cout << endl;

优先级队列存放自定义类型，自定义类型需要支持大小比较运算

建大堆需要提供小于比较的仿函数类
建小堆需要提供大于比较的仿函数类

仿函数

STL组件：使用方式类似于函数的类 —-> 重载圆括号 “( )” 的运算符重载函数

仿函数对象：由仿函数类创建的对象

//仿函数类模版
template<class T>
struct Less
{
  bool operator()(const T& c1, const T& c2)
  {
    return c1 < c2;
  }
};

void test()
{
  Less<C> lc;
  C c1(1, 2, 3);
  C c2(2, 2, 2);
  bool ret = lc.operator()(c1, c2);
  ret = lc(c1, c2);
}

容器适配器

STL组件，stack，queue，priority_queue

通过适配器的设计模式定义的新的数据结构

适配器：把一种接口转化为另一种接口的方法

stack：template< class T, class Container = deque<T> > class stack

实现：vector，list，deque ==默认实现：deque==

stack实现规范：只要包含以下接口，都可以作为stack低层容器

Push_back —-> push
Pop_back —->pop
front —-> top
size —-> size
Empty —-> empty

Queue实现：list， deque ==默认实现：deque==

queue实现规范：只要包含以下接口，都可以作为queue低层容器

Push_back —-> push
Pop_back —-> pop
front —-> front
back —-> back
size —-> size
empty —-> empty

vector不能实现queue，因为它不提供pop_front接口

Priority_queue实现：vector deque，==默认实现：vector==

实现规范：只要包含以下接口，其容器本身支持随机访问，都可以作为priority_queue的低层容器

Push_back —-> push
Pop_back —-> pop
Front —-> top
Size —-> size
Empty —-> empty

list不能实现priority_queue，因为其不支持随机访问

duque 双端队列

逻辑连续，物理上不完全连续的线性表

实现：指针数组 + buffer —-> 动态二维数组

头插、头删、尾插、尾删时间复杂度都为O(1)，不需要移动元素
支持随机访问，但是随机访问的效率低于vector，需要进行位置换算
增容代价小，不需要拷贝所有元素内容。增容过程：开一个更大的指针数组，拷贝原始指针数组中的内容（指针），开新的buffer，buffer首地址存入新的指针数组，新的buffer存放新元素。原始存放元素的空间不需要更改
在中间位置插入数组，时间复杂度O(n)。

stack：默认实现deque，deque实现stack的优势

stack不需要随机访问。
vector增容代价比较大
list容易造成内存碎片，空间利用率低

queue：默认实现deque，deque实现queue优势

list容易造成内存碎片，空间利用率低

priority_queue：默认实现vector，vector实现priority_queue的优势

deque随机访问效率比较低，因为list不支持随机访问，所以不能用其实现

关于模拟实现template<T, Container, Compare>
- 模版参数：Compare：
  1. 执行大小比较的逻辑 —-> 通过仿函数实现
  2. 提供的仿函数不同，可以产生不同的堆结构。不需要修改源代码，极大的增加了代码的灵活性及通用性
  3. 如果是自定义类型数据，需要重载> <运算符

模拟实现

stack、queue及priority_queue的模拟实现—GitHub