Implementing Queue using Stacks

In the previous lessons, we have discussed different implementations of the queue data structure using arrays and linked lists. Now, let's explore another interesting approach - implementing a queue using stacks.

Approach

To implement a queue using stacks, we can use two stacks: one for the enqueue operation and one for the dequeue operation. Let's call them stack1 and stack2, respectively.

Here's a basic outline of the queue implementation using stacks:

1. When an element needs to be enqueued, we simply push it onto stack1.
2. For the dequeue operation, we first check if both stack1 and stack2 are empty. If they are, then the queue is empty and we throw an exception.
3. If stack2 is empty, we transfer all the elements from stack1 to stack2 in reverse order, so that the first element pushed onto stack1 becomes the first element at the top of stack2 (which ensures FIFO order).
4. Finally, we pop and return the top element from stack2 as the dequeued element.

Here is a Java implementation of a queue using stacks:

1{{code}}

Example

Let's enqueue elements 1, 2, and 3 to the queue and then dequeue an element. The internal state of stack1 and stack2 would be as follows:

1stack1: [1, 2, 3]
2stack2: []

After dequeuing an element, the internal state would be:

1stack1: []
2stack2: [3, 2]

The dequeued element would be 1.

By implementing a queue using stacks, we can effectively achieve the FIFO behavior of a queue using the LIFO behavior of stacks. This approach can be useful in scenarios where a stack is readily available or preferred over other data structures. It's important to note that the time complexity of both the enqueue and dequeue operations is O(n), where n is the number of elements in the queue, due to the transfer of elements between the two stacks. However, the space complexity is O(n).

xxxxxxxxxx

}

class QueueUsingStack {

​

    private Stack<Integer> stack1;

    private Stack<Integer> stack2;

​

    public QueueUsingStack() {

        stack1 = new Stack<>();

        stack2 = new Stack<>();

    }

​

    public void enqueue(int num) {

        stack1.push(num);

    }

​

    public int dequeue() {

        if (stack1.isEmpty() && stack2.isEmpty()) {

            throw new NoSuchElementException("Queue is empty");

        }

​

        if (stack2.isEmpty()) {

            while (!stack1.isEmpty()) {

                stack2.push(stack1.pop());

            }

        }

​

        return stack2.pop();

    }

​

    public boolean isEmpty() {