Стек, очередь и монотонный стек

stack = []
stack.append("a")        # push — O(1)
stack.append("b")
stack.append("c")
print(stack[-1])         # top/peek — O(1)
print(stack.pop())       # pop — O(1)
print(stack, bool(stack))

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        print(f"  {ch!r}: стек = {stack}")
    return not stack                      # в конце всё должно быть закрыто

print(is_valid("{[()]}"))
print(is_valid("([)]"))

def simplify_path(path):
    stack = []
    for part in path.split("/"):
        if part == "..":
            if stack:
                stack.pop()
        elif part and part != ".":
            stack.append(part)
    return "/" + "/".join(stack)

print(simplify_path("/home//anna/./docs/../photos/"))

def decode(s):
    """3[a2[c]] → accaccacc"""
    stack = []
    current, num = "", 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == "[":
            stack.append((current, num))      # запомнить, что было до скобки
            current, num = "", 0
        elif ch == "]":
            prev, k = stack.pop()
            current = prev + current * k
        else:
            current += ch
    return current

print(decode("3[a2[c]]"), decode("2[ab]3[x]"))

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                                   # индексы; значения в стеке убывают
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:     # x — следующий больший для них
            result[stack.pop()] = x
        stack.append(i)
    return result

print(next_greater([2, 1, 2, 4, 3]))
print(next_greater([5, 4, 3, 2, 1]))

def largest_rectangle(heights):
    """Самый большой прямоугольник в гистограмме — классическая hard-задача."""
    stack = []                                   # индексы столбцов с возрастающей высотой
    best = 0
    for i, h in enumerate(heights + [0]):        # 0 в конце «выталкивает» всё
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            best = max(best, height * (i - idx))
            start = idx
        stack.append((start, h))
    return best

print(largest_rectangle([2, 1, 5, 6, 2, 3]))

from collections import deque

queue = deque()
queue.append("первый")       # enqueue — O(1)
queue.append("второй")
queue.append("третий")
print(queue.popleft())       # dequeue — O(1)
print(queue[0], len(queue))  # peek

class QueueOnStacks:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def push(self, x):
        self.inbox.append(x)

    def pop(self):
        if not self.outbox:                       # перекладываем, только когда outbox пуст
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop()

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

from collections import deque

def window_max(nums, k):
    dq = deque()                         # индексы; значения убывают
    result = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:  # меньшие элементы больше никогда не станут максимумом
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:               # вышел из окна
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))