Stack patterns: nesting and undo

A stack hands items back in the reverse of the order they arrived: the last one pushed is the first one popped. That one rule fits every problem in which the most recent unfinished item decides what happens next. A closing bracket must match the newest bracket that is still open. A .. in a file path leaves the folder you entered last. An undo reverses the latest change that is still in effect. In each case the newest item waits on top, older items wait below it, and each new item either joins the pile or settles the top. This lesson shows how to recognise these problems and which stack type to use in Python, JavaScript, Java, C++ and Go. Then it solves one problem in full, simplifying a path typed into a terminal, from a brute force to tested code in four languages, and ends with an undo stack for a small editor.

When a problem wants a stack

Look for these cues in a problem statement. Each one says that an item waits until a later item settles it, and that the newest waiting item is always settled first:

• Brackets are the clearest case. An opener stays on the stack until a closer arrives, and a closer that does not match the top means the text is unbalanced.
• Nesting is the same rule under another name. You leave levels in the reverse order you entered them, so the level you are in is always the top.
• Cancelling removes the most recent item that is still standing, never an older one.
• “The nearest earlier item that is larger” is the subtlest cue. Items wait on the stack until a later item answers a question about them, such as “on which later day is it warmer?”. Such a stack stays sorted from bottom to top, which gives it its name, a monotonic stack, and the later lessons of this module are built on it.

A shop’s billing keypad shows the third cue in a few lines: its < key deletes the digit typed just before it.

# A shop's billing keypad: "<" deletes the digit typed just before it, if there is one.


def entered(keys):
    digits = []  # a stack: the newest digit is at the end
    for key in keys:
        if key == "<":
            if digits:
                digits.pop()  # cancel the most recent digit that is still standing
        else:
            digits.append(key)
    return "".join(digits)


print(entered("98<76<<5"))

95

Each < removed the newest digit that was still there, and a < with nothing left to delete would be ignored, which is why the code checks if digits before it pops.

A stack is the wrong tool when the oldest item must go first (a queue), when the largest or most urgent item must go first (a heap), or when items are looked up by a key (a hash map). The self-check at the end of this lesson mixes all four.

Stacks in five languages

Every language in this track has a ready-made stack. Here is the type to use in each, its three operations (push, look at the top, pop), and what happens when you pop an empty stack, which is where the five differ most:

• Python: a list. Push with s.append(x), look at the top with s[-1], pop with s.pop(). Popping an empty list raises IndexError.
• JavaScript: an Array. Push with s.push(x), look with s.at(-1), pop with s.pop(). Popping an empty array returns undefined, with no error.
• Java: an ArrayDeque, used through the Deque interface. Push with s.addLast(x), look with s.peekLast(), pop with s.pollLast(). On an empty deque pollLast() returns null, while pop() throws NoSuchElementException.
• C++: a std::vector. Push with s.push_back(x), look with s.back(), pop with s.pop_back(). Popping an empty vector is undefined behaviour, so check s.empty() first.
• Go: a slice, []T. Push with s = append(s, x), look with s[len(s)-1], pop with s = s[:len(s)-1]. On an empty slice, looking and popping both cause a run-time panic.

Python, Java and C++ document pushing and popping at the end as O(1) amortised: now and then the array behind the stack moves to a bigger block of memory, and that cost is spread over all the pushes. The JavaScript and Go specifications promise no cost at all. Python’s table of costs also says that removing the first element, pop(0), is O(n), because every other element moves, so a stack works at the end, never at the front.

Here are Python and JavaScript side by side, with one pop too many:

# Push, look at the top, pop, and pop once too often: a Python list used as a stack.
stack = []
stack.append("home")  # push
stack.append("asha")
print(stack[-1])  # the top, without removing it: asha
print(stack.pop())  # remove the top and return it: asha
print(stack, len(stack))
stack.pop()
try:
    stack.pop()  # the stack is empty now
except IndexError as error:
    print("IndexError:", error)

