Rare
 0/16

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 O(1)\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; // 7
s.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()); // 7
s.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 = 3
stack.pop() # [1, 2]
v = stack.pop() # stack = [1], v = 2
stack.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, 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
CSA

similar 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 ans[i]\texttt{ans}[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]\texttt{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++

#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

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsStack
CFNormal
Show TagsStack
CEOINormal
Show TagsGeometry, Stack
GoldNormal
Show TagsStack
GoldNormal
Show TagsBinary Search, Stack
CSESNormal
Show TagsStack
CEOINormal
Show TagsStack
CFNormal
Show TagsStack
GoldHard
Show TagsLinked List, Sorted Set, Stack
CSESHard
Show TagsPURS, Stack
CFHard
Show TagsDP, PURS, Stack
IOIVery Hard
Show TagsStack
KilonovaVery Hard
Show TagsStack
CSESInsane
Show TagsStack
COIInsane
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!