# Stacks

Authors: Darren Yao, Michael Cao

Contributor: George Pong

A data structure that only allows insertion and deletion at one end.

Resources | ||||
---|---|---|---|---|

CPH | brief description of operations | |||

CSA | Bracket Matching Application |

## Stacks

A stack is a **Last In First Out** (LIFO) data structure that supports three
operations, all in $\mathcal{O}(1)$ time. Think of it like a real-world stack of
papers.

C++

### C++

`push`

: adds an element to the top of the stack`pop`

: removes an element from the top of the stack`top`

: retrieves the element at the top without removing it

stack<int> s;s.push(1); // [1]s.push(13); // [1, 13]s.push(7); // [1, 13, 7]cout << s.top() << endl; // 7s.pop(); // [1, 13]cout << s.size() << endl; // 2

Java

### Java

`push`

: adds an element to the top of the stack`pop`

: removes an element from the top of the stack`peek`

: retrieves the element at the top without removing it

Stack<Integer> s = new Stack<Integer>();s.push(1); // [1]s.push(13); // [1, 13]s.push(7); // [1, 13, 7]System.out.println(s.peek()); // 7s.pop(); // [1, 13]System.out.println(s.size()); // 2

Python

### Python

Python does not have a built-in stack type, but a list can function like a stack.

`list.append()`

: Appends an element to the end.`list[-1]`

: Retrieves the last element without removing it.`list.pop()`

: Removes the last element and returns it (but you don't need to use the returned value).`list.pop(n)`

: Removes the nth element, 0-indexed. Note that removing elements is an`O(n)`

operation.

stack = [] # []stack.append(1) # [1]stack.append(2) # [1, 2]stack.append(3) # [1, 2, 3]v = stack[-1] # stack = [1, 2, 3] (unchanged), v = 3stack.pop() # [1, 2]v = stack.pop() # stack = [1], v = 2stack.append(4) # [1, 4]v = stack.pop(0) # stack = [4], v = 1

## Application - Nearest Smaller Element

Focus Problem – try your best to solve this problem before continuing!

Consider the following problem:

Given an array, $a$, of $N$ ($1 \le N \le 10^5$) integers, for every index $i$, find the rightmost index $j$ such that $j < i$ and $a_i > a_j$.

Resources | ||||
---|---|---|---|---|

CPH | ||||

CSA | similar application w/ animation |

To solve this, let's store a stack of pairs of $value, index$ and iterate over the array from left to right. For some index $i$, we will compute $\texttt{ans}[i]$, the rightmost index for $i$, as follows:

- Keep popping the top element off the stack as long as $value \ge a_i$. This is because we know that the pair containing $value$ will never be the solution to any index $j > i$, since $a_i$ is less than or equal to than $value$ and has an index further to the right.
- If $value < a_i$, set $\texttt{ans}[i]$ to $index$, because a stack stores the most recently added values first (or in this case, the rightmost ones), $index$ will contain the rightmost value which is less than $a_i$. Then, add ($a_i, i$) to the stack.

The stack we used is called a **monotonic stack** because we keep popping off
the top element of the stack which maintains it's monotonicity (the same
property needed for algorithms like binary search) because the elements in the
stack are increasing.

### Implementation

**Time Complexity:** $\mathcal{O}(N)$

C++

#include <bits/stdc++.h>using namespace std;int N;int main() {ios_base::sync_with_stdio(0);cin.tie(0);

Java

/*** author: Kai Wang*/import java.io.*;import java.util.*;public class NearestSmallestVals {/*** We keep a stack of pairs (ind, value)

Python

n = int(input())nums = list(map(int, input().split()))ans = []stack = [] # stores (a_i, i)for idx, num in enumerate(nums):while stack and stack[-1][0] >= num:stack.pop()ans.append(0 if not stack else stack[-1][1] + 1)stack.append((num, idx))print(*ans)

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsStack | |||

CF | Normal | ## Show TagsStack | |||

CEOI | Normal | ## Show TagsGeometry, Stack | |||

Baltic OI | Normal | ## Show TagsBinary Search, Stack | |||

Gold | Normal | ## Show TagsStack | |||

Gold | Normal | ## Show TagsBinary Search, Stack | |||

CSES | Normal | ## Show TagsStack | |||

CEOI | Normal | ## Show TagsStack | |||

CF | Normal | ## Show TagsStack | |||

Gold | Hard | ## Show TagsLinked List, Sorted Set, Stack | |||

CSES | Hard | ## Show TagsPURS, Stack | |||

CF | Hard | ## Show TagsDP, PURS, Stack | |||

IOI | Very Hard | ## Show TagsStack | |||

Kilonova | Very Hard | ## Show TagsStack | |||

CSES | Insane | ## Show TagsStack | |||

COI | Insane | ## Show TagsStack |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!