~~~
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)
