Stacks

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.

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

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

Application: Nearest Smaller Element

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

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 $an{s}_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 $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

1int n;
2
3int main() {
4    setIO(); re(n);
5    vpi v; v.pb({0,0});
6    FOR(i,1,n+1) {
7        int x; re(x);
8        while (sz(v) && v.back().f >= x) v.pop_back();
9        pr(v.back().s,' ');
10        v.pb({x,i});

1/**
2 * author: Kai Wang
3 */
4
5import java.io.*; import java.util.*;
6public class NearestSmallestVals {
7
8    /**
9     * We keep a stack of pairs (ind, value)
10     * Traverse the array from left to right, use ans to store answers

Problems