~~~
package stackAndQueue;
import java.util.Stack;
import org.junit.Test;
/**
* 由兩個棧組成的隊列：TwoStackQueue【2】
*
* 【編寫一個類，用兩個棧實現隊列，支持隊列的基本操作(add、poll、peek)】
*
* 設計思路：棧-先進后出，隊列-先進先出。用兩個棧把順序反過來。
*
* stackPush只管進棧，stackPop只管出棧且【僅當】其為空時，將stackPush的元素【全部】轉移到stackPop。
*
* @author xiaofan
*/
public class TwoStackQueue {
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;
public TwoStackQueue() {
this.stackPush = new Stack<Integer>();
this.stackPop = new Stack<Integer>();
}
public void add(int e) {
this.stackPush.push(e);
}
public int poll() {
tranfer();
return this.stackPop.pop();
}
public int peek() {
tranfer();
return this.stackPop.peek();
}
private void tranfer() {
if (this.stackPop.empty()) {
if (this.stackPush.isEmpty()) { // isEmpty是Stack繼承的Vector的方法
throw new RuntimeException("Your queue is empty.");
}
while (!this.stackPush.empty()) { // empty是Stack自帶的方法
this.stackPop.push(this.stackPush.pop());
}
}
}
/////// 測試方法//////
@Test
public void test() {
TwoStackQueue queue = new TwoStackQueue();
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(3);
queue.add(4);
System.out.println("peek:" + queue.peek());
while (true) { // 未重寫empty方法，只能這樣遍歷
try {
System.out.println(queue.poll());
} catch (Exception e) {
break;
}
}
TwoStackQueue queue1 = new TwoStackQueue();
queue1.peek(); // java.lang.RuntimeException: Your queue is empty.
}
}
~~~
代碼地址：[https://github.com/zxiaofan/Algorithm/tree/master/src/stackAndQueue](https://github.com/zxiaofan/Algorithm/tree/master/src/stackAndQueue)
