http://blog.csdn.net/sinat_30472685/article/details/70157227

1兩個棧實現一個隊列

1.原理分析：

隊列的主要操作有兩個：入隊操作和出隊操作，出隊時從隊頭出，入隊是從隊尾插入，入隊的操作和入棧的操作類似，而最關鍵的問題是出隊操作，要出隊列的是隊列的第一個元素，而出棧的是棧的棧頂元素，所以我們可以這樣：

? ? ? ?假設兩個棧A和棧B，A主要用來處理入隊操作，B用于處理出隊操作。入隊操作和入棧操作類似，直接將元素壓入棧即可。出隊的時候，實現我們假設棧B為空，則要把棧A的第一個元素（即棧底元素）彈出，直接從A彈出這是不可能的，但如果我們把棧A里面的元素的順序逆過來，這樣直接用棧彈出棧頂元素即可，所以我們可以把棧A的元素全部彈出來，并俺順序壓入棧B中，這樣每次棧B彈出的棧頂元素就是棧A相對應的棧底元素，就是出隊操作。若B不為空，則代表之前從A復制過來的元素還沒有完全彈出，要出棧的時候直接彈出即可。若棧B的元素都彈出來了，就需要從A中補充。

?2.總結操作就是： ? ?

入隊：將元素進棧A

出隊：判斷棧B是否為空，如果為空，則將棧A中所有元素pop，并push進棧B，棧B出棧；如果不為空，棧B直接出棧。

3.Java代碼實現

1. import?java.util.Stack;??
2. ??
3. public?class?StacksToQueue???
4. {??
5. ?????Stack<Integer>?stack1=new?Stack<Integer>()?;??
6. ?????Stack<Integer>?stack2=new?Stack<Integer>();??
7. ?????public?void?addToTail(int?x)//添加元素到隊尾???--進隊---??
8. ?????{??
9. ?????????stack1.push(x);??
10. ???????????
11. ?????}??
12. ?????public?int?deleteHead()//刪除對首??????--出隊---????不需是隊不為空才能刪除呀~~~~??
13. ?????{??
14. ?????????if(?pSize()!=0)//隊列不為空??
15. ?????????{??
16. ?????????????if(stack2.isEmpty())//若stack2為空，則把stack1全部加入stack2??
17. ?????????????????stack1ToStack2();???
18. ?????????????return??stack2.pop();??
19. ???????????????
20. ?????????}??
21. ?????????else??
22. ?????????{??
23. ?????????????System.out.println("隊列已經為空，不能執行從隊頭出隊");??
24. ?????????????return?-1;??
25. ?????????}??
26. ???????????
27. ?????}??
28. ???????
29. ?????public?void?stack1ToStack2()//把stack1全部放入stack2??
30. ?????{??
31. ?????????while(!stack1.isEmpty())???
32. ?????????????stack2.push(stack1.pop());??
33. ?????}??
34. ???????
35. ?????public?int?pSize()//隊列size()??
36. ?????{??
37. ?????????return??stack1.size()+stack2.size();//兩個都為空隊列才是空??
38. ?????}??
39. ? ?
40. } ? ?

2兩個隊列實現一個棧