Java Coding Challenge - Implement Stack Using Two Queues

Author:

Introduction

The Stack Using Two Queues problem is a well-known coding challenge. The goal is to implement the basic operations of a stack—push(), pop(), peek(), and size()—using two queues. This challenge demonstrates a fundamental understanding of how data structures like stacks and queues can be manipulated to achieve different functionalities.

A stack follows the Last In, First Out (LIFO) principle, whereas a queue follows the First In, First Out (FIFO) principle. By using two queues, we can simulate the behavior of a stack while maintaining queue-based operations.

Problem Statement

You are required to implement a stack using two queues with the following operations:

  1. push(x): Add an element to the top of the stack.
  2. pop(): Remove and return the top element from the stack.
  3. peek(): Get the top element of the stack without removing it.
  4. size(): Return the number of elements in the stack.

Example:

  • Input:

    • push(1)
    • push(2)
    • peek() → returns 2
    • pop() → returns 2
    • isEmpty() → returns false

  • Output:

    • The last element pushed is 2, so both peek() and pop() return 2. The stack still contains 1, so isEmpty() returns false.

Approach

Using Two Queues

To implement a stack using two queues, we maintain two queues:

  1. Queue 1: Main queue for holding elements.
  2. Queue 2: Auxiliary queue to help with reordering elements during pop() and peek() operations.

Key Operations:

  • push(x): Push the element to the currently active queue.
  • pop(): Transfer all but the last element from the active queue to the other queue, then remove and return the last element.
  • peek(): Similar to pop(), but instead of removing the last element, return it.
  • size(): Return the current size of the stack.

Java Code Implementation

MyStackViaQueue Class

import java.util.ArrayDeque;
import java.util.EmptyStackException;
import java.util.Queue;

public class MyStackViaQueue<E> {

    private final Queue<E> queue1;  // Primary queue
    private final Queue<E> queue2;  // Auxiliary queue
    private E peek;                 // Holds the top element for efficient peek
    private int size;               // Holds the current size of the stack

    // Constructor to initialize the queues
    public MyStackViaQueue() {
        queue1 = new ArrayDeque<>();
        queue2 = new ArrayDeque<>();
    }

    // Push operation: Add an element to the stack
    public void push(E e) {
        if (!queue1.isEmpty()) {
            if (peek != null) {
                queue1.add(peek);
            }
            queue1.add(e);
        } else {
            if (peek != null) {
                queue2.add(peek);
            }
            queue2.add(e);
        }
        size++;
        peek = null;  // Reset peek
    }

    // Pop operation: Remove and return the top element from the stack
    public E pop() {
        if (size() == 0) {
            throw new EmptyStackException();
        }

        if (peek != null) {
            E e = peek;
            peek = null;
            size--;
            return e;
        }

        E e;
        if (!queue1.isEmpty()) {
            e = switchQueue(queue1, queue2);
        } else {
            e = switchQueue(queue2, queue1);
        }

        size--;
        return e;
    }

    // Peek operation: Return the top element without removing it
    public E peek() {
        if (size() == 0) {
            throw new EmptyStackException();
        }

        if (peek == null) {
            if (!queue1.isEmpty()) {
                peek = switchQueue(queue1, queue2);
            } else {
                peek = switchQueue(queue2, queue1);
            }
        }

        return peek;
    }

    // Return the size of the stack
    public int size() {
        return size;
    }

    // Helper method to switch elements between queues
    private E switchQueue(Queue<E> from, Queue<E> to) {
        while (from.size() > 1) {
            to.add(from.poll());
        }
        return from.poll();  // Return the last element (top of the stack)
    }
}

Explanation

  1. push(x):
    • The element is added to whichever queue (either queue1 or queue2) is currently active.
    • The peek is reset to null to ensure the correct element is retrieved during peek() and pop() operations.
