1.stack和queue
stack和queue的相关接口如下：
stack
queue
我们发现不管是stack还是queue，它们都有push和pop，不区分push_back和push_front，这是由它们的入栈特定顺序特性决定的，并且它们都没有迭代器，stack只有top，queue只有front和back这使得我们只能以规定的方式去访问这个stack或者queue
emplace相当于入栈，一般我们用push就可以了。
2.stack和queue的模拟实现
我们已经知道stack、queue和vector、list本质上并没有区别，所以我们可以将复用的思想带到它们的实现中，并且我们可以利用模板对于同一个stack模板，使用不同的底层来实现。这体现了继迭代器模式后的第二种设计模式：适配器模式，即转换。
下面是它们的实现
template<class T, class Container = vector<T>>
class stack
{
public:
stack(const Container& con = Container())
:_con(con)
{}
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_back();
}
T& top()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
void swap(stack& st)
{
std::swap(_con, st._con);
}
private:
Container _con;
};
template<class T, class Container = list<T>>
class queue
{
public:
queue(const Container& con = Container())
:_con(con)
{}
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
T& back()
{
return _con.back();
}
T& front()
{
return _con.front();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
void swap(queue& q)
{
std::swap(_con, q._con);
}我们可以看出，stack和queue的实现几乎不需要自己实现具体功能，我们只需要关注上层功能而不是底层的细节，这极大地体现了封装的特性。
代码中仍有一些细节点需要注意：
（1）为什么只写了构造但没有写析构？为什么构造有缺省值
构造时我们可能空构造，需要缺省值，也有可能带参构造，带参构造需要我们形参接收，这里展示的是拷贝构造的情况，析构的时候成员_con作为自定义类型会去调用自己的析构函数，不会存在内存泄露的情况，所以不需要我们显式的去写析构
（2）swap为什么使用std::swap？
事实上，当我们包含了<vector><list>后，std域里的swap函数就多了几个重载，这几个重载是专门针对vector和list类型的，_con和q._con是Container类型，也就是vector<int>或list<int>类型，会去调用重载的效率较高的swap函数。
之所以std里重载swap函数，就是为了让我们在不知vector类里有swap成员函数的情况下也能高效地交换（只交换指针的值而不是交换所有指向的值）。因此除了这种写法，我们还可以显式调用vector类的成员函数
（3）stack只能以vector作为容器吗？
vector是连续的物理结构，下标访问快，但头插效率极低。因此vector不支持头插头删。在queue中pop使用了pop.front()，在vector里没有这个接口，所以不能使用vector实现queue，但是我们如果用erase来实现pop也可以，这样就可以用vector实现queue了，但并不建议这么做，因为vector实现queue本就是效率极低的做法。
list是分散的物理结构，任意位置插入删除效果都不错，但下标访问效率低。因此list不支持下标访问。但是stack和queue都没用到下标访问，因此我们可以用list实现queue和stack。
事实上，stack和queue在STL中都是以deque作为默认的容器。我们发现，vector和list本就是两个极端的存储结构。所以deque是结合vector、list，能同时进行下标访问和push_back、push_front等操作的容器。
deque用buff小数组+中控数组来实现它的功能，是vector和list存储的结合体，虽然支持下标访问，但它的没vector快，deque[]偶尔用用还行，头尾删除不错。我们适当了解一下deque即可，不用深究，因为deque本不算一个效率高的容器。
3.优先级队列和仿函数
priority_queue本质上是堆，我们只要掌握了堆，优先级队列的核心就能很快完成了。
但是priority_queue用到了仿函数的知识点，在大堆小堆的处理和我们C语言有所不同
（1）仿函数：
仿函数，即模仿函数的一个类，我们看下面的代码：
comp(1,2)是我们常见的函数的写法，但它的本质是是一个类重载了operator()后表现出来的类似于函数的特性。仿函数实现起来也相当简单，只要理解了它的实质就能很快上手
但是仿函数和构造函数容易搞混，一定要注意仿函数是要针对已创建的对象调用而不是针对类来调用，那种写法是构造函数而不是仿函数
（2）优先级队列
优先级队列的功能很简单，就是结合vector、仿函数实现堆，核心代码就是AdjustUp和AdjustDown。
建议将AdjustUp和AdjustDown放进private，对外只提供push、pop这样的接口，体现封装的特性。
注意当仿函数是less时默认是大堆，greater默认是小堆，在我们进行数值比较时要注意谁在前谁在后，因为顺序不同，会影响返回值，从而影响我们生成的堆的类型。
由于堆相关的知识前面我已经详细讲过，这里就不多阐述了。
完整代码如下：
namespace my_priority_queue
{
template<typename T>
class less
{
public:
bool operator()(const T& t1, const T& t2)
{
return t1 < t2;
}
};
template<typename T>
class greater
{
public:
bool operator()(const T& t1, const T& t2)
{
return t1 > t2;
}
};
template<typename T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
priority_queue() = default;
template<typename iterator>
priority_queue(iterator begin, iterator end)
{
while (begin != end)
{
_con.push_back(*begin);
begin++;
}
for (int parent = (int)(size() - 2) / 2; parent >= 0; parent--)
{
AdjustDown(parent);
}
}
size_t size()
{
return _con.size();
}
void push(const T& val)
{
_con.push_back(val);
AdjustUp(size() - 1);
}
void pop()
{
std::swap(_con[0], _con[size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top()
{
return _con[0];
}
bool empty()
{
return _con.empty();
}
void swap(priority_queue& p)
{
std::swap(_con, p._con);
}
private:
void AdjustUp(size_t child)
{
Compare comp;
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (comp(_con[parent], _con[child]))
std::swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
}
void AdjustDown(size_t parent)
{
Compare comp;
size_t child = parent * 2 + 1;
while (child < size())
{
if (child + 1 < size() && comp(_con[child], _con[child + 1]))
child++;
if(comp(_con[parent], _con[child]))
std::swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
}
private:
Container _con;
};
}
