数据结构--一个数组实现两个栈

用一个数组实现两个栈，通常我们会想到以下几种方案：

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);

3.两个队列实现一个栈；