棧&隊列的那些應用---常見面試題

   首先呢，偶們先來回顧一下棧和隊列的特征：

   棧呢，只能在末端上進行操作，具有先進后出的特點。

   隊列呢，只能在隊頭刪除，隊尾插入，具有先進先出的特點。

   偶們應該利用棧和隊列的特征來解決一下幾個問題：

    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 <stack>
template <class T>
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.top()<<" ";
		s1.pop();
	}
	while(!s2.empty())
	{
		cout<<s2.top()<<" ";
		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<int> s1;//使用庫函數stack
	stack<int> s2;
	size_t _size;//棧中元素個數
};

2.使用兩個隊列實現一個棧

  思路：隊列（先進先出），棧（后進先出）

      隊列和棧插入數據時都是在末端操作。刪除數據不同，棧還是在末端操作而隊列在隊頭操作。

      假設有隊列q1，q2。

      “出棧”：假如現有個n數據，將數據壓入q1，然后將n-1個數據彈入q2，將第n個數據彈出，此時  s1隊列為空，將q2中的前n-1個數據彈入q1，將第n個彈出。此時q2隊列為空，以此類推，知道彈出所有  數據。

代碼實現：

template <class T>
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<int> q1;
	queue<int> 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 <stack>
#include <assert.h>
bool IsVail(int *Push,int *Pop,int n)
{
	assert(Push);//數組元素不為NULL
	assert(Pop);
	stack<int> s;
	int i = 0;
	int j = 0;
	for(j=0;j<n;)//出棧序列下標
	{
		for(i=0;i<n;i++)//入棧序列下標
		{
			if(Push[i] != Pop[j])//不相同
			{
				if(s.empty())//棧空
				{
					s.push(Push[i]);//入棧
					continue;//跳出本次循環
				}	
				else
				{
				    if(Pop[i] == s.top())//棧不為空，不同需和棧中數據比較
					{
						s.pop();//相同彈出
						j++;
					}
					else
					{
						s.push(Push[i]);//不同繼續壓棧
					}
				}
			}
			else
			{
				j++;
			}
		}
	}
	if(i == j) //出棧合法條件
	{
		return true;
	}
	else
	{
		return false;
	}
}
int main()
{
	int arr1[5] = {1,2,3,4,5};
	int arr2[5] = {4,3,5,2,1};
	bool ret = IsVail(arr1,arr2,5);
	if(ret)
	{
		cout<<"出棧順序合法"<<endl;
	}
	else
	{
		cout<<"出棧順序不合法"<<endl;
	}
	return 0;
}

4.一個數組實現兩個棧

 解題思路：

（1）可將數組以奇數為下標的當為棧1，以偶數為下標的當為棧2。

（2）將數組一分為二，左邊為棧1，右邊為棧2。

（3）數組從左邊開始為棧1，從右邊開始為棧2。

分析：

 思路（1），（2）雖然能解決問題，但是會浪費空間。若棧1存滿，需要擴容。而棧2可能空無元素。

 思路（3）可解決此缺憾。當棧1，棧2的棧頂相遇時，需要擴容。

 以下用靜態和動態分別實現：

（1）靜態

代碼實現

#define SIZE 10  
template <class T>
class ArrayToStack
{
public:
	ArrayToStack()
		:_top1(0)//棧1從頭開始
		,_top2(SIZE-1)//棧2從尾開始
	{}
public:
	//void Push2(const T& d)//從頭壓棧
	//{
	//	_a[_top1++] = d;
	//}
	//void Push3(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<<endl;
		for(j=_top2+1;j<_capacity;j++)
		{
			cout<<_a[j]<<" ";
		}
	}
public:
	void Push(const T& d,int choice)
	{
		_CheckCapacity();
		if(choice == 0)//壓入棧1
		{
			_a[_top1++] = d;
		}
		if(choice == 1)//壓入棧2
		{
			_a[_top2--] = d;
		}
	}
	void Pop()
	{
		if(choice == 0)//彈出棧1
		{
			if(_top1 == 0)
				return;
			else
			_top1--;
		}
		if(choice == 1)//彈出棧2
		{
			if(_top2 == 0)
				return;
			else
			_top2++;
		}
	}
protected:
	T* _a;//數組
	int _top1;//棧1的棧頂
	int _top2;//棧2的棧頂
	int _capacity;//容量
};

5.實現一個棧，要求實現Push（入棧）、Pop（出棧）、Min（返回最小值的操作）的時間復雜度為O(1)

  看到此題，我們都知道Push（入棧）、Pop（出棧）的時間復雜度為O（1）。而解決此題的難點在于Min（返回最小值的操作）的時間復雜度為O(1)。我們不可能從頭開始遍歷，這樣復雜度不可能為O（1）

  解決此題的方法有如下兩種：

 （1）使用一個棧

  每一次入棧都壓兩次，第一次壓入原始數據，第二次壓入當前棧中最小的。在第二壓棧之前，需和上一次的比較，若小于則壓棧，否則將上一次的再次壓棧。出棧時，每次都彈出兩次。

 （2）使用兩個棧

  第一個棧用來保存原始數據，第二棧用保存當前棧中最小值。第一次兩個棧中都壓入，若再次壓入棧，需要和當前棧2中的元素比較，若小于等于則入棧，否則只壓入棧1。

分析：

   若要是數據量龐大，可見第一種方法使用的空間很大。

   此處實現的是第二種方法：

棧的簡單實現：

template <class T>
class Stack
{
public:
	Stack()//構造函數
		:_a(NULL)
		,_top(0)
		,_capacity(0)
	{}
	~Stack()
	{
		if(_a)
		{
			delete[] _a;
			_a = NULL;
		}
	}
	Stack(Stack<T>& 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<T>& operator=(Stack<T>& 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 T>
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<T> s1;//棧1
	Stack<T> s2;//棧2
	size_t _size;//棧中元素的個數
};