Stacks: LIFO, implementations, bracket matching

A stack is a collection that gives items back in the reverse of the order they went in: the item added last is the first one taken out, which is why it is called LIFO, last in, first out. Everything happens at one end, the top. Push puts an item on top, pop takes the top item off and returns it, and peek reads the top without removing it; a good implementation does all three in O(1) time (amortised, when an array behind it has to grow). That small contract does a lot of work. Compilers and calculators use it to check brackets, editors to undo changes, search algorithms to explore a maze one corridor at a time, and your own program to run its function calls. This lesson builds a stack twice, on a growable array and on linked nodes, measures what each one costs, lists the stack types of Python, JavaScript, Java, C++ and Go, and then uses a stack to find the first bracket that breaks a formula.

A promise about order

A stack is an abstract data type: it is defined by its operations and the promise they keep, not by how the items are stored. The promise is about order. The item pushed most recently, and not popped yet, is the top, and it is the only item you can read or remove. Everything below it waits until the items above it are gone.

A van loaded through its back door behaves the same way. The parcel loaded last is the first one the driver can reach, so a van that will stop at Surat, then Nashik, then Pune must be loaded in the opposite order: Pune first, Surat last.

Two decisions belong to the contract rather than to any implementation, and they are worth making on purpose:

• What pop does on an empty stack. Raising an error is the safest choice, because the caller made a mistake and should hear about it at once. Returning a special value such as None is shorter, but the value can travel a long way before anything notices.
• Whether the stack has a size limit. The implementations below grow until memory runs out. A stack inside a device driver or a parser of untrusted input may need a fixed limit and a clear error when it is reached.

A stack on a growable array

The simplest stack keeps its items in a growable array, such as a Python list, with the bottom at index 0 and the top at the end. Push appends, pop removes the last item and peek reads it:

class EmptyStackError(Exception):
    """Raised by pop() and peek() when the stack holds nothing."""


class ArrayStack:
    """A stack kept in a Python list: the bottom at index 0, the top at the end."""

    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)  # amortised O(1): the list sometimes moves to a bigger block

    def pop(self):
        if not self._items:
            raise EmptyStackError("pop from an empty stack")
        return self._items.pop()  # O(1): no other item moves

    def peek(self):
        if not self._items:
            raise EmptyStackError("peek at an empty stack")
        return self._items[-1]

    def is_empty(self):
        return not self._items

    def __len__(self):
        return len(self._items)


# A van is loaded through its back door, so the parcel loaded last comes out first.
# The route is Surat, then Nashik, then Pune: load in the opposite order.
van = ArrayStack()
for town in ["Pune", "Nashik", "Surat"]:
    van.push(town)
    print(f"push {town:<7} size {len(van)}, top {van.peek()}")

while not van.is_empty():
    print(f"pop  {van.pop():<7} size {len(van)}")

try:
    van.pop()
except EmptyStackError as error:
    print("pop  again:", error)

push Pune    size 1, top Pune
push Nashik  size 2, top Nashik
push Surat   size 3, top Surat
pop  Surat   size 2
pop  Nashik  size 1
pop  Pune    size 0
pop  again: pop from an empty stack

Python’s documentation describes exactly this use of a list in its tutorial, and its table of costs explains why the top belongs at the end. Appending is O(1) amortised: now and then the list moves to a bigger block of memory and copies every item, but over many appends that cost averages out to a constant. Popping the last item moves nothing at all, so it is O(1). Inserting or popping at index 0 is the worst case, because the whole rest of the list has to move one place.

That is not a small difference. The program below pushes n items and pops them all again, once with the top at the end of a list and once with the top at its front:

"""Push n items and pop them all again, with the top of the stack at the end of a list or at its front."""

import time


def top_at_end(n):
    s = []
    for i in range(n):
        s.append(i)
    while s:
        s.pop()


def top_at_front(n):
    s = []
    for i in range(n):
        s.insert(0, i)  # every item already in the list moves one place right
    while s:
        s.pop(0)  # every item left moves one place left


