http://blog.csdn.net/zw_1510/article/details/51927554

問題1：用兩個棧實現一個隊列，實現隊列的push和delete操作?

棧的特性是先進后出（FILO）,隊列的特性是先進先出（FIFO）,在實現delete時，我們的難點是如何將棧中最底層的數據拿出來，我們有兩個棧，所以我們可以將一個棧中的數據依次拿出來壓入到另一個為空的棧，另一個棧中數據的順序恰好是先壓入棧1的元素此時在棧2的上面，為了實現效率的提升，我們在delete時，判斷棧2是否有數據，如果有的話，直接刪除棧頂元素，在棧2為空時才將棧1的數據壓入到棧2中，從而提高程序的運行效率，實現過程可以分為下面幾個步驟：?
1、push操作時，一直將數據壓入到棧2中?
2、delete操作時，首先判斷棧2是否為空，不為空的情況直接刪除棧2棧頂元素，為空的話將棧1的數據壓入到棧2中，再將棧2棧頂元素刪除。?
實現代碼如下：

template <typename T>
class CQueue
{
public:CQueue(void){}~CQueue(void){}void appendTail(const T& node);T deleteHead();
private:stack<T> stack1;stack<T> stack2;
};template<class T>
void CQueue<T>::appendTail(const T& node)//在隊列尾部添加數據
{stack1.push(node);
}
template<class T>
T CQueue<T>::deleteHead()
{T tmp = 0;if (stack2.empty()) //若棧2為空{while (!stack1.empty()){tmp = stack1.top();stack2.push(tmp);stack1.pop();}}tmp = stack2.top();stack2.pop();return tmp;
}

• 運行結果如下：

問題2：用兩個隊列實現一個棧?
因為隊列是先進先出，所以要拿到隊列中最后壓入的數據，只能每次將隊列中數據pop到只剩一個，此時這個數據為最后壓入隊列的數據，在每次pop時，將數據壓入到另一個隊列中。每次執行delete操作時，循環往復。（感覺效率低）每次刪除時間復雜度O(N)?
代碼如下：

template <typename T>
class CStack
{
public:CStack(void){}~CStack(void){}void appendTail(const T& node);T deleteHead();
private:queue<T> q1;queue<T> q2;
};template<class T>
void CStack<T>::appendTail(const T& node)//在棧尾部添加數據
{if (!q1.empty())//不為空的執行push操作{q1.push(node);}else{q2.push(node);}
}
template<class T>
T CStack<T>::deleteHead()
{int ret = 0;if (q1.empty()){int i = q2.size();while (i > 1 )//將q2隊列中的數據pop到只剩一個{q1.push(q2.front());q2.pop();--i;}ret = q2.front();q2.pop();}else{int i = q1.size();while (i > 1){q2.push(q1.front());q1.pop();--i;}ret = q1.front();q1.pop();}return ret;

• 
  

兩個問題解決思路類似，主要就是要合理使用隊列和棧的特點，并注意程序的效率。