今天写八皇后的算法，采用试探回溯法使用到了c++的stack，然后牵扯出一些毛病让我加深了对c++标准库的stack的理解，我甚至觉得stl 的stack实现的非常简陋，很多不便之处，下面具体分析。 首先贴上vs2013下面的stack源码，跟stl一样，stack默认都是基于deque实现的，所以代码看上去相对其他的数据结构比较简洁，下面贴出主要的源码：
template<class _Ty, class _Container = deque<_Ty> > class stack { // LIFO queue implemented with a container public: typedef stack<_Ty, _Container> _Myt; typedef _Container container_type; typedef typename _Container::value_type value_type; typedef typename _Container::size_type size_type; typedef typename _Container::reference reference; typedef typename _Container::const_reference const_reference; stack() : c() { // construct with empty container } stack(const _Myt& _Right) : c(_Right.c) { // construct by copying _Right } explicit stack(const _Container& _Cont) : c(_Cont) { // construct by copying specified container } _Myt& operator=(const _Myt& _Right) { // assign by copying _Right c = _Right.c; return (*this); } _Myt& operator=(_Myt&& _Right) _NOEXCEPT_OP(is_nothrow_move_assignable<_Container>::value) { // assign by moving _Right c = _STD move(_Right.c); return (*this); } void push(value_type&& _Val) { // insert element at beginning c.push_back(_STD move(_Val)); } template<class... _Valty> void emplace(_Valty&&... _Val) { // insert element at beginning c.emplace_back(_STD forward<_Valty>(_Val)...); } bool empty() const { // test if stack is empty return (c.empty()); } size_type size() const { // test length of stack return (c.size()); } reference top() { // return last element of mutable stack return (c.back()); } const_reference top() const { // return last element of nonmutable stack return (c.back()); } void push(const value_type& _Val) { // insert element at end c.push_back(_Val); } void pop() { // erase last element c.pop_back(); } const _Container& _Get_container() const { // get reference to container return (c); } void swap(_Myt& _Right) _NOEXCEPT_OP(_NOEXCEPT_OP(_Swap_adl(c, _Right.c))) { // exchange contents with _Right _Swap_adl(c, _Right.c); } protected: _Container c; // the underlying container };stack所支持的操作大致有以下：
s.pop();//出栈 s.push(item);s.emplace(args);//压入栈顶 s.top();//返回栈顶元素，但是不将元素出栈 s.empty(); s.size(); s.swap();stack虽然默认基于deque（双端队列）实现的，但是我们可以传入参数，使其底层以其他可以的顺序容器来实现，比如：
stack<int, list<int>> stack<int, vector<int>> stack<int, array<int>>下面给出stl的stack的使用示例：
#include <stack> #include <vector> #include <list> #include <cstdio> using namespace std; int main() { //可以使用list或vector作为栈的容器，默认是使用deque的。 stack<int, list<int>> a; stack<int, vector<int>> b; int i; //压入数据 for (i = 0; i < 10; i++) { a.push(i); b.push(i); } //栈的大小 printf("%d %d\n", a.size(), b.size()); //取栈项数据并将数据弹出栈 while (!a.empty()) { printf("%d ", a.top()); a.pop(); } putchar('\n'); while (!b.empty()) { printf("%d ", b.top()); b.pop(); } putchar('\n'); return 0; }下面说说问题，stack无论底层用什么实现，其接口就那几个，很不灵活！ 首先注意，stack的pop()以及push()都是void类型，并没有返回值，所以像：
stack<Queen> solu; Queen q； //xxxx q=solu.pop();这种感觉是对的用法其实是不对的，遇见这种情况也很好解决，如下：
stack<Queen> solu; Queen q； //xxxx q=solu.top(); solu.pop();因为stack的pop()成员是有返回值的，并且返回值类型是_Container::reference类型，也就是stack的引用类型。 另外要注意的是： stack,queue(stack queue默认是基于deque实现的) ,priority_queue（默认是基于vector实现的） 这3个是c++标准库定义的3个容器适配器，并不是顺序容器或者关联容器，可以接受一个已有的容器类型作为参数来构造自身，比如：stack ,stack等等，所以问题就来了，stack不能进行遍历的操作，stack也并不能使用顺序容器所支持的end(),begin()这些操作，当前也就不支持所有的以迭代器为参数的泛型函数，譬如find()这种，所以使用非常不灵活。
所以我觉得如果想使用灵活的stack结构，还需要自己基于别的数据结构来重新实现stack的底层，譬如使用vector为基类来实现stack类，然后在成员函数中加入我们需要的特定功能，如遍历查找等等：
#include<vector> template <typename T> class Stack: public vector<T> { private: vector<T> data; public: void push ( T const& e ) { data.insert ( data.end(), e ); } T pop() { T tmp=data[data.size()-1]; data.erase( data.end() - 1 ); return tmp; } //xxxxx };这里将向量vector的首端当作栈底，尾部当作栈顶，出栈入栈都十分方便。 这样，第一个问题，pop()函数直接带返回值，解决了。 第二个问题，这种基于vector实现的stack，进行元素的遍历很简单，因为我们可以直接从栈底遍历到栈顶，访问每个元素只是o(1)的时间复杂度，也能解决问题2。
