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

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

Remark

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:

TypeTimeDescriptionIllustration
AccessO(1)Top of the stack O(n)Any other position
Depending on the desired position, the stack needs to be popped at most n times.
SearchO(n)Depending on whether the desired value gets found right away, the stack needs to be popped at most n times. InsertionO(1)Top of the stack
Push the new element. O(n)Any other position
1. 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.
DeletionO(1)Top of the stack
Pop the existing element. O(n)Any other position
1. 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:

$d_i=\underset{j>i, t_j > t_i}{\textrm{min}}(j-i)$

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:

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

Remark

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:

TypeTimeDescriptionIllustration O(n)Any other position
Depending on the desired position, the queue needs be dequeued at most n times.
SearchO(n)Depending on whether the desired value gets found right away, the queue needs to be dequeued at most n times. InsertionO(1)Tail of the queue
Enqueue the new element. O(n)Any other position
1. 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. 