asha
asha
['home'] 1
IndexError: pop from empty list

// Push, look at the top, pop, and pop once too often: a JavaScript array used as a stack.
const stack = [];
stack.push('home'); // push
stack.push('asha');
console.log(stack.at(-1)); // the top, without removing it: asha
console.log(stack.pop()); // remove the top and return it: asha
console.log(JSON.stringify(stack), stack.length);
stack.pop();
console.log(stack.pop()); // the stack is empty now: no error, just undefined

asha
asha
["home"] 1
undefined

Only Python stopped at the extra pop. JavaScript returned undefined, which is harmless here and a bug as soon as the value is used: undefined + 1 is NaN, with no error. Three more traps cost points in coding rounds:

• Java: which end you push to. push() adds at the front of a deque, and its iterator, which String.join and printing use, reads from front to back, so names pushed with push() come out in reverse. The Java run below shows it. When the stack must be read in order, add with addLast() and remove with pollLast(). The old java.util.Stack class still exists, but it extends Vector, a synchronized list, and its documentation recommends a Deque in its place. ArrayDeque also refuses null elements.
• C++: std::stack hides everything below the top. Its operations reach only the top (push, pop, top), apart from empty and size, and it has no way to walk its elements. When the answer needs the whole stack in order, as a path does, use a std::vector.
• Go: keep what append returns. When the slice is full, append moves the elements to a new, larger array and returns a slice of that array, so s = append(s, x) is the only safe way to push.

A worked problem: simplifying a terminal path

Before planning, settle the questions whose answers change the code. Here are the answers this problem gives:

• What does .. at the root do? It stays at the root. POSIX, the standard that Unix-like systems such as Linux and macOS follow, allows the root’s parent to be the root itself.
• Is ... special? No. Only . and .. are; ..., .env and a..b are ordinary folder names.
• What about repeated slashes? // counts as one /, at the start too. POSIX lets a system give a path that begins with exactly two slashes a meaning of its own; this problem does not.
• Should symbolic links be followed? No: simplify the text alone. A shell’s cd does the same by default, which POSIX calls handling dot-dot logically; cd -P resolves the links first.
• What form does the answer take? It starts with / and never ends with one, except the root itself, /.

Work four examples by hand, and keep them as tests: /home/asha/../ravi/./notes/ leads to /home/ravi/notes; /../ to /; /srv//logs/.../ to /srv/logs/...; and /a/b/../../.. to /.

The brute force

The rule for one .. is easy to state: it deletes itself and the folder name just before it. So repeat that until no .. is left. Split the path at its slashes, drop the empty parts and the .s, find the first .., delete it with the name before it (or alone, at the root), and start again:

"""The brute force: delete the first ".." together with the folder name just before it, and repeat."""


def simplify_brute(path, cost=None):
    names = [name for name in path.split("/") if name not in ("", ".")]
    while ".." in names:
        i = names.index("..")
        start = i - 1 if i > 0 else 0  # a ".." at the front stands at the root: there is no name before it
        names = names[:start] + names[i + 1 :]
        if cost is not None:
            cost["rounds"] += 1
            cost["copied"] += len(names)  # each round builds a new list out of the names that stay
    return "/" + "/".join(names)


if __name__ == "__main__":
    for path in ["/home/asha/../ravi/./notes/", "/../", "/srv//logs/.../", "/a/b/../../.."]:
        print(f'"{path}" -> "{simplify_brute(path)}"')
    print()
    print("characters  rounds  names copied")
    for depth in [200, 400, 800, 1600]:
        path = "/d" * depth + "/.." * depth  # down `depth` folders, then all the way back up
        cost = {"rounds": 0, "copied": 0}
        simplify_brute(path, cost)
        print(f"{len(path):>10,}  {cost['rounds']:>6,}  {cost['copied']:>12,}")

"/home/asha/../ravi/./notes/" -> "/home/ravi/notes"
"/../" -> "/"
"/srv//logs/.../" -> "/srv/logs/..."
"/a/b/../../.." -> "/"

