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.
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
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
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
- 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:
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.
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.