Implement Queue using Stack Data Structure

Queues are a fundamental data structure that follow the First-In-First-Out (FIFO) principle. This principle is exactly opposite of Last-In-First-Out (LIFO) principle on which Stack data structure is based on. While queues can be implemented directly using an array or a linked list, they can also be constructed using two stacks.

Implementing a queue with stacks involves maintaining two stacks, where one stack is used to store the elements, while the other stack is used to reverse the order of the elements. Reversing the order of elements in the stack makes sure that among all the elements present in the stack, the most oldest or first element added to the stack will always stay on top of the stack. Similarly the next oldest element is the next topmost element in the stack and so on. The recently added element should be at the bottom of the stack. This ensures that the first element added will be the first element to be popped out, similar to how the Queue behaves.

Below is a basic program which demonstrates implementing a queue data structure using two stack objects:


class Queue:
  def __init__(self):
    # Initialize two empty stacks to implement the queue
    self.stack1 = []
    self.stack2 = []

  def enqueue(self, item):
    """
    Adds an item to the tail end of the Queue.
    """
    # Move all elements from stack1 to stack2
    while self.stack1:
      self.stack2.append(self.stack1.pop())

    # Push the new item to stack1
    self.stack1.append(item)

    # Move all elements back from stack2 to stack1
    while self.stack2:
      self.stack1.append(self.stack2.pop())

  def dequeue(self):
    """
    Removes and returns the front item from the Queue.
    """
    if not self.stack1:
      raise IndexError("Queue is empty")
    return self.stack1.pop()

  def peek(self):
    """
    Returns the front item from the Queue without removing it.
    """
    if not self.stack1:
      raise IndexError("Queue is empty")
    # Return the top most element in Stack without popping
    return self.stack1[-1]

  def is_empty(self):
    """
    Returns True if the stack is empty, False otherwise.
    """
    return not self.stack1

# Let's now test the Queue implementation
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print("Dequeuing front element: ", queue.dequeue())  # Output: 1
print("Peeking front element: ", queue.peek())  # Output: 2
print("Dequeuing front element: ", queue.dequeue())  # Output: 2
print("Is Queue empty?: ", queue.is_empty())  # Output: False, since item 3 is still in queue


#include <iostream>
#include <stdexcept>
#include <stack>

class Queue {
private:
  std::stack<int> stack1;
  std::stack<int> stack2;

public:
  void enqueue(int item) {
    /**
     * Adds an item to the tail end of the Queue.
     */
    // Move all elements from stack1 to stack2
    while (!stack1.empty()) {
      stack2.push(stack1.top());
      stack1.pop();
    }

    // Push the new item to stack1
    stack1.push(item);

    // Move all elements back from stack2 to stack1
    while (!stack2.empty()) {
      stack1.push(stack2.top());
      stack2.pop();
    }
  }

  int dequeue() {
    /**
     * Removes and returns the front item from the Queue.
     */
    if (stack1.empty()) {
      throw std::runtime_error("Queue is empty");
    }
    int frontElement = stack1.top();
    stack1.pop();
    return frontElement;
  }

  int peek() {
    /**
     * Returns the front item from the Queue without removing it.
     */
    if (stack1.empty()) {
      throw std::runtime_error("Queue is empty");
    }
    // Return the top most element in Stack without popping
    return stack1.top();
  }

  bool is_empty() {
    /**
     * Returns True if the stack is empty, False otherwise.
     */
    return stack1.empty();
  }
};

int main() {
  Queue queue;
  queue.enqueue(1);
  queue.enqueue(2);
  queue.enqueue(3);
  std::cout << "Dequeuing front element: " << queue.dequeue() << std::endl; // Output: 1
  std::cout << "Peeking front element: " << queue.peek() << std::endl; // Output: 2
  std::cout << "Dequeuing front element: " << queue.dequeue() << std::endl; // Output: 2
  std::cout << "Is Queue empty?: " << std::boolalpha << queue.is_empty() << std::endl; // Output: false, since item 3 is still in queue
  return 0;
}


class Queue {
  constructor() {
    this.stack1 = [];
    this.stack2 = [];
  }

