[題目]
Implement a queue which support getMin() operation.
Please try to make getMin() in O(1).
這題要你做一個queue，但是要有getMin()的功能。
比如說queue長這樣 : 7 3 1 4 5
getMin()會return 1
這題我本來是沒做過，感謝朋友在我寫完Min Stack這篇後，提醒我還有這個延伸題目。有朋友果然能讓人大開眼界。
[思路]
網路上有少許資料，例如這位印度朋友就分享了解這題的心路歷程。
他的心路歷程跟我一樣，看到了"min"關鍵字就想到min heap(又名min priority queue)這個知名的data structure。這個方法有達成題目的要求O(1) getMin()。但相當複雜需要其他先備知識。
----下面文長甚入----
用一個一般的queue，額外搭配一個min heap。所謂的搭配指的是，queue的每個element有一個pointer指向min heap tree中對應的node。
當你要getMin()，回傳min heap tree的root。
當你要pop()，從queue中pop()出來的元素的link，找到對應的heap tree node，然後將tree node刪除並調整heap tree。
這個方法實在麻煩，原因是你要要用link list的方式寫這棵heap tree。平常可以用array寫heap，但這次不行，因為array版本的heap在調整過程中，tree node的index會交換，這樣你queue中的link就失效了。
所以首先你要懂heap，而且要會implement，還要會implement比較複雜的link list版本。
如果你開始覺得想關掉這個網頁，那代表這個方法真的不適合你。
我本人也不太喜歡這麼複雜。不就是queue嗎，怎麼一下跳到好難的heap tree去了。
[厲害的思路]
老實說我自己肯定想不出來，因為這方法結合了兩個很稀有的技巧，我壓根不會往這去想。
這兩個技巧之前有寫過 (即使我寫過我都沒往這邊想去):
1.Min stack
2.Implement queue using stack
首先你先寫1, 寫class MinStack，因為它能提供O(1)的stack getMin()
然後你再寫2, 寫class MyQueue，但當中用的stack s1,s2請用之前寫好的MinStack
最後是MyQueue的getMin() method，很簡單，return min(s1getMin(),s2.getMin())即可。複雜度方面因為s1.s2的getMin()是O(1)，所以queue的getMin()也是O(1)。
本篇code就不寫了，因為將之前寫過的兩個class組合即可。但話說我之前的code好像忘了error handling(^_^")。大家記得getMin()的時候要檢查一下size是否為0，做個error handling。
