1. Introduction

In this tutorial, we’re going to implement a stack data structure using two queues.

2. Stack and Queue Basics

Before proceeding to the algorithm, let’s first take a glance at these two data structures.

2.1. Stack

In a stack, we add elements in LIFO (Last In, First Out) order. This means that the last element inserted in the stack will be the first one removed. The basic operations of a stack are:

  • push — insert an element at the top
  • pop — remove an element from the top

2.2. Queue

In a queue, we add elements in FIFO (First In, First Out) order, meaning that the first element inserted is the first one to be removed. The basic operations of the queue are:

  • enqueue — insert an element at the rear
  • dequeue — remove an element from the front

3. Algorithm

To construct a stack using two queues (q1, q2), we need to simulate the stack operations by using queue operations:

  • push (E element)
    • if q1 is empty, enqueue E to q1
    • if q1 is not empty, enqueue all elements from q1 to q2, then enqueue E to q1, and enqueue all elements from q2 back to q1
  • pop
    • dequeue an element from q1

As we see, q1 acts as the main source for the stack, while q2 is just a helper queue that we use to preserve the order expected by the stack.

The pseudocode of the push and pop operations are:

Rendered by QuickLaTeX.com

Rendered by QuickLaTeX.com

The time complexity of the pop operation is O(1). For the push operation, we have a time complexity of O(n) because we have to transfer n-1 elements from q1 to q2 and back from q2 to q1.

4. Conclusion

In this tutorial, we presented the algorithm of constructing a stack using two queues.

Note that even if there’s no real advantage in doing this, it teaches us practical programming experience and shows us that we can combine and reuse data structures to achieve our goals. Stacks and queues are covered in greater detail in our article on common and useful data structures.

Subscribe
Notify of
guest
2 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
ellsc
ellsc
20 days ago

You dont need the “if q1 is empty, enqueue E to q1” branch. Because when q1 is empty, you wont loop in the else branch. However, thanks for sharing!

Loredana Crusoveanu
Loredana Crusoveanu
9 days ago
Reply to  ellsc

Hi ellsc,
Technically, that’s right. Though it does make for a cleaner algorithm (and hence implementation) to explicitly mention the empty queue condition.
Cheers!