public void push(E e) {
    if (!queue1.isEmpty()) {
        if (peek != null) {
            queue1.add(peek);
        }
        queue1.add(e);
    } else {
        if (peek != null) {
            queue2.add(peek);
        }
        queue2.add(e);
    }
    size++;
    peek = null;
}
  1. pop():
    • Transfer all elements from the active queue (either queue1 or queue2) to the other queue, except for the last element.
    • The last element is then removed and returned as the result of the pop() operation.
public E pop() {
    if (size() == 0) {
        throw new EmptyStackException();
    }

    if (peek != null) {
        E e = peek;
        peek = null;
        size--;
        return e;
    }

    E e;
    if (!queue1.isEmpty()) {
        e = switchQueue(queue1, queue2);
    } else {
        e = switchQueue(queue2, queue1);
    }

    size--;
    return e;
}
  1. peek():
    • Similar to pop(), but instead of removing the last element, it stores the last element in the peek variable and returns it.
public E peek() {
    if (size() == 0) {
        throw new EmptyStackException();
    }

    if (peek == null) {
        if (!queue1.isEmpty()) {
            peek = switchQueue(queue1, queue2);
        } else {
            peek = switchQueue(queue2, queue1);
        }
    }

    return peek;
}
  1. size():
    • Returns the size of the stack, which is maintained as a variable and updated during each push() and pop() operation.
public int size() {
    return size;
}

Main Class to Test the Stack Implementation

package coding.challenge;

public class Main {

    public static void main(String[] args) {

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

        stack.push(25);
        stack.push(35);
        stack.push(15);

        System.out.println("Size: " + stack.size());
        System.out.println("Peek: " + stack.peek());
        System.out.println("Size: " + stack.size());
        System.out.println("Pop: " + stack.pop());
        System.out.println("Size: " + stack.size());
        System.out.println("Peek: " + stack.peek());
        System.out.println("Peek: " + stack.peek());
        System.out.println("Size: " + stack.size());
        System.out.println("Push 17");
        stack.push(17);
        System.out.println("Push 12");
        stack.push(12);
        System.out.println("Peek: " + stack.peek());
        System.out.println("Peek: " + stack.peek());
        System.out.println("Size: " + stack.size());
        System.out.println("Pop: " + stack.pop());
        System.out.println("Size: " + stack.size());
        System.out.println("Pop: " + stack.pop());
        System.out.println("Size: " + stack.size());
        System.out.println("Push 55");
        stack.push(55);
        System.out.println("Size: " + stack.size());
        System.out.println("Peek: " + stack.peek());
        System.out.println("Peek: " + stack.peek());
        System.out.println("Size: " + stack.size());
        System.out.println("Pop: " + stack.pop());
        System.out.println("Size: " + stack.size());
        System.out.println("Pop: " + stack.pop());
        System.out.println("Size: " + stack.size());
        System.out.println("Peek: " + stack.peek());
        System.out.println("Pop: " + stack.pop());
        System.out.println("Size: " + stack.size());
    }
}

Example Output:

Size: 3
Peek: 15
Size: 3
Pop: 15
Size: 2
Peek: 35
Peek: 35
Size: 2
Push 17
Push 12
Peek: 12
Peek: 12
Size: 4
Pop: 12
Size: 3
Pop: 17
Size: 2
Push 55
Size: 3
Peek: 55
Peek: 55
Size: 3
Pop: 55
Size: 2
Pop: 35
Size: 1
Peek: 25
Pop: 25


Size: 0

Time Complexity

  • Push Operation: O(1), as elements are added to the active queue without moving elements.
  • Pop Operation: O(n), where n is the number of elements in the stack. All elements are transferred from one queue to another during pop().
  • Peek Operation: O(n), similar to pop(), as all elements are transferred.
  • Size Operation: O(1), as the size is tracked by a variable.

Space Complexity

  • Space Complexity: O(n), where n is the number of elements in the stack, since both queues store elements.

Conclusion

In this coding challenge, we implemented a stack using two queues. We used two queues to simulate the Last In, First Out (LIFO) behavior of a stack. This approach demonstrates how we can manipulate queues to behave like a stack, providing efficient push() operations while handling the complexity during pop() and peek() operations.

Comments

Post a Comment

Leave Comment