Stacks & Queues

1class Stack:
2    """Stack implemented with a Python list.
3    push/pop/peek are all O(1) amortized."""
4
5    def __init__(self):
6        self._data = []            # internal storage
7
8    def push(self, val):
9        """Add element to the top of the stack."""
10        self._data.append(val)     # list.append is O(1) amortized
11
12    def pop(self):
13        """Remove and return the top element."""
14        if self.is_empty():
15            raise IndexError("pop from empty stack")
16        return self._data.pop()    # list.pop() removes last item — O(1)
17
18    def peek(self):
19        """Return the top element without removing it."""
20        if self.is_empty():
21            raise IndexError("peek from empty stack")
22        return self._data[-1]      # negative index — O(1)
23
24    def is_empty(self):
25        return len(self._data) == 0
26
27    def size(self):
28        return len(self._data)

1from collections import deque
2
3class Queue:
4    """Queue backed by collections.deque for O(1) operations.
5    deque uses a doubly-linked list of blocks internally."""
6
7    def __init__(self):
8        self._data = deque()       # O(1) append and popleft
9
10    def enqueue(self, val):
11        """Add element to the back of the queue."""
12        self._data.append(val)     # append to right end — O(1)
13
14    def dequeue(self):
15        """Remove and return the front element."""
16        if self.is_empty():
17            raise IndexError("dequeue from empty queue")
18        return self._data.popleft()  # remove from left end — O(1)
19
20    def peek(self):
21        """Return front element without removing it."""
22        if self.is_empty():
23            raise IndexError("peek from empty queue")
24        return self._data[0]       # direct access to front — O(1)
25
26    def is_empty(self):
27        return len(self._data) == 0
28
29    def size(self):
30        return len(self._data)

1def is_valid(s: str) -> bool:
2    """LeetCode #20 — Valid Parentheses.
3    Use a stack to match every closing bracket
4    with the most recent unmatched opening bracket."""
5
6    stack = []                        # our stack of opening brackets
7    matching = {')': '(', '}': '{', ']': '['}
8
9    for char in s:
10        if char in matching:
11            # It's a closing bracket — check the top of stack
12            if not stack or stack[-1] != matching[char]:
13                return False          # mismatch or nothing to match
14            stack.pop()               # matched — remove the opening bracket
15        else:
16            # It's an opening bracket — push it
17            stack.append(char)
18
19    return len(stack) == 0            # all brackets must be matched
20
21# is_valid("()[]{}") -> True
22# is_valid("(]")     -> False
23# is_valid("{[]}")   -> True

1def next_greater_element(nums: list[int]) -> list[int]:
2    """For each element, find the next element that is strictly larger.
3    Returns -1 if no greater element exists to the right.
4
5    The stack maintains indices in monotonically decreasing order.
6    Each element is pushed and popped at most once — O(n) total."""
7
8    n = len(nums)
9    result = [-1] * n                 # default: no greater element
10    stack = []                        # stack of indices (decreasing values)
11
12    for i in range(n):
13        # Pop all elements smaller than current — they found their answer
14        while stack and nums[stack[-1]] < nums[i]:
15            idx = stack.pop()
16            result[idx] = nums[i]     # nums[i] is the next greater element
17        stack.append(i)               # push current index
18
19    return result
20
21# next_greater_element([2, 1, 2, 4, 3]) -> [4, 2, 4, -1, -1]