cc150_3.5

gistfile1.java

/*
 * 3.5 Implement a MyQueue class which implements a queue using two stacks
 * Algorithm
 * use one Stack for  Enqueue -----EnQueueStack
 * use another Stack for Dequeue----DeQueueStack.
 * if DeQueueStack is  empty  then  pop  from EnqueueStack and  push to  DequeueStac one by one.
 * O(N) and O(N)
 */
public class MyQueueByTwoStacks {

	public static void main(String[] args) {
		MyQueue testQ = new MyQueue();
		System.out.println(testQ.deQueue());
		testQ.enQueue(15);
		testQ.enQueue(16);
		testQ.enQueue(17);
		testQ.enQueue(18);
		System.out.println(testQ.deQueue());
		System.out.println(testQ.deQueue());
		System.out.println(testQ.deQueue());
		System.out.println(testQ.deQueue());
		
	}

}

class MyQueue {
	QueStack enQueueStack;
	QueStack deQueueStack;
	public MyQueue(){
		enQueueStack = new QueStack();
		deQueueStack = new QueStack();
	}
	public  void  enQueue(int data){
		enQueueStack.push(data);
	}
	public int deQueue(){
		reverseStacks(enQueueStack,deQueueStack);
		return deQueueStack.pop();
		
	}
	private void reverseStacks(QueStack stack1, QueStack stack2) {
		while(stack1.top!=null) {
			stack2.push(stack1.pop());
		}
		
	}
}

class QueueNode{
	int data;
	QueueNode next;
	public QueueNode(int data){
		this.data = data;
	}
}
class QueStack{
	QueueNode top;
	
	public QueStack(){
		top =null;
	}
	public  void push(int data){
		QueueNode newNode = new QueueNode(data);
		newNode.next= top;
		top = newNode;
	}
	public int pop(){
		if(top!=null){
			int popdata = top.data;
			top = top.next;
			return popdata;
		}
		return Integer.MIN_VALUE;
	}
	
}