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

```
algorithm Push(q1, q2, E):
// INPUT
// q1, q2 = two queues
// E = element to push to stack
// OUTPUT
// element E is now at the head of queue q1
if q1 is empty:
q1.enqueue(E)
else:
q1Size <- q1.size()
for i <- 1, 2, ..., q1Size:
q2.enqueue(q1.dequeue())
q1.enqueue(E)
for j <- 1, 2, ..., q1Size:
q1.enqueue(q2.dequeue())
```

Here’s the pseudocode of the *pop* operation:

```
algorithm Pop(q1):
// INPUT
// q1, q2 = two queues
// OUTPUT
// the head element of the queue q1 (which is removed from q1)
element <- q1.dequeue()
return element
```

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.