棧&隊(duì)列的那些應(yīng)用---常見面試題

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

   棧呢，只能在末端上進(jìn)行操作，具有先進(jìn)后出的特點(diǎn)。

   隊(duì)列呢，只能在隊(duì)頭刪除，隊(duì)尾插入，具有先進(jìn)先出的特點(diǎn)。

   偶們應(yīng)該利用棧和隊(duì)列的特征來解決一下幾個(gè)問題：

    1.使用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列 

    2.使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

    3.元素出棧、入棧順序的合法性。如入棧的序列（1,2,3,4,5），出棧序列為（4,5,3,2,1）

    4.一個(gè)數(shù)組實(shí)現(xiàn)兩個(gè)棧

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

先來看第一個(gè)問題：

1. 使用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

   思路：棧（先進(jìn)后出）  隊(duì)列（先進(jìn)先出）

   假設(shè)有兩個(gè)棧為是s1，s2。將s1作為基礎(chǔ)棧，而s2只是暫時(shí)維護(hù)數(shù)據(jù)棧。

   
   

    若壓入1,2,3。則輸出的也應(yīng)該是1，2,3。

    “入隊(duì)”：棧只能從棧頂出。所以現(xiàn)將s1中的數(shù)據(jù)壓入s2中（如圖）。

    “出隊(duì)”：從s2中彈出即可。

 代碼實(shí)現(xiàn)：

#include <stack>
template <class T>
class StackToQueue//棧s1為基本棧，s2維護(hù)棧
{
public:
	StackToQueue()
		:_size(0)
	{}
public:
void StackToQueuePush(const T& d)//s1入隊(duì)
{
	s1.push(d);
	++_size;
}
void StackToQueuePop()//s2出隊(duì)
{
	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;//使用庫(kù)函數(shù)stack
	stack<int> s2;
	size_t _size;//棧中元素個(gè)數(shù)
};

2.使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

  思路：隊(duì)列（先進(jìn)先出），棧（后進(jìn)先出）

      隊(duì)列和棧插入數(shù)據(jù)時(shí)都是在末端操作。刪除數(shù)據(jù)不同，棧還是在末端操作而隊(duì)列在隊(duì)頭操作。

      假設(shè)有隊(duì)列q1，q2。

      “出?！保杭偃绗F(xiàn)有個(gè)n數(shù)據(jù)，將數(shù)據(jù)壓入q1，然后將n-1個(gè)數(shù)據(jù)彈入q2，將第n個(gè)數(shù)據(jù)彈出，此時(shí)  s1隊(duì)列為空，將q2中的前n-1個(gè)數(shù)據(jù)彈入q1，將第n個(gè)彈出。此時(shí)q2隊(duì)列為空，以此類推，知道彈出所有  數(shù)據(jù)。

代碼實(shí)現(xiàn)：

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;//隊(duì)列中元素的個(gè)數(shù)
};

3.元素出棧、入棧順序的合法性。如入棧的序列（1,2,3,4,5），出棧序列為（4,5,3,2,1）

  看到此題，首先想到棧的特征是后進(jìn)先出。這就使得棧的出棧順序有多種。

  舉一個(gè)簡(jiǎn)單的例子：

  假如有一個(gè)入棧序列為1,2,3。出棧序列就有1,2,3、2,1,3、3,2,1、2,3,1、1,3,2共5種。

  解題思路：

  若要驗(yàn)證出入棧的合法性。首先呢，我們應(yīng)該有兩個(gè)數(shù)組將入棧序列和出棧序列保存起來。假設(shè)Push數(shù)組存入棧，Pop數(shù)組存出棧。從頭開始判斷數(shù)據(jù)是否相同，若相同，Push和Pop數(shù)組下標(biāo)加加。若不同，應(yīng)將數(shù)據(jù)保存起來，以便下一次比較。這就有一個(gè)問題。如何將數(shù)據(jù)保存起來呢，還要便于取出呢？這就需要一個(gè)棧將其保存。若不相同，將其壓棧。比較下一個(gè)數(shù)據(jù)，如不相同，還要將棧中的數(shù)據(jù)彈出比較，相同彈出，不同繼續(xù)壓棧。

代碼實(shí)現(xiàn)：

//借助兩個(gè)數(shù)組以及一個(gè)棧
#include <stack>
#include <assert.h>
bool IsVail(int *Push,int *Pop,int n)
{
	assert(Push);//數(shù)組元素不為NULL
	assert(Pop);
	stack<int> s;
	int i = 0;
	int j = 0;
	for(j=0;j<n;)//出棧序列下標(biāo)
	{
		for(i=0;i<n;i++)//入棧序列下標(biāo)
		{
			if(Push[i] != Pop[j])//不相同
			{
				if(s.empty())//棧空
				{
					s.push(Push[i]);//入棧
					continue;//跳出本次循環(huán)
				}	
				else
				{
				    if(Pop[i] == s.top())//棧不為空，不同需和棧中數(shù)據(jù)比較
					{
						s.pop();//相同彈出
						j++;
					}
					else
					{
						s.push(Push[i]);//不同繼續(xù)壓棧
					}
				}
			}
			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.一個(gè)數(shù)組實(shí)現(xiàn)兩個(gè)棧

 解題思路：

（1）可將數(shù)組以奇數(shù)為下標(biāo)的當(dāng)為棧1，以偶數(shù)為下標(biāo)的當(dāng)為棧2。

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

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

分析：

 思路（1），（2）雖然能解決問題，但是會(huì)浪費(fèi)空間。若棧1存滿，需要擴(kuò)容。而棧2可能空無元素。

 思路（3）可解決此缺憾。當(dāng)棧1，棧2的棧頂相遇時(shí)，需要擴(kuò)容。

 以下用靜態(tài)和動(dòng)態(tài)分別實(shí)現(xiàn)：

（1）靜態(tài)

代碼實(shí)現(xiàn)

#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)//給標(biāo)志，若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];//數(shù)組
	int _top1;//棧1的棧頂
	int _top2;//棧2的棧頂
};

（2）動(dòng)態(tài)

代碼實(shí)現(xiàn)

class ArrayToStack
{
public:
	ArrayToStack()
		:_a(NULL)
		,_top1(0)
		,_top2(0)
		,_capacity(0)
	{}
	~ArrayToStack()
	{
		if(_a)
		{
			delete[] _a;
		}
	}
public:
	void _CheckCapacity()//擴(kuò)容
	{
		if(_a == NULL)
		{
			_capacity = 3;
			_a = new T[_capacity];
			_top1 = 0;
			_top2 = _capacity-1;
		}
		else
		{
			if(_top1 == _top2)
			{
				int capacity = _capacity; //保存之前的容量，在下面復(fù)制時(shí)方便找到最后一個(gè)元素
				_capacity = 2*_capacity;
				int i = 0;
				int j = 0;
				T* tmp = new T[_capacity];
				for(i=0;i<_top1;i++)//將原來的復(fù)制到新開辟的空間上
				{
					tmp[i] = _a[i];
				}
				int k = _capacity - 1;//擴(kuò)容后的最后一位
				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;//數(shù)組
	int _top1;//棧1的棧頂
	int _top2;//棧2的棧頂
	int _capacity;//容量
};

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

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

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

 （1）使用一個(gè)棧

  每一次入棧都?jí)簝纱?，第一次壓入原始?shù)據(jù)，第二次壓入當(dāng)前棧中最小的。在第二壓棧之前，需和上一次的比較，若小于則壓棧，否則將上一次的再次壓棧。出棧時(shí)，每次都彈出兩次。

 （2）使用兩個(gè)棧

  第一個(gè)棧用來保存原始數(shù)據(jù)，第二棧用保存當(dāng)前棧中最小值。第一次兩個(gè)棧中都?jí)喝耄粼俅螇喝霔?，需要和?dāng)前棧2中的元素比較，若小于等于則入棧，否則只壓入棧1。

分析：

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

   此處實(shí)現(xiàn)的是第二種方法：

棧的簡(jiǎn)單實(shí)現(xiàn)：

template <class T>
class Stack
{
public:
	Stack()//構(gòu)造函數(shù)
		:_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()//元素個(gè)數(shù)
	{
		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;//棧中元素的個(gè)數(shù)
};