Advanced Stack Design — Compose Structures

Advanced designs compose stacks: multiple substacks with a capacity, lazy merging, or synchronized auxiliary structures—sketch invariants before coding.

Try this in Python

class SetOfStacks:
    def __init__(self, cap: int) -> None:
        self.cap = cap
        self.stacks: list[list[int]] = [[]]

    def push(self, x: int) -> None:
        if len(self.stacks[-1]) == self.cap:
            self.stacks.append([])
        self.stacks[-1].append(x)

    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        return self.stacks[-1].pop()


s = SetOfStacks(2)
for x in [1, 2, 3, 4]:
    s.push(x)
print(s.pop(), s.pop())

Key takeaways

• When one physical stack fills, roll over to a new list—plates on a table.
• Pop from the last non-empty plate.
• Interview variants add popAt(substack)—think boundary cases.