Implement a MyQueue class which implements a queue using two stacks.

CC150-3.5.java

package POJ;

import java.util.ArrayList;
import java.util.Stack;


public class Main{

	/**
	 * 
	 *  3.5 Implement a MyQueue class which implements a queue using two stacks.
	 *  
	 *  Solution:
	 *  采用书中的方法
	 *  用两个stack，一个专门供enqueue （记做pushStack），一个专门用来dequeue （popStack），
	 *  每次enqueue，直接把元素push进pushStack，每次dequeue，优先从popStack中pop元素，如果
	 *  没有元素，就将pushStack中的元素全部pop进popStack，再pop元素。
	 *  
	 *  @Runtime & spaces
	 * 	runtime: 
	 * 	O(1) for push
	 *  O(N) for pop when data moving is necessary
	 * 	space: O(n)
	 * 
	 */
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		myQueue iQueue = new myQueue();
		for (int i = 0; i < 4; i++) {
			iQueue.push(i);
		}
		for (int i = 0; i < 4; i++) {
			System.out.println(iQueue.peek());
			iQueue.pop();
		}
		for (int i = 0; i < 4; i++) {
			iQueue.push(i+4);
		}
		for (int i = 0; i < 5; i++) {
			System.out.println(iQueue.peek());
			iQueue.pop();
		}
	}
}

class myQueue {
	Stack<Integer> stackNewest, stackOldest;

	public myQueue() {
		// TODO Auto-generated constructor stub
		stackNewest = new Stack<Integer>();
		stackOldest = new Stack<Integer>();
	}

	public int peek() {
		// TODO Auto-generated method stub
		shiftStacks();
		
		if(!stackOldest.isEmpty())
			return stackOldest.peek();
		else
			return -1;
	}

	public void pop() {
		// TODO Auto-generated method stub
		shiftStacks();
		if(!stackOldest.isEmpty())
		stackOldest.pop();
		else
			try {
				throw new Exception("no value");
			} catch (Exception e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
	}

	private void shiftStacks() {
		// TODO Auto-generated method stub
		if (stackOldest.isEmpty()) {
			while (!stackNewest.isEmpty())
				stackOldest.push(stackNewest.pop());
		}
	}

	public void push(int i) {
		// TODO Auto-generated method stub
		stackNewest.push(i);
	}
}