Question

link

Given two queues with their standard operations (enqueue, dequeue, isempty, size), implement a stack with its standard operations (pop, push, isempty, size).

Analysis

There should be TWO versions of the solution.

  1. Version A: The stack should be efficient when pushing an item.

  2. Version B: The stack should be efficient when popping an item.

Version A

The stack should be efficient when pushing an item.

  1. push:

    1. enqueue in queue1

  2. pop:

    1. while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2
    2. dequeue and return the last item of queue1, then switch the names of queue1 and queue2

Version B

The stack should be efficient when popping an item.

  1. push:

    1. enqueue in queue2
    2. enqueue all items of queue1 in queue2, then switch the names of queue1 and queue2

  2. pop:

    1. deqeue from queue1

reference

Learn and compare with another question [Question] Implement Queue Using Stacks.

Code

written by me, Version A. 

public class StackBuiltWithTwoQueue {

    // http://stackoverflow.com/questions/688276/implement-stack-using-two-queues

    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();

    public static void main(String[] args) {
        StackBuiltWithTwoQueue stack = new StackBuiltWithTwoQueue();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());
        stack.push(4);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        stack.push(5);
        stack.push(6);
        stack.push(7);
        stack.push(8);
        stack.push(9);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }

    public void push(int val) {
        q1.offer(val);
    }

    public int pop() {
        if (q1.isEmpty()) {
            System.out.print("Stack is empty now ");
            return -1;
        }
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        int topVal = q1.poll();
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
        return topVal;
    }
}