stack和queue简单模拟实现

stack

Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.

上述描述出自cplusplus.

重点是stack是一个container adaptor也就是容器适配器。
这意味着我们不需要也没有必要从0开始实现stack的方法，而可以通过一个模板，来调用其他容器来实现，以下是stack的部分从成员函数：

template<class T, class Container = deque<int>>
class stack
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con.back();}private:Container _con;
};

可以发现只需要调用传来的模板参数即可。

这里的默认容器是deque，这是一个均衡的容器，整体效率没有vector高，但是可以实现push_front。这是vector做不到的，或者说vector的头插效率是O(n)，过低。

值得注意的是，所有容器适配器都不支持迭代器。
就以stack举例，如果支持迭代器，那是否意味着破坏了他的FILO特性呢？是的。因此不支持迭代器。

reverse_iterator

上文提到容器适配器，那就不得不提到反向迭代器了。
之前我们实现vector和list的时候都没有实现反向迭代器，因为两者内容过于相似，现在了解了反向迭代器的机制后我们知道，是否可以通过穿入迭代器容器，然后实现反向迭代器。

这意味着，我们可以同时实现所有容器的反向迭代器，也就是实现他们的模板：

template<class Iterator,class Ref,class Ptr>
struct Reverse_iterator
{typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Iterator _it;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *((--tmp));}Ptr operator->(){return &(operator*());}Self& operator++(){return --_it;}Self& operator--(){return ++_it;}bool operator!=(const Self& it){return _it != it;}};

需要注意的一点是，我们的operator*返回的是 *（--tmp)，而不是 *（tmp).

原因是，我们的rbegin（）和rend（）返回的是end()和begin（）。这是基于代码对称性考虑的，正常而言我们的rbegin（）和rend（）理应返回end()-1和begin（）-1.

为了解决这个问题，就只能令operator*返回 *（--tmp)。

注：以上实现是visual studio的实现方式。

queue

template<class T, class Container = deque<int>>
class queue
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& front(){return _con.front();}const T& back(){return _con.back();}private:Container _con;
};

priority_queue

priority_queue实质上就是一个堆，并且是默认大根堆。那么我们想要将其改变为小根堆改如何实现？
如果是C语言的话，我们会增加一个函数指针的参数来实现。
在C++中，我们通过传入一个仿函数来实现。

仿函数

所谓仿函数就是指能够像函数一样使用的对象，如下：

template<class T>
class less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};
void test(int x,int y)
{less l;if(l(x,y))cout<<"x<y";else cout<<"x>=y";
}

本质上，我们重载了 ()，因此能够将这个对象像函数一样使用。

具体代码

堆的实现，我们已经讲过，这里就不做赘述，感兴趣的读者可以翻阅我前面的文章。

template<class T,class Container=vector<T>,class Compare = less<T>>
class priority_queue
{
public://默认大堆void adjust_up(size_t child){size_t parent = (child - 1) / 2;Compare com;while (child >0){if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child<_con.size()){if (child + 1 < _con.size() && com(_con[child],_con[child+1])){++child;}if (com(_con[parent],_con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}private:Container _con;
};

说起来这里比较奇怪的点是，默认传入less<T>是大根堆，而穿入greater<T>却是小根堆。
但sort穿入，less<T>却是升序排序：

int main()
{vector<int>v = { 1,5,4,3,2 };sort(v.begin(), v.end(),less<int>());//传入less的匿名对象for (auto& e : v)cout << e << ' ';cout << endl;return 0;
}

Output:1 2 3 4 5