首先呢，偶们先来回顾一下栈和队列的特征：

   栈呢，只能在末端上进行操作，具有先进后出的特点。

   队列呢，只能在队头删除，队尾插入，具有先进先出的特点。

   偶们应该利用栈和队列的特征来解决一下几个问题：

    1.使用两个栈实现一个队列 

    2.使用两个队列实现一个栈

    3.元素出栈、入栈顺序的合法性。如入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1）

    4.一个数组实现两个栈

    5.实现一个栈，要求实现Push（出栈）、Pop（入栈）、Min（返回最小值的操作）的时间复杂度为O(1)

先来看第一个问题：

1. 使用两个栈实现一个队列

   思路：栈（先进后出）  队列（先进先出）

   假设有两个栈为是s1，s2。将s1作为基础栈，而s2只是暂时维护数据栈。

    若压入1,2,3。则输出的也应该是1，2,3。

    “入队”：栈只能从栈顶出。所以现将s1中的数据压入s2中（如图）。

    “出队”：从s2中弹出即可。

 代码实现：

#include 
     
      template 
      
       class StackToQueue//栈s1为基本栈，s2维护栈{public:	StackToQueue()		:_size(0)	{}public:void StackToQueuePush(const T& d)//s1入队{	s1.push(d);	++_size;}void StackToQueuePop()//s2出队{	if(s2.empty())	{		while(!s1.empty())//将栈s1--->s2	   {		   s2.push(s1.top());		   s1.pop();		}	}	s2.pop();	--_size;}void Print(){	while(!s1.empty())	{		cout<
       
        <<" ";		s1.pop();	}	while(!s2.empty())	{		cout<
        
         <<" ";		s2.pop();	}}size_t Size(){	return _size;}T& Back(){	if(s2.empty())	{		return s1.top();	}	else	{		return s2.end();	}}T& Front(){	if(s1.empty())	{		return s2.top();	}	else	{		return s1.end();	}}bool Empty(){	return _size==0;}T& Top(){	if(!s1.empty())	{		return s1.top();	}	else	{		return s2.top();	}}void Pop(){	s1.pop();	--_size;}protected:	stack
         
           s1;//使用库函数stack	stack
          
            s2; size_t _size;//栈中元素个数};
          
         
        
       
      
     

2.使用两个队列实现一个栈

  思路：队列（先进先出），栈（后进先出）

      队列和栈插入数据时都是在末端操作。删除数据不同，栈还是在末端操作而队列在队头操作。

      假设有队列q1，q2。

      “出栈”：假如现有个n数据，将数据压入q1，然后将n-1个数据弹入q2，将第n个数据弹出，此时  s1队列为空，将q2中的前n-1个数据弹入q1，将第n个弹出。此时q2队列为空，以此类推，知道弹出所有  数据。

代码实现：

