Stack模拟实现

从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

代码语言：javascript

AI代码解释

#include<vector>
namespace bite
{
  template<class T>
  class stack
{
public:
stack() {}
void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_back();}
T& top() {return _c.back();}
const T& top()const {return _c.back();}
size_t size()const {return _c.size();}
bool empty()const {return _c.empty();}
private:
std::vector<T> _c;
};
}

Queue简单理解

1. 队列是一种适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元 素，另一端提取元素。 2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供 一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。 3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少 支持以下操作:

• empty：检测队列是否为空
• size：返回队列中有效元素的个数
• front：返回队头元素的引用
• back：返回队尾元素的引用
• push_back：在队列尾部入队列
• pop_front：在队列头部出队列

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

Queue模拟实现

因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实 现queue，具体如下：

代码语言：javascript

AI代码解释

#include <list>
namespace bite
{
  template<class T>
  class queue
 {
   public:
    queue() {}
    void push(const T& x) {_c.push_back(x);}
    void pop() {_c.pop_front();}
    T& back() {return _c.back();}
    const T& back()const {return _c.back();}
    T& front() {return _c.front();}
    const T& front()const {return _c.front();}
    size_t size()const {return _c.size();}
    bool empty()const {return _c.empty();}
   private:
     std::list<T> _c;
  };
}

priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中 元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。注意：默认情况下priority_queue是大堆。

代码语言：javascript

AI代码解释

#include <vector>
#include <queue>
#include <functional>  // greater算法的头文件
   void TestPriorityQueue()
  {
   // 默认情况下，创建的是大堆，其底层按照小于号比较
   vector<int> v{3,2,7,6,0,4,1,9,8,5};
   priority_queue<int> q1;
   for (auto& e : v)
   q1.push(e);
   cout << q1.top() << endl;
   // 如果要创建小堆，将第三个模板参数换成greater比较方式
   priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
   cout << q2.top() << endl;
  }

容器适配器

什么是适配器

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

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

虽然stakc于queue中也存放元素，但是它俩并不属于容器行列，而是属于容器适配器。因为stack于queue只是对其他容器的接口进行了包装。，STL中stack和queue默认 使用deque。

deque

deque原理介绍：

deque（双端队列）：是一种双开口的“连续”空间的数据结构，双端也就是允许头尾进行插入与删除操作。时间复杂度为O(1)，与vector比较，头插效率高，与 list比较，空间利用率比较高