stack ADT

Work in Progress

Summary

Stack ADT

  • last in first out(LIFO)

Compact array implementation

  • fixed size issue
OperationMethodPerformance
push(v)insert after last-
pop()remove last-
peek()get last-
a1a2...anheadtailinout

SLL implementation

OperationMethodPerformance
push(v)insert at head-
pop()remove from head-
peek()get head-
a1a2...anheadtailinout

Stack classes

Library implementation

java
import java.util.Stack;

Stack<Integer> st = new Stack<>();
// or

// push(v)
st.push(2); // [2]
st.push(3); // [3, 2]

// pop()
st.pop(); // 3, [2]

// peek()
st.peek(); // 2, [2]

// check if stack is empty
st.empty(); // false

// number of elements in the stack
st.size(); // 1

Concept

Stack operations

  • push(v)
    • push v onto the top of the stack
  • pop()
    • get the item on top of the stack and remove it
  • peek()
    • get the item on top of the stack without removing it
4321inout

Monotonic stack

  • preserve sorting order when pushing and poping
java
// monotonic increasing stack
while (!st.empty() && st.peek() > e) // pop the top if its larger 
	st.pop();
	
st.push(e);

// or
if (e > st.peek()) // push only if larger
	st.push(e);

Application

Postfix evaluation

java
// 4 3 * -> 4 * 3 = 12
// 3 4 2 * 4 + - -> 3 - ((4 * 2) + 4) = -9

Stack<Integer> stack = new Stack<>();

for (String token : input.split(" ")) {
	// check if token is a number or operator
	if (token.matches("-?\\d+")) {  
			stack.push(Integer.parseInt(token));
	} else {
		// pop the 2 operands
		int val1 = stack.pop();
		int val2 = stack.pop();

		switch (token) {
			case "+":
				stack.push(val2 + val1);
				break;
			case "-":
				stack.push(val2 - val1);
				break;
			case "*":
				stack.push(val2 * val1);
				break;
			case "/":
				stack.push(val2 / val1);
				break;
		}
	}
}
return stack.pop(); // assuming the input is valid

Lisp evaluation

  • parse tokens into a stack
  • when a closing bracket is encountered, pop operands and operator until opening bracket

Leetcode: Max Chunks To Make Sorted II

  • monotonic increasing stack
  • greedy maximum
java
// test inputs: [5,4,3,2,1], [2,1,3,4,4], [0,0,1,1,1], [1,0,1,3,2], [1,1,0,0,1]
Stack<Integer> st = new Stack<>();

for (int i = 0; i < arr.length; i++) {
	int max = arr[i];

	while (!st.empty() && st.peek() > arr[i]) // monotonic increasing stack
		max = Math.max(max, st.pop()); // greedy: keep track of the max

	st.push(max);
}
// resulting stacks: [5], [4,4,3,2], [1,1,1,0,0], [1,1,3], [1,1]
return st.size();

Leetcode: Sum of Subarray Minimums

  • monotonic increasing stack
83954621+14+183954622+11+1
java
// test input: [8,3,9,5,4,6,2]
// arrays with 3 as the minimum: (1+1) * (4+1) = 10
// [8,3,9,5,4,6]
// [8,3,9,5,4]
// [8,3,9,5]
// [8,3,9]
// [8,3]
//   [3,9,5,4,6]
//   [3,9,5,4]
//   [3,9,5]
//   [3,9]
//   [3]
//
// arrays with 4 as the minimum: (2+1) * (1+1) = 6
// [9,5,4,6]
// [9,5,4]
//   [5,4,6]
//   [5,4]
//     [4,6]
//     [4]

int n = arr.length;
int[] prev = new int[n], next = new int[n];

Stack<Integer> st = new Stack<>();

// for every element, find the first element to the left that is smaller or equal
for (int i = 0; i < n; i++) {
	while (!st.empty() && arr[st.peek()] > arr[i])
		st.pop();
	prev[i] = st.empty() ? i + 1 : i - st.peek();
	st.push(i);
}

st.clear();

// for every element, find the first element to the right that is smaller
for (int i = n - 1; i >= 0; i--) {
	while(!st.empty() && arr[st.peek()] >= arr[i])
		st.pop();
	next[i] = st.empty() ? n - i : st.peek() - i;
	st.push(i);
}

int mod = (int) 1e9 + 7;
long sum = 0;

for (int i = 0; i < n; i++) {
	sum += (long) (prev[i] * next[i]) % mod * arr[i] % mod;
	sum %= mod;
}

return (int) sum;