def best_ms(work, n, repeats=3):
    best = float("inf")
    for _ in range(repeats):
        start = time.perf_counter()
        work(n)
        best = min(best, time.perf_counter() - start)
    return best * 1000


print(f"{'n':>8}{'top at end':>14}{'top at front':>15}{'front / end':>13}")
for n in [10_000, 20_000, 40_000]:
    end = best_ms(top_at_end, n)
    front = best_ms(top_at_front, n)
    print(f"{n:>8,}{end:>11.1f} ms{front:>12.1f} ms{front / end:>12.0f}x")

       n    top at end   top at front  front / end
  10,000        0.4 ms        22.9 ms          52x
  20,000        0.8 ms       251.4 ms         310x
  40,000        2.0 ms      1232.5 ms         620x

With the top at the end, the time grows in proportion to n, because each operation costs the same. With the top at the front, every push shifts all the items already there and every pop shifts them all back, so n pushes and n pops move about n² items in total: from 10,000 to 40,000 items its time grows far more than the fourfold that a linear cost would give. The last column shows the consequence: the front version is not slower by a fixed factor, it falls further behind as n grows.

A stack on linked nodes

A stack can also be a chain of small objects called nodes. Each node holds one item and a reference to the node below it, and the stack itself remembers only the top node. Push creates a node that points at the old top and makes it the new top. Pop moves the top one node down and returns the item of the node it left.

class EmptyStackError(Exception):
    """Raised by pop() and peek() when the stack holds nothing."""


class _Node:
    __slots__ = ("value", "below")

    def __init__(self, value, below):
        self.value = value
        self.below = below  # the node pushed just before this one, or None at the bottom


class LinkedStack:
    """A stack of linked nodes: the top is the newest node, and each node points to the one below it."""

    def __init__(self):
        self._top = None
        self._size = 0

    def push(self, item):
        self._top = _Node(item, self._top)  # O(1), every time: one new node, nothing copied
        self._size += 1

    def pop(self):
        if self._top is None:
            raise EmptyStackError("pop from an empty stack")
        node = self._top
        self._top = node.below  # the node below becomes the top
        self._size -= 1
        return node.value

    def peek(self):
        if self._top is None:
            raise EmptyStackError("peek at an empty stack")
        return self._top.value

    def is_empty(self):
        return self._top is None

    def __len__(self):
        return self._size

    def top_to_bottom(self):
        node, out = self._top, []
        while node is not None:
            out.append(node.value)
            node = node.below
        return out


van = LinkedStack()
for town in ["Pune", "Nashik", "Surat"]:
    van.push(town)
print("top to bottom:", " -> ".join(van.top_to_bottom()))

print("pop:", van.pop(), "| now top to bottom:", " -> ".join(van.top_to_bottom()))
van.push("Vapi")
print("push Vapi | now top to bottom:", " -> ".join(van.top_to_bottom()))

while not van.is_empty():
    print("pop:", van.pop())

try:
    van.peek()
except EmptyStackError as error:
    print("peek:", error)

top to bottom: Surat -> Nashik -> Pune
pop: Surat | now top to bottom: Nashik -> Pune
push Vapi | now top to bottom: Vapi -> Nashik -> Pune
pop: Vapi
pop: Nashik
pop: Pune
peek: peek at an empty stack

Every push here costs the same, one new node, with no copying ever, so push and pop are O(1) in the worst case, not just on average. The price is memory. A list slot is a single reference, while a node is a complete object with its own header, and the measurement below counts what each stack allocates for 100,000 items:

"""Memory a stack of 100,000 items takes for its own bookkeeping, measured with tracemalloc.

Every push stores the same object, None, so the items themselves cost nothing extra: only what the stack
allocates to hold them is counted.
"""

import tracemalloc

N = 100_000


class SlotNode:
    __slots__ = ("value", "below")

    def __init__(self, value, below):
        self.value = value
        self.below = below


