題目一：實現(xiàn)一個棧，要求其入棧，出棧，返回最小值的時間復(fù)雜度為O(1)

這道題目，主要問題在于如何時查找最小元素的時間復(fù)雜度為O(1)，這里我們先想到了用一個變量存取最小值

在僅僅入棧時，我們可以通過該MinElem這個變量來查找最小值是完全沒有問題的；

但是，如果我們進(jìn)行出棧，并且把該最小值出棧后，那最小值是不是就找不到了；

下面是正確的解法：

這里我們要用兩個棧，第一個棧s，用來存儲棧的數(shù)據(jù)；第二個棧為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;};
題目二：兩個棧實現(xiàn)一個隊列
棧的特點是后進(jìn)先出，而隊列是先進(jìn)先出；為了用兩個棧實現(xiàn)一個隊列，我們還是需要兩個棧來實現(xiàn)
其中一個棧為sin，主要操縱入隊；另一個棧為sout，主要用來從此出隊
下面我們介紹三種方法，其效率由低到高
這里我只實現(xiàn)了第三種
我們選用第三種的原因是，入隊和出隊的開銷比之前的兩種要少，而且元素可以同存放在兩個棧中，但并不會影響隊列的操作
//兩個棧實現(xiàn)一個隊列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;//出列的棧};
題目三：兩個隊列實現(xiàn)一個棧
這里我們也是，定義兩個隊列，第一個隊列qin主要負(fù)責(zé)元素的入棧；第二個隊列qout負(fù)責(zé)出棧
//兩個隊列實現(xiàn)一個棧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來判斷合法性
當(dāng)棧為空或者棧頂元素不為當(dāng)前出棧的元素，則入棧，知道碰到出棧序列對應(yīng)的元素為止
當(dāng)入棧序列和出棧序列遍歷完后，如果棧為空，則是合法的，否則是非法的
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;};
題目五：用一個數(shù)組實現(xiàn)兩個棧
這道題目很多人第一次見的很可能摸不著頭腦，其實意思非常的簡單，如何用一塊數(shù)組的空間來管理出兩個棧，管理它們的入棧出棧各個接口
這道題需要先定義一個數(shù)組，我這里用了C++STL提供的vector
方法一：
用下標(biāo)為奇數(shù)的空間放第一個棧的元素，下標(biāo)為偶數(shù)的空間放第二個棧的元素
這種做法的缺點是，浪費(fèi)的空間會非常的大；如果我們一直只使用其中一個棧，那么有一般的空間是浪費(fèi)的；
方法二：
將下標(biāo)從中間開始，作為兩個棧的棧底，依次向兩邊增長；
這種做法沒有避免第一種的浪費(fèi)空間的做法，而且每次擴(kuò)容的時候不方便，開銷也很大；
方法三：
這次我們從兩邊向中間增長，這樣就可以避免浪費(fèi)空間的問題；
擴(kuò)容的時候，左邊的棧根本不用動，只需要動右邊的棧就好；
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);		}	}};