Implement Stack using Queue (using single queue)

Dec 18, 2024 • 4 mins read
Hero Image

Problem Overview

LeetCode Problem Title: Implement Stack using Queues

Difficulty Level: Easy

This problem requires you to implement the functionality of a stack using one or more queues. A stack is a Last In, First Out (LIFO) data structure, whereas a queue is a First In, First Out (FIFO) data structure. To solve this problem, you need to simulate the stack operations using queue operations.

Understanding the Problem

A stack supports the following primary operations:

  • push(x): Pushes an element x onto the stack.
  • pop(): Removes the element on top of the stack.
  • top(): Retrieves the element on top of the stack.
  • empty(): Checks if the stack is empty.

On the other hand, a queue supports the following operations:

  • enqueue(x): Adds element x to the back of the queue.
  • dequeue(): Removes element from the front of the queue.
  • front(): Gets the element at the front of the queue.
  • isEmpty(): Checks if the queue is empty.

Your task is to mimic the stack operations utilizing the operations provided by queues.

Key DSA Concepts and Theory

Stack

A Stack is a collection that allows you to add and remove elements in a particular order. The order is LIFO: the last element added is the first one to be removed. The stack operations can be briefly described as:

  • Push: Add an element to the top.
  • Pop: Remove the element from the top.
  • Top/Peek: View the top element without removing it.

Queue

A Queue is a collection that allows elements to be added at the back and removed from the front. The order is FIFO: the first element added is the first one to be removed:

  • Enqueue: Add an element to the back.
  • Dequeue: Remove an element from the front.

Using Queues to Implement Stacks

The challenge is to provide the effect of LIFO using FIFO. This can be achieved in two possible ways:

  1. Using one queue with costly push operations.
  2. Using two queues with costly pop operations.

Solution Approach

Approach 1: Single Queue with Costly Push

Algorithm

  1. Push(x): To simulate pushing an element onto the stack, enqueue the new element, followed by dequeuing all proceeding elements from the queue and enqueueing them back. This ensures the new element is at the front.

  2. Pop(): The front of the queue is the top of the stack; retrieve it and remove.

  3. Top(): Simply return the front of the queue, which is the current top of the stack.

  4. Empty(): Check if the queue is empty.

C++ Implementation

#include <queue>
using namespace std;

class MyStack {
public:
    queue<int> q;
    
    MyStack() {}
    
    void push(int x) {
        q.push(x);
        for (int i = 0; i < q.size() - 1; ++i) {
            q.push(q.front());
            q.pop();
        }
    }
    
    int pop() {
        int topElement = q.front();
        q.pop();
        return topElement;
    }
    
    int top() {
        return q.front();
    }
    
    bool empty() {
        return q.empty();
    }
};

Java Implementation

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    Queue<Integer> q;
    
    public MyStack() {
        q = new LinkedList<>();
    }
    
    public void push(int x) {
        q.add(x);
        for (int i = 0; i < q.size() - 1; ++i) {
            q.add(q.remove());
        }
    }
    
    public int pop() {
        return q.remove();
    }
    
    public int top() {
        return q.peek();
    }
    
    public boolean empty() {
        return q.isEmpty();
    }
}

Approach 2: Two Queues with Costly Pop

Algorithm

  1. Push(x): Enqueue the element in queue1.

  2. Pop(): Transfer all elements but the last from queue1 to queue2, then dequeue the last element left in queue1.

  3. Top(): Similar to pop, but instead of dequeuing the last element, return it.

  4. Empty(): Check if queue1 is empty.

This approach uses two queues but offers a more balanced runtime distribution in operations at the expense of increased space utilization.

Time and Space Complexity Analysis

For both approaches:

  • Time Complexity:

    • push: O(n) due to rearranging elements.
    • pop, top, empty: O(1).

  • Space Complexity:

    • Approach 1: Uses O(n) additional space for queue storage.
    • Approach 2: Uses O(n) space across two queues.

Common Mistakes to Avoid

  • Confusing the operations of stack and queue. Ensure to maintain the correct order of operations.
  • Implementing top and pop incorrectly could lead to removing wrong elements.

Similar Problems on LeetCode

    1. Implement Queue using Stacks
    1. Evaluate Reverse Polish Notation
    1. Implement Stack using Queues (this problem)

Additional Resources and References