题目一：实现一个栈，要求其入栈，出栈，返回最小值的时间复杂度为O(1)

这道题目，主要问题在于如何时查找最小元素的时间复杂度为O(1)，这里我们先想到了用一个变量存取最小值

在仅仅入栈时，我们可以通过该MinElem这个变量来查找最小值是完全没有问题的；

但是，如果我们进行出栈，并且把该最小值出栈后，那最小值是不是就找不到了；

下面是正确的解法：

这里我们要用两个栈，第一个栈s，用来存储栈的数据；第二个栈为s_MinElem，用来存取最小值；

与之前我们想的用变量存储，解决的问题是，在出栈后，若出栈了最小元素，那s_MinElem也弹出栈顶最小元素，之后s_MinElem的栈顶是弹出前次小的元素，扔是弹出后最小的元素；

template<typename T>class Stack{public:	void Push(const T& t)	{		if (s_MinElem.empty() || t < s_MinElem.top())			s_MinElem.push(t);		s.push(t);	}	void Pop()	{		assert(!s.empty());		if (s.top() == s_MinElem.top())			s_MinElem.pop();		s.pop();	}	T Min()const	{		return s_MinElem.top();	}PRotected:	stack<T> s;	stack<T> s_MinElem;};
题目二：两个栈实现一个队列
栈的特点是后进先出，而队列是先进先出；为了用两个栈实现一个队列，我们还是需要两个栈来实现
其中一个栈为sin，主要操纵入队；另一个栈为sout，主要用来从此出队
下面我们介绍三种方法，其效率由低到高
这里我只实现了第三种
我们选用第三种的原因是，入队和出队的开销比之前的两种要少，而且元素可以同存放在两个栈中，但并不会影响队列的操作
//两个栈实现一个队列template<typename T>class QueueBTS{public:	void Push(const T& x)	{		sin.push(x);	}	void Pop()	{		assert(!sin.empty() || !sout.empty());		if (sout.empty())		{			while (!sin.empty())			{				sout.push(sin.top());				sin.pop();			}		}		sout.pop();	}	const T& Front()	{		assert(!sin.empty() || !sout.empty());		if (sout.empty())		{			while (!sin.empty())			{				sout.push(sin.top());				sin.pop();			}		}		return sout.top();	}protected:	stack<T> sin;//入列的栈	stack<T> sout;//出列的栈};
题目三：两个队列实现一个栈
这里我们也是，定义两个队列，第一个队列qin主要负责元素的入栈；第二个队列qout负责出栈
//两个队列实现一个栈template<typename T>class StackBTQ{public:	void Push(const T& x)	{		//入栈的元素直接push到qin里面		qin.push(x);	}	void Pop()	{		assert(!qin.empty() || !qout.empty());		//qin队列为空		if (qin.empty())		{			while (qout.size() > 1)			{				qin.push(qout.front());				qout.pop();			}			qout.pop();		}		else//qin队列不为空		{			while (qin.size() > 1)			{				qout.push(qin.front());				qin.pop();			}			qin.pop();		}	}	T Top()	{		assert(!qin.empty() || !qout.empty());		//qin队列为空		if (qin.empty())		{			while (qout.size() > 1)			{				qin.push(qout.front());				qout.pop();			}			return qout.front();		}		else//qin队列不为空		{			while (qin.size() > 1)			{				qout.push(qin.front());				qin.pop();			}			return qin.front();		}	}protected:	queue<T> qin;	queue<T> qout;};
题目四：判断出栈顺序的合法性
比如入栈顺序是【1,2,3,4,5】出栈顺序是【2,4,1,5,3】，判断是否合法
我这里定义的成员是两个vector，用来存储出栈和入栈的序列，且定义了一个stack来判断合法性
当栈为空或者栈顶元素不为当前出栈的元素，则入栈，知道碰到出栈序列对应的元素为止
当入栈序列和出栈序列遍历完后，如果栈为空，则是合法的，否则是非法的
template<typename T>class CheckLegit{public:	CheckLegit(const T* s1, const T* s2,size_t n)	{		for (size_t i = 0; i < n; ++i)		{			vin.push_back(s1[i]);			vout.push_back(s2[i]);		}	}	bool IsLegit()	{		size_t v1 = 0;		size_t v2 = 0;		while (v1 < vin.size() && v2 < vout.size())		{			//如果栈顶元素和出栈顺序不同			//则入栈			while (s.empty() || (s.top() != vout[v2] && v1<vin.size()))			{				s.push(vin[v1]);				v1++;			}			//如果和出栈顺序相同，则出栈			while (!s.empty() && s.top() == vout[v2])			{				if (v2 > vout.size())					return false;				s.pop();				v2++;			}					}		//判断栈是否为空，为空的话是合法的出栈顺序		if (s.empty())			return true;		return false;	}protected:	vector<T> vin;	vector<T> vout;	stack<T> s;};
题目五：用一个数组实现两个栈
这道题目很多人第一次见的很可能摸不着头脑，其实意思非常的简单，如何用一块数组的空间来管理出两个栈，管理它们的入栈出栈各个接口
这道题需要先定义一个数组，我这里用了C++STL提供的vector
方法一：
用下标为奇数的空间放第一个栈的元素，下标为偶数的空间放第二个栈的元素
这种做法的缺点是，浪费的空间会非常的大；如果我们一直只使用其中一个栈，那么有一般的空间是浪费的；
方法二：
将下标从中间开始，作为两个栈的栈底，依次向两边增长；
这种做法没有避免第一种的浪费空间的做法，而且每次扩容的时候不方便，开销也很大；
方法三：
这次我们从两边向中间增长，这样就可以避免浪费空间的问题；
扩容的时候，左边的栈根本不用动，只需要动右边的栈就好；
template<typename T>class TwoStack{public:	TwoStack()		:firstStack_top(0)		, lastStack_top(0)	{}	void FirstStack_Push(const T& x)	{		CheckSize();		_v[firstStack_top++] = x;	}	void FirstStack_Pop()	{		assert(firstStack_top != 0);		firstStack_top--;	}	size_t FirstStack_Size()	{		return firstStack_top;	}	void LastStack_Push(const T& x)	{		CheckSize();		_v[lastStack_top--] = x;	}	void LastStack_Pop()	{		assert(lastStack_top != _v.size() - 1);		lastStack_top++;	}	size_t LastStack_Size()	{		return _v.size() - lastStack_top;	}protected:	vector<T> _v;	size_t firstStack_top;	size_t lastStack_top;protected:	void CheckSize()	{		if (firstStack_top == lastStack_top)		{			if (_v.empty())			{				_v.resize(5);				lastStack_top = 5;				return;			}			size_t lastStacksize = LastStack_Size();			size_t ls = lastStacksize;			size_t newsize = _v.size() * 2;			size_t oldsize = _v.size();			_v.resize(newsize);			for (size_t i = oldsize-1,tmp = newsize; lastStacksize > 0; --i,lastStacksize--)			{				_v[tmp-1] = _v[i];				tmp--;			}			lastStack_top += (newsize / 2);		}	}};