Stack
stack
Data Structures
Stack (LIFO)
Every time a function calls another function, the language runtime pushes a frame onto an internal stack; every `return` pops one off. That same Last In, First Out discipline shows up in undo buttons, expression evaluators, browser back navigation, and the call patterns of recursion, which is why **Stack (LIFO)** is one of the first abstract data types every engineer learns. This lesson introduces the four core operations of a stack (`push`, `pop`, `peek`, `isEmpty`), the underflow case you must handle on every pop, and two implementations: a dynamic array stack with amortized `O(1)` push, and a linked list stack with strict `O(1)` push at the head. You will trace stack state through bracket matching, postfix evaluation, and string reversal so the LIFO mental model becomes a tool you reach for instinctively when a problem asks you to remember the most recent thing. In **Arrays & Strings**, you saw that appending to the end of a dynamic array is `O(1)` amortized, which is exactly the cost model for an array-backed stack. **Linked Lists (Singly)** showed that head insertion is unconditionally `O(1)`, which is what makes a linked list the cleanest backing store for a stack with a strict worst-case guarantee. Next, **Queue & Deque** flips the discipline: instead of pulling from the same end you pushed to, you pull from the opposite end, and the implementation gets just a little more interesting.
Not Started
0%
Practice Problems
Implement Queue using Stacks
Implement a first-in-first-out (FIFO) queue using only two stacks, supporting push, pop, peek, and empty operations.
Next Greater Element I
Given two arrays where nums1 is a subset of nums2, find the next greater element in nums2 for each element in nums1.
Valid Parentheses
Given a string containing only brackets, determine if the input string has valid (properly matched and nested) parentheses.
Basic Calculator
Implement a basic calculator to evaluate a string expression containing '+', '-', parentheses, and non-negative integers.
Largest Rectangle in Histogram
Given an array of bar heights representing a histogram, find the area of the largest rectangle that can be formed within the histogram.
Maximal Rectangle
Given a 2D binary matrix filled with '0's and '1's, find the area of the largest rectangle containing only '1's.
Binary Search Tree Iterator
Implement an iterator over a BST that returns elements in ascending order (in-order traversal).
Car Fleet
Given positions and speeds of cars heading toward a target, determine how many car fleets will arrive at the destination.
Daily Temperatures
Given an array of daily temperatures, return how many days you have to wait for a warmer temperature for each day.
Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression given in Reverse Polish Notation (postfix), where operators follow their operands.
Generate Parentheses
Given n pairs of parentheses, generate all combinations of well-formed (valid) parentheses.
Kth Smallest Element in a BST
Given the root of a BST and an integer k, return the kth smallest value (1-indexed) using in-order traversal.
Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element, all in constant time.
Simplify Path
Given an absolute Unix-style file path, simplify it by resolving '.', '..', and multiple slashes to produce the canonical path.
Sum of Subarray Minimums
Given an array of integers, find the sum of the minimum value of every contiguous subarray, modulo 10^9 + 7.
Code Snippets
Stack via Array
JavaScript does not ship a dedicated `Stack` class because `Array` already supports O(1) `push` and `pop`. This snippet covers the array-as-stack idiom, a tiny class wrapper for self-documenting code, and a balanced-parentheses checker that demonstrates the canonical stack-driven algorithm. Use this template anywhere the LIFO order matters: undo, expression evaluation, DFS bookkeeping.
DFS Traversal Template
Depth-first search visits a node, then recursively visits each unvisited neighbor before backtracking. It is the natural traversal for tree problems, cycle detection, topological order, and connected-components. This snippet covers the recursive form, an iterative stack-based form for very deep graphs, and a path-tracking variant that surfaces the actual route from start to a target.
Question Banks
Stack and Queue Fundamentals
Four short prompts on LIFO vs FIFO behavior, balanced parentheses, and a bug hunt in a circular queue. Good warm-up before monotonic-stack drills.
Monotonic Stack Patterns
Five prompts on monotonic stacks for next-greater-element, daily temperatures, and largest rectangle. Mostly implementation with one trace and one bug hunt.
Community
Decode String
Expand a run-length-encoded string with arbitrary nesting using two parallel stacks (counts and string fragments).
Remove Outermost Parentheses
Strip the outer parentheses of every primitive group in a balanced parenthesis string, in one pass with a depth counter.
Online Stock Span
Design an online structure that returns the streak of consecutive previous days with price <= today, using a monotonic stack of (price, span) pairs.
Stacks and Queues Cheat Sheet
LIFO vs FIFO, the operations that matter, and the language-specific footguns (JS shift, Python list.pop(0), Java Stack vs Deque) that turn O(1) into O(n).
Backspace String Compare
Compare two strings after applying backspace edits, with the catch that the O(1) space version uses two pointers walking from the end.
Monotonic Stack: The Pattern Everyone Skips
The next-greater-element trick that turns O(n^2) scans into O(n). Daily temperatures, largest rectangle in histogram, and trapping rain water, all from the same shape.
Flatten a Multilevel Doubly Linked List
Flatten a doubly-linked list whose nodes may have a child pointer to another doubly-linked list, producing a single-level list via DFS or an explicit stack.
Min Add to Make Parentheses Valid
Count the minimum number of '(' and ')' insertions that turn a parenthesis string valid using a single-pass two-counter scan.
Asteroid Collision
Simulate collisions between right- and left-moving asteroids using a stack of survivors, popping while the top loses head-on encounters.