Rare
 0/10

Stacks

Authors: Darren Yao, Michael Cao

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

Resources
CPHbrief description of operations
CSABracket Matching Application

Stacks

A stack is a Last In First Out (LIFO) data structure that supports three operations, all in O(1)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
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

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

Focus Problem – read through this problem before continuing!

Consider the following problem:

Given an array, aa, of NN (1N1051 \le N \le 10^5) integers, for every index ii, find the rightmost index jj such that j<ij < i and ai>aja_i > a_j.

Resources
CPH
CSAsimilar application w/ animation

To solve this, let's store a stack of pairs of value,indexvalue, index and iterate over the array from left to right. For some index ii, we will compute ansians_i, the rightmost index for ii, as follows:

  • Keep popping the top element off the stack as long as valueaivalue \ge a_i. This is because we know that the pair containing valuevalue will never be the solution to any index j>ij > i, since aia_i is less than or equal to than valuevalue and has an index further to the right.
  • If value<aivalue < a_i, set ans[i]ans[i] to indexindex, because a stack stores the most recently added values first (or in this case, the rightmost ones), indexindex will contain the rightmost value which is less than aia_i. Then, add (ai,ia_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

C++

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});

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

convert this

Java

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

StatusSourceProblem NameDifficultyTagsSolution
LCEasyView Solution
GoldNormalExternal Sol
GoldNormalExternal Sol
CSESNormalView Solution
CEOINormalCheck CF
IOIVery Hard
InfoArenaVery HardView Solution
CSESInsaneView Solution
Croatian OIInsaneExternal Sol

Module Progress:

Give Us Feedback on Stacks!