How to use stacks to implement a queue in Java

Key takeaways:
A queue operates on FIFO, while a stack operates on LIFO. Stimulating queue behavior using stacks requires careful handling.
Using two stacks achieves queue functionality while maintaining correctness.
The costly enqueue approach prioritizes efficient dequeue operations, making it ideal for frequent dequeues.
The costly dequeue approach optimizes enqueues, suiting scenarios with more frequent enqueue operations.
The trade-off between approaches depends on the balance of enqueue and dequeue operations.

In computer science, data structures like stacks and queues play a fundamental role in solving various computational problems. A queue operates on the principle of First In, First Out (FIFO), where the first element added is the first to be removed, while a stack operates on Last In, First Out (LIFO), where the most recently added element is removed first. Now, we will understand solutions to a coding interview problem where you are constrained to implement the queue behavior using only stacks.

Problem statement

Implement a queue using stacks. Your task is to use two stacks to simulate the behavior of a queue, implementing the fundamental operations:

Enqueue (adding an element to the end of the queue).
Dequeue (removing an element from the front of the queue).

Ensure that the solution maintains the expected behavior of a queue while utilizing only stack operations for implementation.

Solution

To implement a queue using two stacks, we will explore two different approaches.

The first approach focuses on making the enqueue operation costly, which means that elements are added to the queue with a higher time complexity or overhead, making it more expensive to insert items into the queue.
The second approach, on the other hand, aims to make the dequeue operation costly. Removing elements from the queue requires more time or resources, increasing the complexity of extracting items from the queue.

Queue implementation using two stacks: Costly enqueue approach

This algorithm uses two stacks to implement a queue, where the enqueue operation is made costly to ensure that the dequeue operation is efficient. Elements are transferred between the stacks during enQueue to maintain the correct order, while deQueue simply involves popping from one stack.

enQueue operation:
1. Transfer all elements from stack1 to stack2.
2. Push the new element onto stack1.
3. Transfer all elements back from stack2 to stack1.
deQueue operation: Pop an element directly from stack1. This makes the dequeue operation efficient since no additional transfer is required.

Now, let’s look at the following illustration to get a better understanding of the solution:

import java.util.Stack;
class Solution {
    static class Queue {
        Stack<Integer> stack1;
        Stack<Integer> stack2;
        public Queue() {
            stack1 = new Stack<>();
            stack2 = new Stack<>();
        }
    }
    // Push an element onto a stack
    static void push(Stack<Integer> stack, int value) {
        stack.push(value);
    }
    // Pop an element from a stack
    static int pop(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            System.out.println("Stack Underflow");
            System.exit(0);
        }
        return stack.pop();
    }
    // Enqueue an element into the queue (Costly Operation)
    static void enQueue(Queue q, int x) {
        // Step 1: Transfer all elements from stack1 to stack2
        while (!q.stack1.isEmpty()) {
            push(q.stack2, pop(q.stack1));
        }
        // Step 2: Push the new element onto stack1
        push(q.stack1, x);
        // Step 3: Transfer all elements back from stack2 to stack1
        while (!q.stack2.isEmpty()) {
            push(q.stack1, pop(q.stack2));
        }
    }
    // Dequeue an element from the queue (Efficient Operation)
    static int deQueue(Queue q) {
        if (q.stack1.isEmpty()) {
            System.out.println("Queue is empty");
            System.exit(0);
        }
        // Simply pop from stack1
        return pop(q.stack1);
    }
    // Helper function to display the current state of the queue
    static void printQueue(Queue q) {
        System.out.print("Front -> ");
    
        // Print elements directly from stack1 in reverse order of stack iteration
        for (int i = q.stack1.size() - 1; i >= 0; i--) {
            System.out.print(q.stack1.get(i) + " ");
        }
    
        System.out.println("<- Rear");
    }
    public static void main(String[] args) {
        // Create a new Queue instance
        Queue q = new Queue();
        // Show the empty queue
        System.out.println("Queue initially:");
        printQueue(q);
        // Perform enqueue operations
        enQueue(q, 1);
        System.out.println("\nQueue after enqueuing 1:");
        printQueue(q);
        enQueue(q, 2);
        System.out.println("\nQueue after enqueuing 2:");
        printQueue(q);
        enQueue(q, 3);
        System.out.println("\nQueue after enqueuing 3:");
        printQueue(q);
        // Perform dequeue operations
        System.out.println("\nDequeued elements:");
        System.out.print(deQueue(q) + " ");
        System.out.println("\nQueue after dequeuing 1:");
        printQueue(q);
        System.out.print(deQueue(q) + " ");
        System.out.println("\nQueue after dequeuing 2:");
        printQueue(q);
        System.out.print(deQueue(q) + " ");
        System.out.println("\nQueue after dequeuing 3:");
        printQueue(q);
        // Test dequeue from an empty queue
        System.out.println("\nAttempting to dequeue from an empty queue:");
        try {
            System.out.println(deQueue(q));
        } catch (Exception e) {
            System.out.println("Queue is empty.");
        }
    }
}

Efficient queue implementation using two stacks: costly enqueue approach

Time complexity

enQueue operation: In the worst case, we transfer all elements between stacks, which takes $O(n)$ time, where $n$ is the number of elements in stack1.
deQueue operation: The deQueue operation pops an element directly from stack1, which takes $O(1)$ time.

