用Stack 制作Queue

记录学习内容。
以下内容和截图大多引用文章。
还不了解，内容可能有错误。

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。用递回。