栈和队列的一些算法

看本文之前，推荐本博客的http://blog.csdn.net/lsjseu/article/details/9351141，熟悉一下STL中序列容器的接口以及内部实现结构。

本文搜集了一下关于栈和队列的一些算法。

（1）用两个栈构成一个队列。

算法很简单，一个栈负责“插入”，一个栈负责“弹出”。当弹出的栈没有元素的时候，要从插入的栈把元素全部搬过来。

#include <iostream>#include <stack>#include <cassert>#include <string>using namespace std;bool IsPopOrder(int pushSeq[],int popSeq[],int len){assert(pushSeq && popSeq && len>0);stack<int> st;int i,j = 0;for(i=0; i<len; ++i){int popNum = popSeq[i];while(st.empty() || st.top()!=popNum){st.push(pushSeq[j++]);if(j == len)break;}if(st.top() != popNum)break;st.pop();}if(st.empty() && i==len)return true;else return false;}int main(){const int SIZE = 5;int pushSeq[SIZE] = {1,2,3,4,5};int popSeq[SIZE] = {4,5,3,2,1};string result = IsPopOrder(pushSeq,popSeq,SIZE)?"True":"False";cout<<result<<endl;system("pause");return 0;}

这里说明一下：给定栈的入栈序列，出栈的序列可能有多少种。（这是一个卡特兰数）类似的问题，包括给定前序遍历，中序遍历的有多少种？括号匹配问题。1,2,5......详细参考：http://blog.csdn.net/lsjseu/article/details/11827109