class PlainNode:  # an ordinary class: every node also gets an attribute dictionary
    def __init__(self, value, below):
        self.value = value
        self.below = below


def measure(build):
    tracemalloc.start()
    keep = build()  # keep the stack alive while measuring
    used, _peak = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    del keep
    return used


def list_stack():
    items = []
    for _ in range(N):
        items.append(None)
    return items


def linked_stack(node_class):
    def build():
        top = None
        for _ in range(N):
            top = node_class(None, top)
        return top

    return build


print(f"{N:,} pushes")
print(f"{'stack':<28}{'bytes':>12}{'per item':>10}")
for name, build in [
    ("list (top at the end)", list_stack),
    ("linked, nodes with slots", linked_stack(SlotNode)),
    ("linked, plain nodes", linked_stack(PlainNode)),
]:
    used = measure(build)
    print(f"{name:<28}{used:>12,}{used / N:>10.1f}")

100,000 pushes
stack                              bytes  per item
list (top at the end)            800,928       8.0
linked, nodes with slots       4,800,000      48.0
linked, plain nodes            8,803,360      88.0

On the 64-bit CPython 3.14.8 that ran it, a list spent 8 bytes per item, a node with __slots__ 48 and an ordinary node 88. __slots__ tells Python not to give each object an attribute dictionary, and the language reference notes that the space saved can be significant: here it nearly halved the cost of a node. Even so, the linked stack used six times the memory of the list, and its nodes can lie anywhere in memory, while the list’s slots sit side by side.

That last row needs a word. A push links a new node above the old top and changes no node that was already there, so a reference to the old top node still describes the old stack, complete and unchanged. Two stacks can share a tail this way: the stack before a push and the stack after it share every node but one. Search programs that try a choice and then return to the state before it use this, because keeping an old version costs one reference.

Stacks in five languages

You will rarely write a stack class in production code, because every language of this track already has one. The programs below run the same steps in each: push 10, 20 and 30, read the top, pop everything, then try to pop once more.

# Python: a list is the stack. append() pushes, pop() pops, [-1] reads the top.
stack = []
for x in [10, 20, 30]:
    stack.append(x)
print("after pushing 10, 20, 30:", stack, "top", stack[-1])

print("pop", stack.pop(), "pop", stack.pop(), "pop", stack.pop())

try:
    stack.pop()
except IndexError as error:
    print("pop on an empty list raises IndexError:", error)

try:
    stack[-1]
except IndexError as error:
    print("reading the top of an empty list raises IndexError:", error)

after pushing 10, 20, 30: [10, 20, 30] top 30
pop 30 pop 20 pop 10
pop on an empty list raises IndexError: pop from empty list
reading the top of an empty list raises IndexError: list index out of range

// JavaScript: an Array is the stack. push() pushes, pop() pops, at(-1) reads the top.
const stack = [];
for (const x of [10, 20, 30]) stack.push(x);
console.log('after pushing 10, 20, 30:', JSON.stringify(stack), 'top', stack.at(-1));

console.log('pop', stack.pop(), 'pop', stack.pop(), 'pop', stack.pop());

// No exception: an empty array answers undefined, and arithmetic on it quietly gives NaN.
const missing = stack.pop();
console.log('pop on an empty array returns', missing, '| missing + 1 =', missing + 1);
console.log('at(-1) on an empty array returns', stack.at(-1));

after pushing 10, 20, 30: [10,20,30] top 30
pop 30 pop 20 pop 10
pop on an empty array returns undefined | missing + 1 = NaN
at(-1) on an empty array returns undefined

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;

