Stacks & Queues
Loading
Loading
Stacks & Queues
Last in, first out — and why that is the right shape for nesting.
By the end of this chapter
Push adds to the top, pop removes from the top. Nothing else is reachable. That restriction is the point: it exactly matches problems where the most recent unfinished item is the one that must be resolved next.
| Operation | Time | Space |
|---|---|---|
| Push | O(1) | O(1) |
| Pop | O(1) | O(1) |
| Peek | O(1) | O(1) |
| Searchwhich is why you should not | O(n) | O(1) |
def is_balanced(text): partner = {")": "(", "]": "[", "}": "{"} open_brackets = [] for char in text: if char in partner: if not open_brackets or open_brackets.pop() != partner[char]: return False else: open_brackets.append(char) return not open_brackets # anything left was never closedSign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: try 3 practice problems.