Algorithm Deep Dive Implement Queue using Stack Data Structure

Implement Queue using Stack Data Structure

3 min read

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:

Loading code…

Here’s how the implementation works:

  1. The Queue class has two stacks: stack1 and stack2.
  2. 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.
  3. 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).
  4. 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).
  5. 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.