// Java: an ArrayDeque used through the Deque interface. push(), pop() and peek() work at the deque's head.
public class StackOps {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int x : new int[] {10, 20, 30}) stack.push(x);
        // The deque prints from its head, which is the top of the stack.
        System.out.println("after pushing 10, 20, 30: " + stack + " top " + stack.peek());

        System.out.println("pop " + stack.pop() + " pop " + stack.pop() + " pop " + stack.pop());

        try {
            stack.pop();
        } catch (NoSuchElementException e) {
            System.out.println("pop on an empty deque throws NoSuchElementException");
        }
        System.out.println("peek on an empty deque returns " + stack.peek() + ", and poll returns " + stack.poll());
        try {
            stack.push(null);
        } catch (NullPointerException e) {
            System.out.println("push(null) throws NullPointerException: an ArrayDeque holds no nulls");
        }
    }
}

#include <iostream>
#include <stack>

// C++: std::stack is an adaptor, by default over a std::deque. top() reads, pop() removes and returns nothing.
int main() {
    std::stack<int> stack;
    for (int x : {10, 20, 30}) stack.push(x);
    std::cout << "after pushing 10, 20, 30: size " << stack.size() << " top " << stack.top() << '\n';

    std::cout << "pop";
    while (!stack.empty()) {
        std::cout << ' ' << stack.top();  // read the top first: pop() returns void
        stack.pop();
    }
    std::cout << '\n';

    // top() or pop() on an empty stack is undefined behaviour, so the program checks first.
    if (stack.empty()) std::cout << "empty: top() and pop() must not be called now\n";
}

package main

import "fmt"

// Go: a slice is the stack. append pushes, s[len(s)-1] reads the top, s = s[:len(s)-1] pops.
func pop(s []int) ([]int, int) {
	top := s[len(s)-1] // panics when s is empty
	return s[:len(s)-1], top
}

func main() {
	var stack []int
	for _, x := range []int{10, 20, 30} {
		stack = append(stack, x) // keep what append returns: it may be a new array
	}
	fmt.Println("after pushing 10, 20, 30:", stack, "top", stack[len(stack)-1])

	var x int
	fmt.Print("pop")
	for len(stack) > 0 {
		stack, x = pop(stack)
		fmt.Print(" ", x)
	}
	fmt.Println()

	defer func() {
		fmt.Println("pop on an empty slice panics:", recover())
	}()
	stack, x = pop(stack)
	fmt.Println("never printed", x)
}

from session import run, versions

