Module 3.2 ⏱ 30 min read ⚡ Abstract Data Types

Stacks (LIFO Architecture)

Explore Last-In-First-Out data structures, contrast underlying array vs. linked-list stack designs, and master the advanced Monotonic Stack pattern.

1. Array-Based vs. Linked-List-Based Stacks

A stack restricts insertions and deletions to a single endpoint known as the "top," adhering strictly to a Last-In-First-Out (LIFO) model. Stacks can be implemented using two primary underlying architectures:

Array-Based Stacks: Utilize a dynamic array or vector where push and pop operations occur at the back end. This approach benefits from high CPU cache locality, though occasional resizes introduce amortized $O(1)$ overhead.

Linked-List-Based Stacks: Implement the stack by adding and removing nodes at the head of a singly linked list. This avoids capacity resizing overhead at the cost of extra memory allocation per node and reduced cache locality.

2. The Monotonic Stack Pattern

The monotonic stack pattern maintains elements in a strictly increasing or decreasing order. As you iterate through an array, elements that violate the monotonic property are popped off the stack. This powerful technique solves problems involving next-greater or previous-smaller elements in linear $O(n)$ time.

// C++ Solution: Next Greater Element Using Monotonic Stack
#include <vector>
#include <stack>

class Solution {
public:
    std::vector<int> nextGreaterElement(std::vector<int>& nums) {
        int n = nums.size();
        std::vector<int> res(n, -1);
        std::stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && nums[st.top()] < nums[i]) {
                res[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
};
            

# Python Solution: Next Greater Element Using Monotonic Stack
class Solution:
    def nextGreaterElement(self, nums: list[int]) -> list[int]:
        n = len(nums)
        res = [-1] * n
        st = []
        for i in range(n):
            while st and nums[st[-1]] < nums[i]:
                res[st.pop()] = nums[i]
            st.append(i)
        return res
            

// Java Solution: Next Greater Element Using Monotonic Stack
import java.util.Stack;
import java.util.Arrays;

class Solution {
    public int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Stack<Integer> st = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && nums[st.peek()] < nums[i]) {
                res[st.pop()] = nums[i];
            }
            st.push(i);
        }
        return res;
    }
}
            

3. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for the Valid Parentheses Checker and the Next Greater Element problem using stack tracking.

Quick Check: Test Your Intuition

What core data structure property makes a stack ideal for validating nested parentheses pairs?