# Stacks and queues

*By Afshine Amidi and Shervine Amidi*

## Stacks

### Definition

A stack $s$ is a data structure that deals with elements $s_1, ..., s_{n}$ in a *Last In First Out* (LIFO) order.

In order to do that, it uses the push and pop operations:

Push | Pop |
---|---|

Insert an element on the top of the stack. | Remove the element from the top of the stack and return its value. |

As a result, the last element added to the data structure will be the first one removed.

Stacks are commonly used for Depth-First Search (DFS) graph traversals.

### Operations

The main operations that can be performed on a stack are explained below:

Type | Time | Description | Illustration |
---|---|---|---|

Access | O(1) | Top of the stackRead the top element. | |

O(n) | Any other positionDepending on the desired position, the stack needs to be popped at most n times. | ||

Search | O(n) | Depending on whether the desired value gets found right away, the stack needs to be popped at most n times. | |

Insertion | O(1) | Top of the stackPush the new element. | |

O(n) | Any other position1. Pop elements until accessing the desired position and push them into an auxiliary stack. 2. Push the new element. 3. Pop elements from the auxiliary stack and push them into the initial stack. | ||

Deletion | O(1) | Top of the stackPop the existing element. | |

O(n) | Any other position1. Pop elements until accessing the desired position and push them into an auxiliary stack. 2. Pop the existing element. 3. Pop elements from the auxiliary stack and push them into the initial stack. |

### Daily temperatures

Suppose we are given an array $T=[t_{0}, ..., t_{n-1}]$ of temperatures. For each day $i$, the goal is to find the number of days $d_i$ until there is a warmer temperature.

In other words, for each day $i\in[\![0, n-1]\!]$, we want to find the number of days $d_i$ such that:

A naive approach would compute the answer for each day in isolation. By scanning up to $\mathcal{O}(n-i)$ elements for each day $i$, this approach leads to an overall time complexity of $\mathcal{O}(n^2)$.

However, a more efficient approach uses stacks and computes the solution in $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ space:

*Initialization:*Initialize an empty stack $s$.

Initialize the output array $D=[d_{0}, ..., d_{n-1}]$ with zeros.

*Compute step:*We use the monotonic stack trick:The stack $s$ tracks days $k$ and their associated temperatures $t_k$.

Elements added to the stack are days for which we want to find a greater temperature. They are popped as soon as a future warmer day is found.

Temperature values are popped in a monotonically non-decreasing manner. This ensures that all relevant values are popped for a given warmer day.

We start from day 0. For each day $i$, we have the following cases:

If the temperature $t_{k}$ at the top of the stack is lower than the current temperature $t_i$, pop $(k, t_k)$ from the stack, and write the corresponding day difference in the final array:

$\boxed{d_k=i-k}$Repeat the popping procedure until the condition is not satisfied anymore.

Add the current item $(i, t_i)$ to the stack $s$.

Repeat this process until reaching the end of the array $T$. The array $D$ contains the final answer. Entries with zeros correspond to days that do not have future warmer days.

## Queues

### Definition

A queue $q$ is a data structure that deals with elements $q_{1}, ..., q_{n}$ in a *First In First Out* (FIFO) order, where its tail has the most recently arrived elements and its head has elements that arrived the earliest.

In order to do that, it uses the enqueue and dequeue operations:

Enqueue | Dequeue |
---|---|

Insert element at the tail of the queue. | Remove element from the head of the queue. |

As a result, the first element added to the data structure will be the first one to be removed.

Queues are commonly used for Breadth-First Search (BFS) graph traversals.

### Operations

The main operations that can be performed on a queue are explained below:

Type | Time | Description | Illustration |
---|---|---|---|

Access | O(1) | Head of the queueRead the front element. | |

O(n) | Any other positionDepending on the desired position, the queue needs be dequeued at most n times. | ||

Search | O(n) | Depending on whether the desired value gets found right away, the queue needs to be dequeued at most n times. | |

Insertion | O(1) | Tail of the queueEnqueue the new element. | |

O(n) | Any other position1. Initialize a new empty queue. 2. Dequeue elements from the current queue and enqueue them to the new queue up until right before the desired position of insertion. 3. Enqueue the new element in the new queue. 4. Dequeue the remaining elements from the current queue and enqueue them to the new queue. | ||

Deletion | O(1) | Head of the queueDequeue the existing element. | |

O(n) | Any other position1. Initialize a new empty queue. 2. Dequeue elements from the current queue and enqueue them to the new queue up until right before the desired position of deletion. 3. Dequeue the element to be removed from the current queue and ignore it. 4. Dequeue the remaining elements from the current queue and enqueue them to the new queue. |

**Subscribe here** to be notified of new Super Study Guide releases!