Space complexity

We use two stacks (stack1 and stack2), and both can hold at most n elements, where n is the number of elements in the queue at any given time.

Queue implementation using two stacks: Costly dequeue approach

In this approach, the deQueue operation is designed to be more time-intensive. During the enQueue operation, new elements are simply pushed onto the top of stack1, making it efficient. However, when performing the deQueue operation, if stack2 is empty, all elements from stack1 are transferred to stack2 to reverse their order. The top element of stack2 is then returned, ensuring the correct queue behavior.

Let’s look at the code for the above solution discussed.

import java.util.Stack;
class Solution {
    static class Queue {
        Stack<Integer> stack1;
        Stack<Integer> stack2;
        // Constructor to initialize the stacks
        Queue() {
            stack1 = new Stack<>();
            stack2 = new Stack<>();
        }
    }
    // Push an element onto a stack
    static void push(Stack<Integer> stack, int value) {
        stack.push(value);
    }
    // Pop an element from a stack
    static int pop(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            System.out.println("Stack Underflow");
            System.exit(0);
        }
        return stack.pop();
    }
    // Enqueue an element into the queue
    static void enQueue(Queue q, int x) {
        push(q.stack1, x);
    }
    // Dequeue an element from the queue
    static int deQueue(Queue q) {
        // If both stacks are empty, the queue is empty
        if (q.stack1.isEmpty() && q.stack2.isEmpty()) {
            System.out.println("Queue is empty");
            System.exit(0);
        }
        // If stack2 is empty, transfer elements from stack1 to stack2
        if (q.stack2.isEmpty()) {
            while (!q.stack1.isEmpty()) {
                push(q.stack2, pop(q.stack1));
            }
        }
        // Pop the element from stack2
        return pop(q.stack2);
    }
    // Helper function to display the current state of the queue
    static void printQueue(Queue q) {
        Stack<Integer> temp = new Stack<>();
        // Move all elements from stack1 to a temporary stack
        while (!q.stack1.isEmpty()) {
            temp.push(q.stack1.pop());
        }
        // Print elements in the queue order
        System.out.print("Front -> ");
        while (!temp.isEmpty()) {
            int value = temp.pop();
            System.out.print(value + " ");
            q.stack1.push(value); // Restore elements back to stack1
        }
        System.out.println("<- Rear");
    }
    public static void main(String[] args) {
        // Create a new Queue instance
        Queue q = new Queue();
        // Show the empty queue
        System.out.println("Queue initially:");
        printQueue(q);
        // Perform enqueue operations
        enQueue(q, 1);
        System.out.println("\nQueue after enqueuing 1:");
        printQueue(q);
        enQueue(q, 2);
        System.out.println("\nQueue after enqueuing 2:");
        printQueue(q);
        enQueue(q, 3);
        System.out.println("\nQueue after enqueuing 3:");
        printQueue(q);
        // Perform dequeue operations
        System.out.println("\nDequeued elements:");
        System.out.print(deQueue(q) + " ");
        System.out.println("\nQueue after dequeuing 1:");
        printQueue(q);
        System.out.print(deQueue(q) + " ");
        System.out.println("\nQueue after dequeuing 2:");
        printQueue(q);
        System.out.print(deQueue(q) + " ");
        System.out.println("\nQueue after dequeuing 3:");
        printQueue(q);
        // Test dequeue from an empty queue
        System.out.println("\nAttempting to dequeue from an empty queue:");
        try {
            System.out.println(deQueue(q));
        } catch (Exception e) {
            System.out.println("Queue is empty.");
        }
    }
}

Efficient queue implementation using two stacks: costly dequeue approach

Time complexity

enQueue operation: The enQueue operation simply pushes an element onto stack1, which takes $O(1)$ time.
deQueue operation: In the worst case, the deQueue operation takes $O(n)$ when all elements need to be transferred from stack1 to stack2.

Space complexity

The space complexity is dominated by the two stacks (stack1 and stack2), each of which can hold at most $n$ elements at any given time, where $n$ is the number of elements in the queue. So, the space complexity is $O(n)$ .

Additional resources

To find other coding interview questions like this, you may consider the course “Grokking the Coding Interview Patterns.” This course focuses on essential coding patterns and algorithms frequently tested in technical interviews, offering hands-on practice and in-depth explanations. It’s an excellent way to build a solid foundation for tackling coding interview questions and mastering patterns like sliding windows, two pointers, and subsets.

To further strengthen your coding skills and boost your technical interview preparation, here are some LeetCode problems to practice:

To further strengthen your knowledge about stacks and queues, here are some Educative answers to read:

Frequently asked questions

Haven’t found what you were looking for? Contact Us

Why use two stacks to implement a queue?

Using two stacks allows us to simulate the FIFO behavior of a queue with the LIFO property of stacks by rearranging the order of elements.

What are the differences between the two approaches?

Approach 1 makes enQueue costly with $O(n)$ complexity but optimizes deQueue to $O(1)$ . Approach 2 does the opposite, making deQueue costly and enQueue efficient.

When should I choose Approach 1 or Approach 2?

Choose Approach 1 when frequent deQueue operations are expected and Approach 2 when enQueue operations dominate.

What are the practical trade-offs of these approaches?

Both approaches require additional memory for two stacks, but they demonstrate flexibility in utilizing stack operations to achieve queue functionality.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)