# The Java file runs as a single source file, the C++ file is built with the sanitizers on, go run builds the Go file.
versions("java -version", "clang++ --version", "go version")
run("""
java StackOps.java
clang++ -std=c++23 -O1 -Wall -Wextra -fsanitize=address,undefined stack_ops.cpp -o stack_ops && ./stack_ops
go run stack_ops.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java StackOps.java
after pushing 10, 20, 30: [30, 20, 10] top 30
pop 30 pop 20 pop 10
pop on an empty deque throws NoSuchElementException
peek on an empty deque returns null, and poll returns null
push(null) throws NullPointerException: an ArrayDeque holds no nulls
$ clang++ -std=c++23 -O1 -Wall -Wextra -fsanitize=address,undefined stack_ops.cpp -o stack_ops && ./stack_ops
after pushing 10, 20, 30: size 3 top 30
pop 30 20 10
empty: top() and pop() must not be called now
$ go run stack_ops.go
after pushing 10, 20, 30: [10 20 30] top 30
pop 30 20 10
pop on an empty slice panics: runtime error: index out of range [-1]

The five agree on the order and disagree on the empty pop, which is where bugs hide:

• Python uses a list and raises IndexError for pop() and for [-1] on an empty list.
• JavaScript uses an Array. The language specification makes pop() on an empty array return undefined, and the run shows where that leads: undefined + 1 is NaN, and nothing reports an error.
• Java uses an ArrayDeque through the Deque interface. push, pop and peek all work at the head of the deque, which is why printing it shows the top first, [30, 20, 10]. On an empty deque pop() throws NoSuchElementException while peek() and poll() return null, and the class refuses null items. The older java.util.Stack extends Vector, and its own documentation says to prefer a Deque.
• C++ has std::stack, an adaptor that by default stores its items in a std::deque, and a std::vector works as well. top() reads and pop() removes and returns nothing, so you read before you pop. Neither may be called on an empty stack: the program checks empty() first, because the standard containers leave that case undefined.
• Go uses a slice: append pushes, s[len(s)-1] reads and s = s[:len(s)-1] pops. On an empty slice the index is out of range, and the specification turns that into a run-time panic, which the program catches with recover to print it.

Matching brackets with a stack

A formula such as 24 - [5 + {8 - (3 + 2)}] uses three kinds of brackets, and it is balanced when every closing bracket matches the most recent opening bracket that is still open. “Most recent still open” is the stack’s promise, so the check is short: push each opening bracket; at a closing bracket, pop and compare; at the end, the stack must be empty.

PARTNER = {")": "(", "]": "[", "}": "{"}  # each closer and the opener it must match


def balanced(text, show=False):
    """True when every bracket of text is closed, in the right order, by a closer of its own kind."""
    stack = []  # the openers still waiting for their closer, the newest on top
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in PARTNER:
            if not stack or stack.pop() != PARTNER[ch]:
                return False  # nothing is open, or the newest open bracket is of another kind
        else:
            continue  # digits, operators and spaces do not matter
        if show:
            print(f"  after {ch}  stack: {''.join(stack) or '(empty)'}")
    return not stack  # anything still open was never closed


print("24 - [5 + {8 - (3 + 2)}]")
print("balanced:", balanced("24 - [5 + {8 - (3 + 2)}]", show=True))
print()
for formula in ["(2 + 3] * 4", "{[(1 + 2) * 3] - 4", "(1 + 2)) * 3", "[{()}()]", ""]:
    print(f"{formula!r:<22} balanced: {balanced(formula)}")

24 - [5 + {8 - (3 + 2)}]
  after [  stack: [
  after {  stack: [{
  after (  stack: [{(
  after )  stack: [{
  after }  stack: [
  after ]  stack: (empty)
balanced: True

'(2 + 3] * 4'          balanced: False
'{[(1 + 2) * 3] - 4'   balanced: False
'(1 + 2)) * 3'         balanced: False
'[{()}()]'             balanced: True
''                     balanced: True

const PARTNER = { ')': '(', ']': '[', '}': '{' }; // each closer and the opener it must match

/** True when every bracket of text is closed, in the right order, by a closer of its own kind. */
function balanced(text, show = false) {
  const stack = []; // the openers still waiting for their closer, the newest on top
  for (const ch of text) {
    if ('([{'.includes(ch)) {
      stack.push(ch);
    } else if (ch in PARTNER) {
      if (stack.length === 0 || stack.pop() !== PARTNER[ch]) return false; // nothing open, or the wrong kind
    } else {
      continue; // digits, operators and spaces do not matter
    }
    if (show) console.log(`  after ${ch}  stack: ${stack.join('') || '(empty)'}`);
  }
  return stack.length === 0; // anything still open was never closed
}

const py = (b) => (b ? 'True' : 'False'); // print like the Python version
console.log('24 - [5 + {8 - (3 + 2)}]');
console.log('balanced:', py(balanced('24 - [5 + {8 - (3 + 2)}]', true)));
console.log();
for (const formula of ['(2 + 3] * 4', '{[(1 + 2) * 3] - 4', '(1 + 2)) * 3', '[{()}()]', '']) {
  console.log(`${`'${formula}'`.padEnd(22)} balanced: ${py(balanced(formula))}`);
}

24 - [5 + {8 - (3 + 2)}]
  after [  stack: [
  after {  stack: [{
  after (  stack: [{(
  after )  stack: [{
  after }  stack: [
  after ]  stack: (empty)
balanced: True

'(2 + 3] * 4'          balanced: False
'{[(1 + 2) * 3] - 4'   balanced: False
'(1 + 2)) * 3'         balanced: False
'[{()}()]'             balanced: True
''                     balanced: True

The trace shows the stack after each bracket of the first formula: it grows to [{( at the innermost point and empties exactly at the last ]. The other lines show the three ways to fail. In (2 + 3] * 4 a ] arrives while ( is on top. In (1 + 2)) * 3 a ) arrives with nothing open. In {[(1 + 2) * 3] - 4 every closer matches, but the { is still open when the text ends.

Each character is read once, so the check takes O(n) time for a text of n characters. The stack holds the openers that are open at the same moment, so it needs O(n) memory in the worst case, a text that opens everything before it closes anything. One counter would be enough for a single kind of bracket, but not for three, because a counter cannot tell ([)] from ([]): only a stack remembers which kind was opened last.

A real checker for program code also skips brackets inside strings and comments, such as the ) in print(")"), which takes a tokenizer that knows the language. The idea underneath stays the same.

The call stack is a stack

Your program runs on a stack too. Each function call pushes a frame holding its arguments and local variables, and each return pops it, which is why the function that was called last is always the first to finish. A recursive function therefore uses one frame per level of recursion, and the depth is limited. Python checks a recursion limit, which sys.getrecursionlimit() reports and which, as its documentation says, keeps runaway recursion from overflowing the interpreter’s own C stack and crashing it. Going past the limit raises RecursionError.

Any recursion can be rewritten with an explicit stack of the work still to do, kept in an ordinary list that is limited only by memory. This program adds up the numbers in nested lists both ways:

import sys


def nested(depth):
    """[1, [1, [1, ...]]]: `depth` lists, each holding a 1 and the next list."""
    item = [1]
    for _ in range(depth - 1):
        item = [1, item]
    return item


def total_recursive(item):
    if not isinstance(item, list):
        return item
    total = 0
    for x in item:
        total += total_recursive(x)  # each level of nesting is one more frame on the call stack
    return total


def total_with_stack(item):
    total, tallest = 0, 0
    stack = [item]  # the parts still to add up
    while stack:
        tallest = max(tallest, len(stack))
        x = stack.pop()
        if isinstance(x, list):
            stack.extend(reversed(x))  # reversed, so the parts come off in the order they are written
        else:
            total += x
    return total, tallest


print("recursion limit:", sys.getrecursionlimit())
for depth in [100, 5_000]:
    data = nested(depth)
    try:
        print(f"depth {depth:>5,}: recursive total = {total_recursive(data)}")
    except RecursionError as error:
        print(f"depth {depth:>5,}: recursive version failed with RecursionError: {error}")
    total, tallest = total_with_stack(data)
    print(f"depth {depth:>5,}: explicit stack total = {total}, at most {tallest} items on the stack")

recursion limit: 1000
depth   100: recursive total = 100
depth   100: explicit stack total = 100, at most 2 items on the stack
depth 5,000: recursive version failed with RecursionError: maximum recursion depth exceeded
depth 5,000: explicit stack total = 5000, at most 2 items on the stack

At a depth of 100 both versions agree. At a depth of 5,000 the recursive version needs 5,000 frames, five times the limit of 1,000 in the recorded run, and fails, while the explicit stack finishes. The explicit version never held more than 2 items, because it pushes the parts of each list in reverse, so the number comes off first and the nested list waits below it. The same loop, pop an item and push what it leads to, is depth-first search, which a later module of this track uses on graphs.

Exercise

Turn the yes-or-no check into one that points at the problem: return the index of the first bracket that breaks the formula.

PARTNER = {")": "(", "]": "[", "}": "{"}


def first_error(text):
    """Index of the first bracket error in text, or -1 when every bracket is matched."""
    stack = []  # indexes of the brackets still open
    # Write your loop here.
    return -1

from first_error import first_error


def test_balanced_formulas():
    """matched brackets give -1"""
    assert first_error("") == -1
    assert first_error("24 - [5 + {8 - (3 + 2)}]") == -1
    assert first_error("x = f(a[0], {k: v})") == -1
    assert first_error("no brackets at all") == -1


def test_closer_with_nothing_open():
    """a closer that finds nothing open is the error"""
    assert first_error(")") == 0
    assert first_error("(1 + 2)) * 3") == 7
    assert first_error("a]b") == 1


def test_closer_of_the_wrong_kind():
    """a closer that does not match the newest open bracket is the error"""
    assert first_error("(2 + 3] * 4") == 6
    assert first_error("([)]") == 2
    assert first_error("{[}]") == 2


def test_brackets_left_open():
    """when the text ends with brackets open, the oldest one is the error"""
    assert first_error("{[(1 + 2) * 3] - 4") == 0
    assert first_error("a(b[c]d") == 1
    assert first_error("((") == 0
    assert first_error("()(") == 2

const PARTNER = { ')': '(', ']': '[', '}': '{' };

/** Index of the first bracket error in text, or -1 when every bracket is matched. */
export function firstError(text) {
  const stack = []; // indexes of the brackets still open
  // Write your loop here.
  return -1;
}

import { test, assert } from 'mysmartcopilot:test';
import { firstError } from './first_error.mjs';

test('matched brackets give -1', () => {
  assert.equal(firstError(''), -1);
  assert.equal(firstError('24 - [5 + {8 - (3 + 2)}]'), -1);
  assert.equal(firstError('x = f(a[0], {k: v})'), -1);
  assert.equal(firstError('no brackets at all'), -1);
});

test('a closer that finds nothing open is the error', () => {
  assert.equal(firstError(')'), 0);
  assert.equal(firstError('(1 + 2)) * 3'), 7);
  assert.equal(firstError('a]b'), 1);
});

test('a closer that does not match the newest open bracket is the error', () => {
  assert.equal(firstError('(2 + 3] * 4'), 6);
  assert.equal(firstError('([)]'), 2);
  assert.equal(firstError('{[}]'), 2);
});

test('when the text ends with brackets open, the oldest one is the error', () => {
  assert.equal(firstError('{[(1 + 2) * 3] - 4'), 0);
  assert.equal(firstError('a(b[c]d'), 1);
  assert.equal(firstError('(('), 0);
  assert.equal(firstError('()('), 2);
});

Interview questions

Warm-up (fresher to mid-level): Why does an array-backed stack keep its top at the end of the array rather than at index 0?

Because the end is the only place where adding and removing move nothing. A push at the end writes one slot and a pop clears one, so both are O(1); Python documents append as O(1) amortised and popping the last item as moving nothing. With the top at index 0, every push shifts all the items one place right and every pop shifts them all back, so each operation is O(n) and pushing and popping n items costs O(n²). The lesson’s measurement shows the gap growing with n. The order of the items is the same either way, so nothing is gained by putting the top at the front.

Warm-up (fresher to mid-level): What is the difference between the stack abstract data type and a stack implementation?

The abstract data type is the contract: push puts an item on top, pop removes and returns the top, peek reads it, and the item popped is always the newest one still there. It says nothing about memory. An implementation chooses how to keep that promise. A growable array keeps the items in one block with the top at the end, so push is O(1) amortised and each item costs one reference, 8 bytes in 64-bit CPython. Linked nodes give every item its own node that points to the one below, so each push is O(1) without copying, but a node with __slots__ took 48 bytes in the lesson’s measurement. Code written against the contract works with either.

Key takeaways

• A stack gives items back in reverse order: push, pop and peek all work at the top, in O(1).
• On a growable array, keep the top at the end. Push is O(1) amortised and pop is O(1); a top at index 0 makes every operation shift the whole array.
• Linked nodes make every push O(1) without copying and let stacks share their lower nodes, at about six times the memory per item in CPython.
• Use a list in Python, an Array in JavaScript, an ArrayDeque in Java, std::stack or a std::vector in C++ and a slice in Go, and decide what an empty pop does before it happens.
• Brackets match when every closer pairs with the newest opener still open: push openers, pop and compare at closers, and expect an empty stack at the end.
• Recursion runs on the call stack, which has a depth limit; an explicit stack in a list moves the same work to memory you control.