How implement a Queue using only One (1) Stack?

Technology Community › Category: Queues › How implement a Queue using only One (1) Stack?

VietMX Staff asked 3 years ago

Problem

I know how to do that with 2 stacks but how to implement it with one?

Tricky question.

You can “cheat” by using recursive function calls to pop the stack, then you push the item being queued, then as the recursive calls unwind you push what was popped. But this is really two stacks, because the function call stack counter is a stack.

Following is the implementation:

During Enqueue operation, we can straight away push the element into the stack.
During Dequeue operation,
- Pop all the elements from a Stack recursively until Stack size is equal to 1.
- If Stack size = 1, Pop item from Stack, and return the same item.
- Push all popped element back to Stack.

Implementation

public class QueueUsingSingleStack {

    Stack<Integer> stack = new Stack<>();

    private void enqueue(int i) {
        stack.push(i);
    }

    private int dequeue() throws Exception {
        if (stack.size() == 0)
            throw new Exception("Queue is Empty");

        if (stack.size() == 1)
            return stack.pop();

        int data = stack.pop();
        int retVal = dequeue();
        stack.push(data);
        return retVal;
    }

    public static void main(String[] args) throws Exception {
        QueueUsingSingleStack queue = new QueueUsingSingleStack();
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);

        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());

    }
}

Question Tags: Queues, Senior Level