用兩個棧實作一個隊列 & 用兩個隊列實作一個棧

隊列（先進先出）和棧（先進後出）都是常用的經常讨論的基本的資料結構，本文要讨論的是一對有趣的問題：如何用兩個棧（隊列）實作一個隊列（棧），下面将分别說明，并附示例代碼。

        1、用兩個棧實作一個隊列

基本思路：初始有兩個空棧s1和s2，當入隊列是，将元素加入s1，而出隊列則從s2出，當然s1與s2之間存在一定的互動。

入隊：元素壓入棧s1即可。

出隊：首先看s2是否為空，若s2為空，則依次彈出s1的元素，加入s2中；若不為空，則不需額外處理；

之後彈出s2中的棧頂元素（即為隊列的首元素）删除即可。

獲得隊首元素：與出隊操作類似，差別隻是在最後彈出s2中的棧頂元素（即為隊列的首元素）并傳回而不删除。

        代碼實作以及簡單的測試代程式如下：

測試截圖：

2、兩個隊列實作一個棧

基本思路：初始有兩個空隊列q1和q2，q1用于存儲棧中元素，q2用于在pop()和top()操作時候臨時存放q1的元素。

入棧push()：将元素直接加入隊列q1的尾部

出棧pop()：先判斷隊列q1元素數目是否為1，若為一，直接彈出并删除即可；若多于1，則将q1中元素彈出并加入q2直至q1剩餘一個元素，将其删除，然後将

q2暫存的元素彈出并壓入q1即可。

獲得棧頂元素top():與pop()操作類似，隻是對于q1中的最後一個元素，将其傳回而不是删除。

        實作代碼及簡單的測試程式如下：