Tuesday, July 07, 2015

Implement Queue using Stacks

Picked up from http://www.geeksforgeeks.org/queue-using-stacks/

enQueue(q,  x)
  1) Push x to stackin (assuming size of stacks is unlimited).

deQueue(q)
  1) If both stacks are empty then error.
  2) If stackout is empty
       While stack1 is not empty, push everything from satckin to stackout.
  3) Pop the element from stackout and return it.


import java.util.Stack;

class MyQueue {
 Stack<Integer> stackIn = new Stack<Integer>();
 Stack<Integer> stackOut = new Stack<Integer>();
    // Push element x to the back of queue.
    public void push(int x) {
        stackIn.push(x);
    }

    // Removes the element from in front of queue.
    public void pop() {
        if (stackOut.isEmpty()){
            //if out stack is empty, then moving elements to stackOut
            //benefit of this solution is it moves aroudn the elements only when the stack out is empty
            while(!stackIn.isEmpty())
             stackOut.push(stackIn.pop());
        }

        stackOut.pop();
    }

    // Get the front element.
    public int peek() {
     if (stackOut.isEmpty()){
            while(!stackIn.isEmpty())
             stackOut.push(stackIn.pop());

        }
        //benefit of this solution is it moves aroudn the elements only when the stack out is empty
        Integer o = stackOut.peek();
     return o.intValue();
        
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}

No comments: