## 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*

- if
*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:

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.

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!

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!