Stack adapters: browser history, undo, queues

A browser history is a class with three calls: open(page) shows a new page, while back(steps) and forward(steps) move through the pages already seen and stop at either end. Two rules make it a design problem. Opening a page after going back forgets every page that lay ahead, and one jump may ask for a billion steps. The two-stack design most people write first moves one page per step, which is right but far too slow at the limits below. The same calls also shape undo and redo, a queue built from two stacks and a fixed-size circular buffer.

The problem: a help-centre browser

One test, written as tests are written, with null for calls that return nothing: HelpBrowser("home"), then open("kb/12"), open("kb/40"), open("kb/7"), back(1), back(5), forward(1), open("kb/99"), forward(1) and back(1) give [null, null, null, null, "kb/40", "home", "kb/12", null, "kb/99", "kb/12"]. The call back(5) stops at the first page, and after open("kb/99") the two pages ahead are gone, so forward(1) stays where it is. A second test, with jumps far past both ends: HelpBrowser("home"), back(10**9), forward(10**9), open("kb/3"), back(10**9) and forward(10**9) give [null, "home", "home", null, "home", "kb/3"].

The brute force: two stacks, one page per step

The first design keeps two stacks: the pages up to the one shown, with that page on top, and the pages ahead. A step back moves one page from the first stack to the second, a step forward moves one back, and open empties the second stack. The answers are right, but a jump costs one move per page it passes. The slowest test opens n pages and then jumps 10⁹ pages back and forth, so every jump crosses the whole history:

"""The design most people write first: two stacks of pages, moved one page per step.

The back stack holds the pages up to the one shown, which is on top; the forward stack holds the pages that
forward() can return to. The answers are right. What this program measures is the work: every page moved from one
stack to the other is counted.
"""


class TwoStackBrowser:
    def __init__(self, home):
        self.back_stack = [home]  # the page shown is on top
        self.forward_stack = []
        self.moves = 0

    def open(self, page):
        self.back_stack.append(page)
        self.forward_stack.clear()  # a new page ends the forward history

    def back(self, steps):
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            self.moves += 1
            steps -= 1
        return self.back_stack[-1]

    def forward(self, steps):
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())
            self.moves += 1
            steps -= 1
        return self.back_stack[-1]


# The example of the statement.
b = TwoStackBrowser("home")
for page in ["kb/12", "kb/40", "kb/7"]:
    b.open(page)
answers = [b.back(1), b.back(5), b.forward(1)]
b.open("kb/99")
answers += [b.forward(1), b.back(1)]
print("example:", " ".join(answers))

# The slowest test: n pages opened, then n jumps that alternate back(10**9) and forward(10**9).
BIG = 10**9
for n in (500, 1_000, 2_000):
    b = TwoStackBrowser("home")
    for i in range(n):
        b.open(f"kb/{i}")
    for j in range(n):
        b.back(BIG) if j % 2 == 0 else b.forward(BIG)
    print(f"n = {n:,}: {2 * n:,} calls moved {b.moves:,} pages")

# Each jump moves the whole history across, n pages, so n jumps move n * n.
n = 100_000
print(f"n = {n:,}: {2 * n:,} calls would move {n * n:,} pages")

example: kb/40 home kb/12 kb/99 kb/12
n = 500: 1,000 calls moved 250,000 pages
n = 1,000: 2,000 calls moved 1,000,000 pages
n = 2,000: 4,000 calls moved 4,000,000 pages
n = 100,000: 200,000 calls would move 10,000,000,000 pages

Doubling n doubles the calls and multiplies the moves by four. At the limits that is 10¹⁰ moves. With the planning figure of the constraints lesson, about 10⁷ simple steps a second in CPython, the test would run for more than a quarter of an hour.

What to notice

A jump never changes the order of the pages; it only changes which page is shown. So the pages can stay where they are, and a jump of any length becomes arithmetic on a position, clamped at both ends. Three designs compete:

• Two stacks move the pages between them, one page per step.
• A list with a cursor keeps every page in place and moves an index instead.
• A doubly linked list of pages walks one node per step, as slowly as the stacks.

Three neighbours reuse these ideas. Undo and redo keep a document’s edits on two stacks. A queue from two stacks serves the oldest item first with stack operations alone. A circular buffer keeps the newest k items in k slots and overwrites the oldest.

Jumps of any length in O(1): the cursor design, step by step Pro: opens with a Pro, Premium or Ultimate pass