Implement Stack using Two Queues (with efficient push)

Technology Community › Category: Queues › Implement Stack using Two Queues (with efficient push)

VietMX Staff asked 4 years ago

Problem

Given two queues with their standard operations (enqueue, dequeue, isempty, size), implement a stack with its standard operations (pop, push, isempty, size). The stack should be efficient when pushing an item.

Given we have queue1 and queue2:

push – O(1):

enqueue in queue1

pop – O(n):

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

Complexity Analysis

If queue is implemented as linked list the enqueue operation has O(1) time complexity.

Implementation

public Stack<E> {
    private Queue<E> q1 = new Queue<E>();
    private Queue<E> q2 = new Queue<E>();

    public void push(E x) {
        q1.enqueue(x);
    }

    public E pop() {
        while (q1.size() > 1) {
            q2.enqueue(q1.dequeue());
        }
        E pop = q1.dequeue();
        Queue<E> temp = q1;
        q1 = q2;
        q2 = temp;
        return pop;
    }
}

Question Tags: Junior Level, Queues