記錄學習內容。
以下內容和截圖大多引用文章。
還不了解，內容可能有錯誤。

Queue 可以用 Stack 製作 。

Stack 也可以用 Queue 製作 。

Queue 的 enQueue  相當於 Stack 的 push 。放東西進去 。

Queue 的 deQueue  相當於 Stack 的 pop 。把東西拿出 。

先來看 ，用 Stack 製作 Queue :

Queue using Stacks

https://www.geeksforgeeks.org/queue-using-stacks/

方法 1

一個stack 叫s1 ， 另一個stack叫 s2 。


enQueue 代表 放東西 。
enQueue 裡的寫法 :
如果 s1 不是空的 ，s2就會push (s1的pop) 
像是s1 現在是1(stack的top) 2 3 4 5(5代表最後放，在stack的最底端) 。
會變成 
s2 : 5(stack的top) 4 3 2 1  
s1:空的 
之後 s1.push(x) ，s1: 6 (新增的數字)
如果s2不是空的 ，就
s1.push(s2.pop());  
s1 會變成 1(stack的top) 2 3 4 5 6 

看程式，主要是寫在enQueue 。
簡單想就是 把s1倒到s2 -- >s1.push -->再把s2倒回來。

時間複雜度 :

Push operation: O(N).
把s1 倒 到 s2 ，再把s2 倒回來 。大概2n ?

Pop operation: O(1).
直接從s1頂端 pop

方法2

程式寫在deQueue(取東西)裡
這個想法比較簡單 ，如果s1是5(stack的top，最後放) 4 3 2 1 。
s1 倒到 s2 ，s2會變成1(stack的top ) 2 3 4 5
這樣s2 pop 的時候 ，就是答案了

方法3

也可以只用一個stack的製作 。

不斷把s1 pop ，return 最後一項 ，不是最後一項的，在一個一個放回s1。用遞迴。