characters  rounds  names copied
     1,000     200        39,800
     2,000     400       159,600
     4,000     800       639,200
     8,000   1,600     2,558,400

It gets every example right. The table under the answers shows its cost on a path that hurts it, one that goes k folders down and then climbs straight back up. Every round deletes one pair and copies the rest of the list, so the names copied add up to k² − k, and doubling the path’s length roughly multiplies them by four. At the limit of 100,000 characters (k = 20,000) that comes to about 400 million copies, with about as many comparisons to find each ..: ten thousand times the work of the one-pass method below.

What to notice

Watch which name each .. deletes. It is not simply the name before it in the original path: in /a/b/../../.. the second .. deletes a, because b is already gone. A .. always cancels the most recent name that is still standing. That is the stack cue from the first section, so keep the names that are still standing on a stack, and let each .. pop the top.

One pass with a stack

Read the parts between the slashes from left to right. An empty part (from //, or before the first slash or after the last) and . change nothing; .. pops the top, if there is one; every other part is pushed. At the end the answer is a slash followed by the names on the stack, joined with slashes.

The proof rests on one statement that stays true after every part: the stack holds the folders of the path read so far, from the root down. It is true at the start, when the stack is empty and the path so far leads to the root. A name moves one folder down, which is one more name on the stack. A .. moves one folder up, which drops the last name, or stays at the root when there is no name to drop. A . and an empty part stay where they are. So after the last part, the stack spells the answer.

Each part costs at most one push or one pop, so the pass takes O(n) time for a path of n characters, and the stack and the answer take O(n) memory. On the deep path from the brute force’s table, that means 400 pushes and pops at 1,000 characters, against 39,800 names copied, and 40,000 at the full 100,000 characters.

The same pass in four languages

"""Simplify an absolute path with a stack of folder names."""


def simplify_path(path):
    stack = []  # the folders of the path read so far, from the root down
    for name in path.split("/"):
        if name in ("", "."):
            continue  # a repeated or trailing "/", or "this folder": nothing changes
        if name == "..":
            if stack:
                stack.pop()  # back to the parent: drop the most recent folder
        else:
            stack.append(name)  # into a folder; "..." and ".env" are names too
    return "/" + "/".join(stack)


if __name__ == "__main__":
    for path in ["/home/asha/../ravi/./notes/", "/../", "/srv//logs/.../", "/a/b/../../..", "/.config/../.local/share/"]:
        print(f'"{path}" -> "{simplify_path(path)}"')

"/home/asha/../ravi/./notes/" -> "/home/ravi/notes"
"/../" -> "/"
"/srv//logs/.../" -> "/srv/logs/..."
"/a/b/../../.." -> "/"
"/.config/../.local/share/" -> "/.local/share"

// Simplify an absolute path with a stack of folder names.
function simplifyPath(path) {
  const stack = []; // the folders of the path read so far, from the root down
  for (const name of path.split('/')) {
    if (name === '' || name === '.') continue; // a repeated or trailing "/", or "this folder"
    if (name === '..') {
      if (stack.length > 0) stack.pop(); // back to the parent: drop the most recent folder
    } else {
      stack.push(name); // into a folder; "..." and ".env" are names too
    }
  }
  return '/' + stack.join('/');
}

for (const path of ['/home/asha/../ravi/./notes/', '/../', '/srv//logs/.../', '/a/b/../../..', '/.config/../.local/share/']) {
  console.log(`"${path}" -> "${simplifyPath(path)}"`);
}

"/home/asha/../ravi/./notes/" -> "/home/ravi/notes"
"/../" -> "/"
"/srv//logs/.../" -> "/srv/logs/..."
"/a/b/../../.." -> "/"
"/.config/../.local/share/" -> "/.local/share"

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

// Simplify an absolute path with a stack of folder names.
public class PathSimplifier {
    static String simplify(String path) {
        Deque<String> stack = new ArrayDeque<>(); // the folders read so far: first is nearest the root, last is the top
        for (String name : path.split("/")) {
            if (name.isEmpty() || name.equals(".")) continue; // a repeated or trailing "/", or "this folder"
            if (name.equals("..")) {
                stack.pollLast(); // back to the parent; on an empty deque pollLast() just returns null
            } else {
                stack.addLast(name); // into a folder; "..." and ".env" are names too
            }
        }
        return "/" + String.join("/", stack); // a deque is read from first to last: the path's own order
    }

    public static void main(String[] args) {
        String[] paths = {"/home/asha/../ravi/./notes/", "/../", "/srv//logs/.../", "/a/b/../../..", "/.config/../.local/share/"};
        for (String path : paths) {
            System.out.println("\"" + path + "\" -> \"" + simplify(path) + "\"");
        }
        // The trap: push() adds at the front, and reading starts at the front, so the folders come out reversed.
        Deque<String> pushed = new ArrayDeque<>();
        for (String name : new String[] {"home", "ravi", "notes"}) pushed.push(name);
        System.out.println("joined after push(): /" + String.join("/", pushed));
    }
}

// Simplify an absolute path with a stack of folder names (C++23).
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

std::string simplify(const std::string& path) {
    std::vector<std::string> stack;  // the folders read so far; back() is the top
    std::istringstream parts(path);
    std::string name;
    while (std::getline(parts, name, '/')) {
        if (name.empty() || name == ".") continue;  // a repeated or trailing "/", or "this folder"
        if (name == "..") {
            if (!stack.empty()) stack.pop_back();  // pop_back() on an empty vector is undefined behaviour
        } else {
            stack.push_back(name);  // into a folder; "..." and ".env" are names too
        }
    }
    std::string out;
    for (const std::string& folder : stack) out += "/" + folder;
    return out.empty() ? "/" : out;
}

int main() {
    for (const std::string path : {"/home/asha/../ravi/./notes/", "/../", "/srv//logs/.../", "/a/b/../../..", "/.config/../.local/share/"}) {
        std::cout << '"' << path << "\" -> \"" << simplify(path) << "\"\n";
    }
}

"""Compiles and runs the Java and the C++ version, showing each command and what it printed."""
from terminal import session

session("""
java --version | head -n 1 | cut -d ' ' -f 1,2
javac --release 25 PathSimplifier.java
java PathSimplifier
clang++ --version | head -n 1
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined simplify.cpp -o simplify
./simplify
""")

$ java --version | head -n 1 | cut -d ' ' -f 1,2
openjdk 27
$ javac --release 25 PathSimplifier.java
$ java PathSimplifier
"/home/asha/../ravi/./notes/" -> "/home/ravi/notes"
"/../" -> "/"
"/srv//logs/.../" -> "/srv/logs/..."
"/a/b/../../.." -> "/"
"/.config/../.local/share/" -> "/.local/share"
joined after push(): /notes/ravi/home
$ clang++ --version | head -n 1
Apple clang version 21.0.0 (clang-2100.3.34.2)
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined simplify.cpp -o simplify
$ ./simplify
"/home/asha/../ravi/./notes/" -> "/home/ravi/notes"
"/../" -> "/"
"/srv//logs/.../" -> "/srv/logs/..."
"/a/b/../../.." -> "/"
"/.config/../.local/share/" -> "/.local/share"

All four print the same answers for the same five paths. The Java version is compiled with javac --release 25, which checks it against the Java 25 platform, although the JDK that ran it is a newer one, version 27. The last line of its run is the trap from the language section: the same three names, pushed with push(), come out as /notes/ravi/home. The C++ version is built with AddressSanitizer and UndefinedBehaviorSanitizer, which report bad memory accesses and undefined behaviour while the program runs; both stayed silent. In Go the same pass keeps a []string, appends each name and drops the last one with a slice expression, as shown for Go above.

Checking it against the brute force

The brute force is slow but easy to trust, which makes it the right judge for the fast version:

"""Checks the stack version against the brute force on random paths (a fixed seed: every run tests the same paths)."""
import random

from brute import simplify_brute
from simplify import simplify_path

PARTS = ["", ".", "..", "...", "a", "b", ".env"]  # every kind of part, the awkward ones included
rng = random.Random(35)
paths = ["/" + "/".join(rng.choice(PARTS) for _ in range(rng.randint(0, 10))) for _ in range(3000)]

for path in paths[:4]:
    print(f'"{path}" -> "{simplify_path(path)}"')
disagreements = [p for p in paths if simplify_path(p) != simplify_brute(p)]
print(f"{len(paths):,} random paths, {len(disagreements)} disagreements")
for path in disagreements[:3]:  # the first few, if there are any, are a ready-made bug report
    print(f'  "{path}": stack "{simplify_path(path)}", brute force "{simplify_brute(path)}"')

"/../.env/./b/../.env/./.." -> "/.env"
"/../a//b/a/.env" -> "/a/b/a/.env"
"/b/../.env/b" -> "/.env/b"
"/.env//..//a///b/..." -> "/a/b/..."
3,000 random paths, 0 disagreements

The random paths mix every awkward part: //, ., .. at the root, ... and .env. The seed is fixed, so every run tests the same 3,000 paths, and the first four are printed so that you can check them by hand. Not one disagreement turned up. Had there been any, the program would have printed the first three, each a ready-made bug report: the path, the stack’s answer and the brute force’s.

Why not call a library?

Python and Node.js both come with a path normaliser, and in real code you might call one. In a coding round, ask first: the interviewer usually wants to see the stack, and the libraries follow rules of their own.

"""What Python's own normaliser makes of four paths (posixpath: the POSIX rules, on any operating system)."""
import posixpath

THE_RULES = {  # path -> the answer under this lesson's rules
    "/home/asha/../ravi/./notes/": "/home/ravi/notes",
    "/srv//logs/.../": "/srv/logs/...",
    "//srv/logs": "/srv/logs",
    "/../": "/",
}
for path, rule in THE_RULES.items():
    got = posixpath.normpath(path)
    note = "same" if got == rule else f'differs: the rules give "{rule}"'
    print(f'"{path}" -> "{got}" ({note})')

"/home/asha/../ravi/./notes/" -> "/home/ravi/notes" (same)
"/srv//logs/.../" -> "/srv/logs/..." (same)
"//srv/logs" -> "//srv/logs" (differs: the rules give "/srv/logs")
"/../" -> "/" (same)

// What Node.js's own normaliser makes of four paths (path.posix: the POSIX rules, on any operating system).
import { posix } from 'node:path';

const theRules = new Map([ // path -> the answer under this lesson's rules
  ['/home/asha/../ravi/./notes/', '/home/ravi/notes'],
  ['/srv//logs/.../', '/srv/logs/...'],
  ['//srv/logs', '/srv/logs'],
  ['/../', '/'],
]);
for (const [path, rule] of theRules) {
  const got = posix.normalize(path);
  const note = got === rule ? 'same' : `differs: the rules give "${rule}"`;
  console.log(`"${path}" -> "${got}" (${note})`);
}

"/home/asha/../ravi/./notes/" -> "/home/ravi/notes/" (differs: the rules give "/home/ravi/notes")
"/srv//logs/.../" -> "/srv/logs/.../" (differs: the rules give "/srv/logs/...")
"//srv/logs" -> "/srv/logs" (same)
"/../" -> "/" (same)

Each one differs from this problem’s rules on an edge case of its own. Python keeps exactly two leading slashes, because POSIX lets a system give such a path a meaning of its own. Node.js keeps a trailing slash, and its documentation says so. Both, like the stack, work on the text alone, and Python’s documentation warns that this can change the meaning of a path that contains symbolic links.

Undo: a stack of changes

Undo is “cancel the previous one” applied to changes instead of characters. Each change pushes what it would take to reverse it, and an undo pops the newest entry and applies it. This editor knows three commands: type <text>, delete <count> (characters from the end) and undo.

"""A tiny editor with type, delete and undo: every change pushes what it takes to reverse it."""


def run(commands):
    text = []  # the document, one character per item
    undo = []  # one entry per change still in effect, the most recent last
    for command in commands:
        action, _, argument = command.partition(" ")
        if action == "type":
            text.extend(argument)
            undo.append(("typed", len(argument)))  # to reverse it: delete that many characters
        elif action == "delete":
            count = min(int(argument), len(text))  # there may be fewer characters than asked for
            removed = "".join(text[len(text) - count :])
            del text[len(text) - count :]
            undo.append(("deleted", removed))  # to reverse it: type the same characters again
        elif action == "undo" and undo:  # with nothing left to undo, undo does nothing
            kind, value = undo.pop()
            if kind == "typed":
                del text[len(text) - value :]
            else:
                text.extend(value)
        print(f"{command:<17} {''.join(text)!r}")


run(["type masala chai", "delete 4", "type coffee", "undo", "undo", "delete 50", "undo", "undo", "undo"])

type masala chai  'masala chai'
delete 4          'masala '
type coffee       'masala coffee'
undo              'masala '
undo              'masala chai'
delete 50         ''
undo              'masala chai'
undo              ''
undo              ''

Three details keep it correct:

• An entry holds only what reversing needs: how many characters were typed, or exactly which characters were deleted. The document itself is never copied, so an undo costs time in proportion to the change, not to the document.
• An entry records what really happened. delete 50 on an 11-character text deletes 11, and the entry stores those 11, so undoing it restores exactly masala chai.
• An undo with nothing to undo does nothing, as the last command shows. Without the check, pop() on the empty list would stop the program with an IndexError.

The same shape, push what reverses a step and pop it to go back, is how backtracking takes back a choice before it tries the next one, in a later module of this track.

Interview questions

Warm-up (fresher to mid-level): How do you recognise that a coding problem wants a stack?

Look for a rule in which the newest unfinished item decides what happens next. Brackets and tags are the clearest case: a closer must match the most recent opener that is still open. Nested structures behave the same way, whether folders, nested calls or nested data, because you leave levels in the reverse order you entered them. “Cancel the previous one” is another sign: a backspace, an undo or a .. removes the most recent item still standing. And “the nearest earlier item that is larger” calls for a stack of items still waiting for their answer, a monotonic stack. If instead the oldest item must go first, use a queue; if the largest or most urgent, a heap.

Warm-up (fresher to mid-level): In Java, should a stack be a java.util.Stack or an ArrayDeque, and does it matter which end you push to?

Use an ArrayDeque through the Deque interface. Stack is a legacy class that extends Vector, a synchronized list, and its own documentation recommends a Deque instead; the ArrayDeque documentation adds that it is likely to beat Stack at the job. The end matters when you read the stack. push() adds at the front, and a deque’s iterator reads from front to back, so after pushing home, ravi and notes, String.join gives notes/ravi/home. To read a stack in the order it was built, as when folder names become a path, add with addLast() and remove with pollLast(). Remember too that ArrayDeque refuses null elements.

Key takeaways

• Reach for a stack when the most recent unfinished item decides what happens next: brackets and tags, nesting, “cancel the previous one” and “the nearest earlier item that is larger”.
• Use a list in Python, an Array in JavaScript, an ArrayDeque in Java (with addLast and pollLast when order matters), a std::vector in C++ and a slice in Go. Check for an empty stack before you pop: the five languages answer an empty pop with anything from an exception to undefined behaviour.
• A path simplifies in one pass: skip empty parts and ., pop on .., push everything else. The stack is always the folder you are in.
• The brute force, deleting the first .. and repeating, is O(n²). Keep it as the judge in a stress test of the O(n) stack.
• An undo stack stores just enough to reverse each change, records what really happened, and ignores an undo when it is empty.