Stacks and the LIFO rule

Last in, first out

A stack is a collection with one rule: you can only add or remove items at one end, called the top. The last item pushed is the first popped, which is called LIFO, last in first out. A stack of plates works the same way.

It has three operations:

• push(x) puts x on top;
• pop() removes and returns the top item;
• peek() returns the top item without removing it.

That is deliberately less than an array offers. You can't read the middle, insert at the bottom or search. The restriction is the point: when a problem only ever needs the most recent item, a stack says so in the code, and it lets the implementation be as cheap as possible.

Building one

A dynamic array is the natural home for a stack, with the top at the end of the array. Push is an append and pop removes the last element, so both are O(1) (amortized for push), and neither moves any other element. In Python a plain list is a stack: append and pop. Java has ArrayDeque, C++ has std::stack over a vector or deque, and Rust's Vec provides push and pop directly.

Putting the top at the front of an array would be a mistake: every push and pop would shift all the other elements. A singly linked list also works, with the top at the head, and gives O(1) push and pop without ever resizing, at the cost of one allocation per item and the cache behavior from the previous module.

Popping an empty stack is an error, called underflow. Check before popping, as the bracket checker in the trace does with not stack.

When the most recent thing matters

Stacks fit problems with nested structure, where whatever opened most recently must close first.

Matching brackets. In the trace above, each opener is pushed. Each closer must match the opener on top, the most recent one still open, so the checker pops and compares. If they don't match, or there is nothing to pop, the input is unbalanced; if anything is left open at the end, it is unbalanced too. Counting brackets isn't enough: ([)] has matching counts but crosses its pairs, and the stack catches it when ) meets [. Compilers, JSON and XML parsers and code editors use this idea constantly.

Evaluating expressions. In postfix notation, also called reverse Polish notation, operators come after their operands: 2 3 + 4 * means (2 + 3) × 4. Evaluating it takes one stack. Push numbers; when an operator arrives, pop two numbers, apply it and push the result. At the end the stack holds the answer, 20. No parentheses or precedence rules are needed, which is why some calculators, the Java virtual machine and Python's bytecode interpreter all work this way: their instructions push values onto a stack and pop them as operands. Converting ordinary expressions such as (2 + 3) * 4 to postfix also uses a stack, in Dijkstra's shunting-yard algorithm.

Undo and back. An editor pushes each change onto an undo stack; undo pops the most recent one and reverses it. A redo stack holds what was undone, and any new edit clears it. A browser's back and forward buttons are the same pair of stacks around the current page.

Remembering extra information

Some problems need a little more than the top item. A min stack must report the smallest item currently on the stack in O(1). Keeping one variable for the minimum fails as soon as that minimum is popped, because nothing remembers the one before it. The fix is to push a pair: each item together with the minimum of everything at or below it. The top pair always knows the current minimum, and popping it automatically restores the previous minimum.

The same idea, storing with each stack entry whatever summary of the entries beneath it you will need, solves a family of problems. Longest valid parentheses, among this lesson's practice problems, pushes indexes instead of characters, so that each match can measure the length of the valid run it ends.

Costs at a glance

Both are constant time, so the choice comes down to constants. The array version touches memory sequentially and allocates rarely; the list version never resizes, which helps only when a single slow push is unacceptable. For almost every program, the array wins.

The shape to recognize

When you read a problem, a stack is likely the right tool if:

• items open and close, start and finish, or enter and leave in a nested way;
• the question is about the most recent unfinished item;
• you need to undo steps in reverse order of doing them;
• you process something recursive and want to do it without recursion.

The last point connects to the final lesson of this module: every running program already has a stack, the call stack, which works exactly like the ones here. Before that, the next lesson turns the rule around, first in first out, and builds a queue that never shifts an element.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Stacks and the LIFO rule from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

function next_greater_elements(nums):
    n = length(nums)
    ans = array of size n filled with -1
    stack = empty_stack()  // stores indices with decreasing values
    for i from 0 to n - 1:
        while not stack.empty() and nums[stack.top()] < nums[i]:
            idx = stack.pop()
            ans[idx] = nums[i]
        stack.push(i)
    return ans

#include <vector>
 
std::vector<int> nextGreaterElements(const std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    std::vector<int> ans(n, -1), st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[st.back()] < nums[i]) {
            ans[st.back()] = nums[i];
            st.pop_back();
        }
        st.push_back(i);
    }
    return ans;
}

import java.util.*;
 
public class StackQueueSolver {
    public static int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && nums[st.peekLast()] < nums[i]) {
                ans[st.pollLast()] = nums[i];
            }
            st.offerLast(i);
        }
        return ans;
    }
}

def next_greater_elements(nums: list[int]) -> list[int]:
    ans = [-1] * len(nums)
    stack: list[int] = []
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x
        stack.append(i)
    return ans

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.