Skip to main content

Stacks and queues

By Afshine Amidi and Shervine Amidi

Stacks

Definition

A stack ss is a data structure that deals with elements s1,...,sns_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
Read the top element.
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=[t0,...,tn1]T=[t_{0}, ..., t_{n-1}] of temperatures. For each day ii, the goal is to find the number of days did_i until there is a warmer temperature.

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

di=minj>i,tj>ti(ji)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 O(ni)\mathcal{O}(n-i) elements for each day ii, this approach leads to an overall time complexity of O(n2)\mathcal{O}(n^2).

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

  • Initialization:

    • Initialize an empty stack ss.

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

  • Compute step: We use the monotonic stack trick:

    • The stack ss tracks days kk and their associated temperatures tkt_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 ii, we have the following cases:

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

      dk=ik\boxed{d_k=i-k}

      Repeat the popping procedure until the condition is not satisfied anymore.

    • Add the current item (i,ti)(i, t_i) to the stack ss.

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

Queues

Definition

A queue qq is a data structure that deals with elements q1,...,qnq_{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
AccessO(1)Head of the queue
Read the front element.
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.
DeletionO(1)Head of the queue
Dequeue the existing 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 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.

Want more content like this?

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