template 
     
      class QueueToStack{public:	QueueToStack()		:_size(0)	{}public:	void QueueStackPush(const T& d)//q1入栈	{		q1.push(d);		++_size;	}void QueueStackPop()//出栈{	size_t sz = 0;	if(_size)	{		if(q2.empty())		{		    sz = _size - 1;			while(sz--)			{				q2.push(q1.front());				q1.pop();			}			q1.pop();			--_size;		}		else //(q1.empty())		{			sz = _size - 1;			while(sz--)			{				q1.push(q2.front());				q2.pop();			}			q2.pop();			--_size;		}	}}size_t Size(){	return _size;}T& Top()//栈顶元素{	return q1.back();}protected:	queue
      
        q1;	queue
       
         q2;	size_t _size;//队列中元素的个数};
       
      
     

3.元素出栈、入栈顺序的合法性。如入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1）

  看到此题，首先想到栈的特征是后进先出。这就使得栈的出栈顺序有多种。

  举一个简单的例子：

  假如有一个入栈序列为1,2,3。出栈序列就有1,2,3、2,1,3、3,2,1、2,3,1、1,3,2共5种。

  解题思路：

  若要验证出入栈的合法性。首先呢，我们应该有两个数组将入栈序列和出栈序列保存起来。假设Push数组存入栈，Pop数组存出栈。从头开始判断数据是否相同，若相同，Push和Pop数组下标加加。若不同，应将数据保存起来，以便下一次比较。这就有一个问题。如何将数据保存起来呢，还要便于取出呢？这就需要一个栈将其保存。若不相同，将其压栈。比较下一个数据，如不相同，还要将栈中的数据弹出比较，相同弹出，不同继续压栈。

代码实现：

//借助两个数组以及一个栈#include 
     
      #include 
      
       bool IsVail(int *Push,int *Pop,int n){	assert(Push);//数组元素不为NULL	assert(Pop);	stack
       
         s;	int i = 0;	int j = 0;	for(j=0;j
       
      
     

4.一个数组实现两个栈

 解题思路：

（1）可将数组以奇数为下标的当为栈1，以偶数为下标的当为栈2。

（2）将数组一分为二，左边为栈1，右边为栈2。

（3）数组从左边开始为栈1，从右边开始为栈2。

分析：

 思路（1），（2）虽然能解决问题，但是会浪费空间。若栈1存满，需要扩容。而栈2可能空无元素。

 思路（3）可解决此缺憾。当栈1，栈2的栈顶相遇时，需要扩容。

 以下用静态和动态分别实现：

（1）静态

代码实现

#define SIZE 10  template 
     
      class ArrayToStack{public:	ArrayToStack()		:_top1(0)//栈1从头开始		,_top2(SIZE-1)//栈2从尾开始	{}public:	//void Push1(const T& d)//从头压栈	//{	//	_a[_top1++] = d;	//}	//void Push2(const T& d)//从尾部压栈	//{	//	_a[_top2--] = d;	//}	void Push(const T& d,int choice)//给标志，若choice为0，压入栈1，若为1，压入栈2	{		if(choice == 0)		{			_a[_top1++] = d;		}		if(choice == 1)		{			_a[_top2--] = d;		}	}	void Pop(int choice)//choice为0，弹出栈1，choice为1，弹出栈2	{   	       if(choice == 0)		{			if(_top1 == 0)				return;			else			_top1--;		}		if(choice == 1)		{			if(_top2 == 0)				return;			else			_top2++;		}	}	size_t size(int choice)	{		if(choice == 0)		{			return _top1;		}		if(choice == 1)		{			return _top2;		}		}	T& Top(int choice)	{		if(choice == 0)		{			return _a[_top1];		}		if(choice == 1)		{			return _a[_top2];		}		}protected:	T _a[SIZE];//数组	int _top1;//栈1的栈顶	int _top2;//栈2的栈顶};
     

（2）动态

代码实现

class ArrayToStack{public:	ArrayToStack()		:_a(NULL)		,_top1(0)		,_top2(0)		,_capacity(0)	{}	~ArrayToStack()	{		if(_a)		{			delete[] _a;		}	}public:	void _CheckCapacity()//扩容	{		if(_a == NULL)		{			_capacity = 3;			_a = new T[_capacity];			_top1 = 0;			_top2 = _capacity-1;		}		else		{			if(_top1 == _top2)			{				int capacity = _capacity; //保存之前的容量，在下面复制时方便找到最后一个元素				_capacity = 2*_capacity;				int i = 0;				int j = 0;				T* tmp = new T[_capacity];				for(i=0;i<_top1;i++)//将原来的复制到新开辟的空间上				{					tmp[i] = _a[i];				}				int k = _capacity - 1;//扩容后的最后一位				for(j=capacity-1;j>_top2;j--)				{					tmp[k--] = _a[j];				}				_top2 = k;//将_top2更新				delete[] _a;				_a = tmp;			}		}	}	void Print()	{		int i = 0;		int j = 0;		for(i=_top1-1;i>=0;i--)		{			cout<<_a[i]<<" ";		}		cout<

5.实现一个栈，要求实现Push（入栈）、Pop（出栈）、Min（返回最小值的操作）的时间复杂度为O(1)

  看到此题，我们都知道Push（入栈）、Pop（出栈）的时间复杂度为O（1）。而解决此题的难点在于Min（返回最小值的操作）的时间复杂度为O(1)。我们不可能从头开始遍历，这样复杂度不可能为O（1）

  解决此题的方法有如下两种：

 （1）使用一个栈

  每一次入栈都压两次，第一次压入原始数据，第二次压入当前栈中最小的。在第二压栈之前，需和上一次的比较，若小于则压栈，否则将上一次的再次压栈。出栈时，每次都弹出两次。

 （2）使用两个栈

  第一个栈用来保存原始数据，第二栈用保存当前栈中最小值。第一次两个栈中都压入，若再次压入栈，需要和当前栈2中的元素比较，若小于等于则入栈，否则只压入栈1。

分析：

   若要是数据量庞大，可见第一种方法使用的空间很大。

   此处实现的是第二种方法：

栈的简单实现：

template 
     
      class Stack{public:	Stack()//构造函数		:_a(NULL)		,_top(0)		,_capacity(0)	{}	~Stack()	{		if(_a)		{			delete[] _a;			_a = NULL;		}	}	Stack(Stack
      
       & s)	{		size_t i = 0;		_top = s._top;		_capacity = s._top;		_a = new T[_top];		for(i=0;i<_top;i++)		{			_a[i] = s._a[i];		}	}	Stack
       
        & operator=(Stack
        
         & s)	{		if(this != &s)		{			size_t i = 0;			delete[] _a;			_top = s._top;			_capacity = s._capacity;			_a = new T[_top];			for(i=0;i<_top;i++)			{				_a[i] = s._a[i];			}		}		return *this;	}public:	void CheckCapacity()//检容	{		if(_top == _capacity)		{			_capacity = _capacity*2+3;		    T* tmp = new T[_capacity];			size_t i = 0;			for(i=0;i<_top;i++)			{				tmp[i] = _a[i];			}			delete[] _a;			_a = tmp;		}	}public:	void Push(const T& x)//插入	{		CheckCapacity();		_a[_top++] = x;	}	void Pop()//栈顶删除	{		_top--;	}	T& Top()//返回栈顶元素	{		return _a[_top-1];	}	bool Empty()//栈是否为空	{		return _top == 0;	}	size_t Size()//元素个数	{		return _top;	}private:	T* _a;	size_t _top;	size_t _capacity;};
        
       
      
     

返回最小值操作：

template 
     
      class StackMin{public:	StackMin()		:_size(0)	{}public:	void M_Push(const T& d)	{		if(s1.Empty() && s2.Empty())		{			s1.Push(d);			s2.Push(d);		}		else		{			if(s2.Top() < d)			{				s1.Push(d);			}			else			{				s1.Push(d);				s2.Push(d);			}		}		++_size;	}	void M_Pop()	{		if(s1.Top() == s2.Top())		{			s1.Pop();			s2.Pop();		}		else		{			s1.Pop();		}		--_size;	}	T& MinMem()	{		return s2.Top();	}	size_t M_Size()	{		return _size;	}protected:	Stack
      
        s1;//栈1	Stack
       
         s2;//栈2	size_t _size;//栈中元素的个数};