資料結構--一個數組實作兩個棧

用一個數組實作兩個棧，通常我們會想到以下幾種方案：

1.奇偶棧，即就是将數組的偶數位置看作一個棧的存儲空間，将奇數位置看作另一個棧的存儲空間。

2.從中間分别向兩邊展開，即就是将數組的中間位置看作是兩個棧的棧底，壓棧時棧頂指針分别向兩邊移動，當任何一邊到達數組的起始位置或是數組尾部就開始擴容。

3.從兩邊向中間壓棧，就是将數組的起始位置看作是一個棧的棧底，将數組的尾部看作是另一個棧的棧底，壓棧時，棧頂指針分别向中間移動，隻要兩棧頂指針不相遇，兩個棧就可以一直使用，如果相遇就實行擴容。

這幾種方法比較下來，前兩種在一些情況下對空間的使用率較低，比如：在一個棧裡存的資料多，另一個棧又存的比較少。第三種方法對空間的使用率相對就比較高了，但也存在着一些問題，比如在擴容的時候還得把資料都拷過來，萬事都沒有十全十美的。。。

這裡呢，就以空間使用率較高的第三種方法來附上代碼：

template<class T>
class TwoStack
{
public:
	TwoStack()
		:_top1(0)
		,_top2(0)
		,_capacity(0)
		,_arr(NULL)
	{
		CheckCapacity();
	}

	~TwoStack()
	{
		if(NULL!=_arr)
		{
			delete[] _arr;
		}
	}
	void Push1(const T& d)
	{
		CheckCapacity();
		_arr[_top1++]=d;
	}
	void Push2(const T& d)
	{
		CheckCapacity();
		_arr[_top2--]=d;
	}
	void Pop1()
	{
		assert(_top1>0);
		_top1--;
	}
	void Pop2()
	{
		assert(_top2<_capacity-1);
		_top2++;
	}
	size_t Size1()
	{
		return _top1;
	}
	size_t Size2()
	{
		return _capacity-1-_top2;
	}
	bool Empty1()
	{
		return _top1==0;
	}
	bool Empty2()
	{
		return _top2==_capacity-1;
	}
	T& Top1()
	{
		assert(_top1>0);
		return _arr[_top1-1];
	}
	T& Top2()
	{
		assert(_top2<_capacity-1);
		return _arr[_top2+1];
	}
protected:

	void CheckCapacity()
	{
		if(NULL==_arr)
		{
			_capacity += 2;
			_arr=new T[_capacity];
			_top2=_capacity-1;
			return ;
		}
		if(_top1==_top2)
		{
			size_t newCapacity=_capacity*2+2;
			T* tmp=new T[newCapacity];
			for(size_t i=0;i<_top1;++i)
			{
				tmp[i]=_arr[i];
			}
			size_t j=newCapacity-1;
			for(size_t k=_capacity-1;k>_top2;--k)
			{
				tmp[j]=_arr[k];
				--j;
			}

			_top2=newCapacity-(_capacity-_top2);
			_capacity=newCapacity;
			_arr=tmp;	
		}
	}
private:
	T* _arr;
	size_t _top1;
	size_t _top2;
	size_t _capacity;

};
           

測試代碼：

void test()
{
	TwoStack<int> s;
	for(size_t i=0;i<4;++i)
	{
		s.Push1(i);
	}
	for(size_t i=4;i<8;++i)
	{
		s.Push2(i);
	}
	cout<<"s1:"<<s.Size1()<<endl;
	cout<<"s2:"<<s.Size2()<<endl;
	cout<<"棧1：";
	while(!s.Empty1())
	{
		cout<<s.Top1()<<" ";
		s.Pop1();
	}
	cout<<endl;
	cout<<"棧2：";
	while(!s.Empty2())
	{
		cout<<s.Top2()<<" ";
		s.Pop2();
	}
}
           

邊緣檢測：

void test1()
{
	TwoStack<int> s;
	for(size_t i=0;i<6;++i)
	{
		s.Push1(i);
	}
	cout<<"s1:"<<s.Size1()<<endl;
	cout<<"s2:"<<s.Size2()<<endl;
	cout<<"棧1：";
	while(!s.Empty1())
	{
		cout<<s.Top1()<<" ";
		s.Pop1();
	}
}

void test2()
{
	TwoStack<int> s;
	for(size_t i=0;i<6;++i)
	{
		s.Push2(i);
	}
	cout<<"s1:"<<s.Size1()<<endl;
	cout<<"s2:"<<s.Size2()<<endl;
	cout<<"棧2：";
	while(!s.Empty2())
	{
		cout<<s.Top2()<<" ";
		s.Pop2();
	}
}
           

棧和隊列相關的其他幾道常考面試題：

1.實作一個棧，要求實作push,pop以及min(傳回最小值)的時間複雜度為O(1);

http://blog.csdn.net/qq_29503203/article/details/52507057 2.兩個棧實作一個隊列; http://blog.csdn.net/qq_29503203/article/details/52713523

3.兩個隊列實作一個棧；

http://blog.csdn.net/qq_29503203/article/details/52718137 4.判斷棧的1彈出序列是否合法; http://blog.csdn.net/qq_29503203/article/details/52722648