探索C/C++的奥秘之stack和queue

1. stack的介绍和使用

1.1 stack的介绍

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。具体什么是适配器呢？其实就是由现有的东西进行转换，转化出我要的东西。container adaptor就是适配器，

2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

empty：判空操作

back：获取尾部元素操作

push_back：尾部插入元素操作

pop_back：尾部删除元素操作

4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

1.2 stack的使用

int main()
{
   stack<int> st;
   st.push(1);
   st.push(2);
   st.push(3);
   st.push(4);
   while (!st.empty())
   {
       cout << st.top() << " ";
       st.pop();
   }
   cout << endl;
   return 0;
}

stack和队列都是空间适配器，他们都没传空间配置器，都是传了一个容器进去，它是通过容器转换出来的。

3. priority_queue的介绍和使用

3.1 priority_queue的介绍

优先级队列和双端队列严格来说都不是队列了，它只是占了队列的名称而已，严格来说队列是要求先进先出，双端队列没有要求先进先出，其实它就是一个支持各种操作的线性表，优先级队列也不是先进先出，它占一个优先级，它的名称还更好一点，它是按优先级去出。

优先级队列一般是放在queue的头文件下，queue的头文件下面有两个，一个是queue，一个是优先级队列。

优先级队列也是一个容器适配器，首先它有一个Container，基本上而言，有Container的都是容器适配器，它的默认适配容器没有用deque，用的是vector，为什么会用vector呢？它还给了一个Compare，这个叫做仿函数，具体后面再说。

它的相关操作：

优先级队列要出优先级高的，那什么是优先级高的呢？我们也不知道。大的高还是小的高？它这给的仿函数的意思是自己可以控制，想要大的高就大的高，想要小的高就小的高，都可以帮助你去做到，它默认是大的高，它的底层是什么？再看看它的接口，push、pop、top、为啥起名叫top？其实它的底层就是二叉树的堆，那就是说大的优先级高它是大堆，小的优先级高它是小堆，它的接口设计跟咱们当初写的那个堆也很像，严格来说不是它跟我们写的堆很像，是我们写的跟它很像，我们那个堆只是没有取名叫优先级队列，其实是参考着它写的。

优先级队列不需要传其它的东西，因为后面有缺省参数。学了这个东西的本质是我们不需要搞一个堆出来，我们造top不需要堆了。这个容器适配器也有一个特点是：不支持遍历，它没有提供迭代器，取数据的时候也要跟我们的栈和队列类似，边取边走才能取到所有的数据。

#include<iostream>
#include<queue>
using namespace std;
void text_priority_queue()
{
   priority_queue<int> pq;
   pq.push(1);
   pq.push(2);
   pq.push(3);
   pq.push(4);
   pq.push(5);
   while (!pq.empty())
   {
       cout << pq.top() << " ";
       pq.pop();
   }
   cout << endl;
}

int main()
{
   text_priority_queue();
   return 0;
}

它有一个非常奇怪的现象，less<typename Container::value_type>这个地方叫做容器适配器，这个默认的容器适配器传的是less，less就是小于，这个算是当初设计这个库时的失误。默认是大堆，要搞成小堆应该怎么办？要传第三个模板参数，必须优先传第二个。

#include<iostream>
#include<queue>
using namespace std;
void text_priority_queue()
{
   priority_queue<int, vector<int>, greater<int>> pq;
   pq.push(1);
   pq.push(2);
   pq.push(3);
   pq.push(4);
   pq.push(5);
   while (!pq.empty())
   {
       cout << pq.top() << " ";
       pq.pop();
   }
   cout << endl;
}

int main()
{
   text_priority_queue();
   return 0;
}

小的优先级高就搞定了，为什么要传greater呢？通过小于大于去控制升序和降序。

优先级队列给了一个迭代器区间构造，第一个是无参构造，相当于全缺省就是无参，第二个是传了一个迭代器区间，传一个迭代器区间的意思是我给你这段区间，你可以直接用这些值去构建一个堆。

把这里的vector改成deque也是可以的，但换成deque效率不是很高。

很多人在这里有疑问，greater<int>()和greater<int> 有什么关系呢？第一个是函数模板，函数模板要传对象，传的是匿名对象，第二个是类模板，类模板传的是参数，参数是什么？参数是类型，不能加括号。

什么是仿函数？

PriorityQueue.h

//这就是一个最简单的仿函数，也叫做函数对象
//仿函数更多的是指这个类，函数对象是指这个类定义的对象
class Less
{
public:
   bool operator()(int x, int y)
   {
       return x < y;
   }
private:

};

text.cpp

#include"PriorityQueue.h"

int main()
{
   Less lessfunc;
   cout << lessfunc(1, 2) << endl;
   //上面的代码本质等价于下面的这个代码
   cout << lessfunc.operator()(1, 2) << endl;
   return 0;
}

实际上是怎么调用的呢？

这个类重载一个运算符，叫operator()，cout << lessfunc(1, 2) << endl;本质等价于cout << lessfunc.operator()(1, 2) << endl;仿函数的真正意义是这个类的对象可以像函数一样使用，其实它真正要替代是C语言中的函数指针。

有些地方是把这个库再扩展一下写成类模板，这个时候就可以支持更大类型的了，前提是这个类型支持小于的比较。

.h

template<class T>
class Less
{
public:
   bool operator()(const T& x, const T& y)
   {
       return x < y;
   }
private:

};

.cpp

int main()
{
   Less<int> lessfunc;
   cout << lessfunc(1, 2) << endl;
   //上面的代码本质等价于下面的这个代码
   cout << lessfunc.operator()(1, 2) << endl;
   return 0;
}