  enqueue(item) {
    /**
     * Adds an item to the tail end of the Queue.
     */
    // Move all elements from stack1 to stack2
    while (this.stack1.length > 0) {
      this.stack2.push(this.stack1.pop());
    }

    // Push the new item to stack1
    this.stack1.push(item);

    // Move all elements back from stack2 to stack1
    while (this.stack2.length > 0) {
      this.stack1.push(this.stack2.pop());
    }
  }

  dequeue() {
    /**
     * Removes and returns the front item from the Queue.
     */
    if (this.stack1.length === 0) {
      throw new Error("Queue is empty");
    }
    return this.stack1.pop();
  }

  peek() {
    /**
     * Returns the front item from the Queue without removing it.
     */
    if (this.stack1.length === 0) {
      throw new Error("Queue is empty");
    }
    // Return the top most element in Stack without popping
    return this.stack1[this.stack1.length - 1];
  }

  isEmpty() {
    /**
     * Returns True if the stack is empty, False otherwise.
     */
    return this.stack1.length === 0;
  }
}

// Let's now test the Queue implementation
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log("Dequeuing front element: ", queue.dequeue()); // Output: 1
console.log("Peeking front element: ", queue.peek()); // Output: 2
console.log("Dequeuing front element: ", queue.dequeue()); // Output: 2
console.log("Is Queue empty?: ", queue.isEmpty()); // Output: false, since item 3 is still in queue


import java.util.Stack;

public class Main {
  public static class Queue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public Queue() {
      // Initialize the two stacks
      stack1 = new Stack<>();
      stack2 = new Stack<>();
    }

    public void enqueue(int item) {
      /*
      Adds an item to the tail end of the Queue.
      */
      // Move all elements from stack1 to stack2
      while (!stack1.isEmpty()) {
        stack2.push(stack1.pop());
      }

      // Push the new item to stack1
      stack1.push(item);

      // Move all elements back from stack2 to stack1
      while (!stack2.isEmpty()) {
        stack1.push(stack2.pop());
      }
    }

    public int dequeue() {
      /*
      Removes and returns the front item from the Queue.
      */
      if (stack1.isEmpty()) {
        throw new IndexOutOfBoundsException("Queue is empty");
      }
      return stack1.pop();
    }

    public int peek() {
      /*
      Returns the front item from the Queue without removing it.
      */
      if (stack1.isEmpty()) {
        throw new IndexOutOfBoundsException("Queue is empty");
      }
      // Return the top most element in Stack without popping
      return stack1.peek();
    }

    public boolean isEmpty() {
      /*
      Returns True if the stack is empty, False otherwise.
      */
      return stack1.isEmpty();
    }
  }

  public static void main(String[] args) {
    // Let's now test the Queue implementation
    Queue queue = new Queue();
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    System.out.println("Dequeuing front element: " + queue.dequeue()); // Output: 1
    System.out.println("Peeking front element: " + queue.peek()); // Output: 2
    System.out.println("Dequeuing front element: " + queue.dequeue()); // Output: 2
    System.out.println("Is Queue empty?: " + queue.isEmpty()); // Output: False, since item 3 is still in queue
  }
}

Here’s how the implementation works:

The Queue class has two stacks: stack1 and stack2.
In the enqueue operation:
- We ensure that the topmost element in the stack is always the first element added to the Queue among all the elements present.
- And bottom most element in the stack should the mostly recently added element.
- In order to achieve this, we perform the below steps:
  - Move all elements from stack1 to stack2.
  - Push the new item to stack1.
  - Move all elements back from stack2 to stack1.
  - The time complexity is O(N), where N is the number of elements in the queue.
The dequeue operation:
- Checks if the stack1 is empty. If it is, it raises an error indicating that the queue is empty.
- Otherwise, it pops the top element from stack1, which is the first element added to the queue.
- The time complexity of the dequeue operation is O(1).
The peek operation:
- Checks if the stack1 is empty. If it is, it raises an error indicating that the queue is empty.
- Otherwise, it returns the top element of stack1, which is the first element added to the queue.
- The time complexity of the peek operation is O(1).
The is_empty operation:
- Returns True if stack1 is empty, indicating that the queue is empty.
- The time complexity of the is_empty operation is O(1).

This implementation ensures that the enqueue operation takes O(N) time, while the dequeue, peek, and is_empty operations take O(1) time. There are other variations of implementations as well with different time complexities. This implementation is simpler to understand among all as the core logic of reversing the order of elements in the stack is done only in one operation enqueue.