#include<iostream>usingnamespacestd;#include<stack>#include<queue>#include<assert.h>//template<classT>//两个栈实现一个队列//classStackToqueue//{//public://StackToqueue()//{}//voidPush(constT&x)//{//始终保持让栈1进//_stack1.push(x);//}//TPop()//{//if(_stack2.empty()&&!_stack1.empty())//{//如果栈2为空且栈1不为空，则将栈1的所有元素导入到栈2中，保证栈1进，栈2出//while(!_stack1.empty())//{//_stack2.push(_stack1.top());//_stack1.pop();//}//}//TStackPopElm=_stack2.top();//_stack2.pop();//returnStackPopElm;//}//~StackToqueue()//{}//protected://stack<T>_stack1;//stack<T>_stack2;//};////voidTest()//{//StackToqueue<int>s;//s.Push(1);//s.Push(2);//s.Push(3);//s.Push(4);//s.Push(5);//s.Push(6);//s.Push(7);//s.Push(8);//s.Push(9);//s.Push(10);//cout<<s.Pop()<<""<<endl;//cout<<s.Pop()<<""<<endl;//s.Push(11);//cout<<s.Pop()<<""<<endl;//cout<<s.Pop()<<""<<endl;//}//两个队列实现一个栈//template<classT>//classQueueToStack//{//public://QueueToStack()//{}//voidpush(constT&x)//{//如果队列1不为空则让元素入到这个不为空的队列中，若为空，默认入到队列2中//if(!_queue1.empty())//{//_queue1.push(x);//}//else//_queue2.push(x);//}//TPop()//{//if(_queue1.empty()&&_queue2.empty())//{//return-1;//}////如果-个队列不为空，让该队列的前n-1个元素出队列，放入到另一个队列中////让该队列中保持只有一个元素然后让其出队列//if(!_queue1.empty())//{//while(_queue1.front()&&_queue1.front()!=_queue1.back())//{//_queue2.push(_queue1.front());//_queue1.pop();//}//TQueuePopElm=_queue1.front();//_queue1.pop();//returnQueuePopElm;////}//if(!_queue2.empty())//{//while(_queue2.front()&&_queue2.front()!=_queue2.back())//{//_queue1.push(_queue2.front());//_queue2.pop();//}//TQueuePopElm=_queue2.front();//_queue2.pop();//returnQueuePopElm;//}//}//~QueueToStack()//{}//protected://queue<T>_queue1;//queue<T>_queue2;//};//voidTest()//{//QueueToStack<int>q;//q.push(1);//q.push(2);//q.push(3);//q.push(4);//q.push(5);//q.push(6);//q.push(7);//q.push(8);//cout<<q.Pop()<<"";//cout<<q.Pop()<<"";//cout<<q.Pop()<<"";//q.push(9);//cout<<q.Pop()<<"";//cout<<q.Pop()<<"";//}//求一个栈中的最小元素//template<classT>//classStackMin//{//public://StackMin()//{}//TGetStackMinTop()//{//return_stack_min.top();//}//voidPush(constT&x)//两个栈同时入元素，保存最小数的那个栈在入栈前先要与该栈顶元素相比较//{//始终保持保存最小数的那个栈的栈顶元素是当前所有元素之中最小的//_stack.push(x);//if(_stack_min.empty())//{//_stack_min.push(x);//}//else//{//if(_stack_min.top()<x)//{//_stack_min.push(GetStackMinTop());//}//else//{//_stack_min.push(x);//}//}//}//voidPop()//{//if(!_stack.empty()&&!_stack_min.empty())//{//_stack.pop();//_stack_min.pop();//}//}//protected://stack<T>_stack;//stack<T>_stack_min;//};////voidTest()//{//StackMin<int>sm;//sm.Push(2);//sm.Push(8);//sm.Push(6);//sm.Push(9);//sm.Push(1);//sm.Push(5);//cout<<sm.GetStackMinTop()<<endl;//sm.Pop();//cout<<sm.GetStackMinTop()<<endl;//sm.Pop();//cout<<sm.GetStackMinTop()<<endl;//sm.Push(0);//cout<<sm.GetStackMinTop()<<endl;////}//判断出栈顺序的合法性template<classT>classStack{public:Stack(){}boolIsLegal(constchar*pushstr,constchar*popstr){assert(pushstr&&popstr);if(strlen(pushstr)!=strlen(popstr))returnfalse;while(*pushstr||!_stack.empty()){//如果入栈序列不为空或者栈不为空_stack.push(*pushstr++);while(!_stack.empty()&&_stack.top()==*popstr){//若栈不为空且栈顶元素与出栈序列元素相同，则出栈序列指针后移同时将栈顶元素出栈popstr++;_stack.pop();}//如果入栈序列已为空且出栈序列元素不与栈顶元素匹配if(*pushstr=='\0'&&!_stack.empty()&&*popstr!=_stack.top())returnfalse;}returntrue;}~Stack(){}protected:stack<T>_stack;};voidTest(){Stack<char>s;char*str="12345";char*dst="54321";cout<<s.IsLegal(str,dst)<<endl;}