Advanced stack design — compose

Advanced — பல substacks / lazy merge / aux structures; முதலில் invariant.

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

• Cap நிரம்பினால் புதிய list — plates.
• கடைசி non-empty plate-ல் pop.
• popAt — boundary.