Семинар. Стек, очередь, дек

Семинар 7. Стек, очередь, дек

Лекция 7 дала ADT, синтаксис class, готовые class Stack и class RingQueue, collections.deque, проверку скобок и вычисление обратной польской записи. Связные структуры (class Node, очередь на узлах) остались помеченным звёздочкой разделом: на лекции их не разбирали.

Здесь вы собираете это руками: Stack и Queue классами, кольцевой буфер, дек, скобки и ОПЗ.

Договор пары: свою структуру пишем сами. collections.deque и list допустимы как эталон проверки — они стоят внутри check_queue и check_deque — и как рабочий инструмент в контесте, но в упражнениях 1–5 структуру собираем руками. Это условие пары, а не ограничение тестера.

Ноутбук — тетрадь пары. Его семинаристу не отправляйте. Зачёт пары — прорешанность задач контеста на algo.ai.msu.ru.

Заглушки возвращают неверный ответ — так и задумано, их надо переписать.

Как устроен ноутбук

Как на семинарах 1–5: ячейки Markdown и Code; командный режим — Esc, правка — Enter; Shift+Enter выполняет ячейку.

Скачайте с сайта курса этот файл .ipynb. Отдельного файла тестов на этой неделе нет: проверки встроены в ноутбук, зачёт — контест на платформе.

Ячейки с комментарием «Ваш эксперимент» никто автоматически не проверяет.

Порядок работы

инструменты проверки: check_stack, check_queue, check_deque, check_brackets_fn, check_rpn_fn;
1. стек классом;
2. очередь: наивная на списке и кольцевой буфер;
3. дек на кольцевом буфере;
4. скобочные структуры;
5. обратная польская запись;
6. необязательный хвост: связные структуры на ссылках;
контест на algo.ai.msu.ru.

Разделы 1–5 — обязательная часть пары. Раздел 6 — только для тех, кто закрыл обязательное; в оценивание он не входит.

Инструменты проверки

Эти функции уже написаны, их менять не нужно. Каждая гоняет вашу реализацию на случайных последовательностях операций и сверяет её с моделью — обычным списком, который ведёт себя как стек, очередь или дек.

collections.deque и list стоят внутри проверок, а не внутри решения: сравнивать свой ответ с эталоном — нормальная практика, сдавать эталон вместо решения — нет.

In [ ]:

import random
from collections import deque


def check_stack(Stack, trials=200, seed=0):
    """Стек: push/pop/is_empty/__len__ против списка-эталона.

    seed фиксирован, поэтому неудача воспроизводится.
    """
    rng = random.Random(seed)
    for _ in range(trials):
        s = Stack()
        model = []
        for _ in range(rng.randint(0, 30)):
            if model and rng.random() < 0.45:
                got, want = s.pop(), model.pop()
                if got != want:
                    print("pop:", got, "ожидалось", want)
                    return False
            else:
                x = rng.randint(-10, 10)
                s.push(x)
                model.append(x)
            if len(s) != len(model) or s.is_empty() != (not model):
                print("размер или is_empty расходятся:", len(s), len(model))
                return False
        while model:
            if s.pop() != model.pop():
                print("порядок извлечения не LIFO")
                return False
        if not s.is_empty():
            print("после опустошения is_empty() должно быть True")
            return False
    try:
        Stack().pop()
    except IndexError:
        pass
    else:
        print("pop на пустом стеке должен поднимать IndexError")
        return False
    print(f"ok: стек прошёл {trials} прогонов")
    return True


def check_queue(make_queue, trials=200, seed=0):
    """Очередь: push/pop/is_empty/__len__/front против списка-эталона.

    make_queue — функция без аргументов, создающая новую очередь.
    Если у очереди есть front(), проверяем и его.
    """
    rng = random.Random(seed)
    for _ in range(trials):
        q = make_queue()
        model = []
        for _ in range(rng.randint(0, 40)):
            if model and rng.random() < 0.45:
                got, want = q.pop(), model.pop(0)
                if got != want:
                    print("pop:", got, "ожидалось", want)
                    return False
            else:
                x = rng.randint(-10, 10)
                q.push(x)
                model.append(x)
            if len(q) != len(model) or q.is_empty() != (not model):
                print("размер или is_empty расходятся:", len(q), len(model))
                return False
            if model and hasattr(q, "front") and q.front() != model[0]:
                print("front:", q.front(), "ожидалось", model[0])
                return False
        while model:
            if q.pop() != model.pop(0):
                print("порядок извлечения не FIFO")
                return False
        if not q.is_empty():
            print("после опустошения is_empty() должно быть True")
            return False
    try:
        make_queue().pop()
    except IndexError:
        pass
    else:
        print("pop на пустой очереди должен поднимать IndexError")
        return False
    print(f"ok: очередь прошла {trials} прогонов")
    return True


def check_deque(Deque, trials=200, seed=0):
    """Дек: append/appendleft/pop/popleft против списка-эталона."""
    rng = random.Random(seed)
    for _ in range(trials):
        d = Deque()
        model = []
        for _ in range(rng.randint(0, 40)):
            left = rng.random() < 0.5
            if model and rng.random() < 0.4:
                got = d.popleft() if left else d.pop()
                want = model.pop(0) if left else model.pop()
                if got != want:
                    print("извлечение:", got, "ожидалось", want)
                    return False
            else:
                x = rng.randint(-10, 10)
                if left:
                    d.appendleft(x)
                    model.insert(0, x)
                else:
                    d.append(x)
                    model.append(x)
            if len(d) != len(model) or d.is_empty() != (not model):
                print("размер или is_empty расходятся:", len(d), len(model))
                return False
        while model:
            if d.popleft() != model.pop(0):
                print("остаток извлекается в неверном порядке")
                return False
        if not d.is_empty():
            print("после опустошения is_empty() должно быть True")
            return False
    try:
        Deque().pop()
    except IndexError:
        pass
    else:
        print("pop на пустом деке должен поднимать IndexError")
        return False
    print(f"ok: дек прошёл {trials} прогонов")
    return True


def check_brackets_fn(brackets_fn, trials=500, seed=0):
    """Скобки: фиксированные случаи и случайные строки против эталона."""
    fixed = {
        "([{}])": True, "([)]": False, "())": False, "(": False, "": True,
        "()[]{}": True, "{[()]}": True, "}": False, "(((": False, "())(": False,
        "a(b)c": True, "[(])": False,
    }
    for s, want in fixed.items():
        got = brackets_fn(s)
        if got != want:
            print(f"на {s!r} получено {got}, ожидалось {want}")
            return False

    def reference(s):
        left, right = "([{", ")]}"
        stack = []
        for ch in s:
            if ch in left:
                stack.append(ch)
            elif ch in right:
                if not stack or stack.pop() != left[right.find(ch)]:
                    return False
        return not stack

    rng = random.Random(seed)
    alphabet = "()[]{}abc"
    for _ in range(trials):
        s = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 12)))
        got, want = brackets_fn(s), reference(s)
        if got != want:
            print(f"на {s!r} получено {got}, ожидалось {want}")
            return False
    print(f"ok: скобки верны на {len(fixed)} примерах и {trials} случайных строках")
    return True


def check_rpn_fn(rpn_fn, trials=500, seed=0):
    """ОПЗ: фиксированные примеры и случайные выражения.

    Деление — с усечением к нулю, как в задаче 150: int(a / b), а не a // b.
    """
    fixed = [
        (["3", "4", "2", "*", "+"], 11),
        (["3", "4", "+", "2", "*"], 14),
        (["4", "2", "-"], 2),
        (["2", "4", "-"], -2),
        (["7", "2", "/"], 3),
        (["-7", "2", "/"], -3),
        (["3", "-4", "*"], -12),
        (["5"], 5),
    ]
    for tokens, want in fixed:
        got = rpn_fn(tokens[:])
        if got != want:
            print(f"на {' '.join(tokens)!r} получено {got}, ожидалось {want}")
            return False

    ops = ["+", "-", "*", "/"]

    def gen(rng, depth=0):
        # Глубина ограничена: ветвящийся процесс с вероятностью оператора 0.5
        # и больше не заканчивается.
        if depth >= 3 or rng.random() < 0.5:
            return str(rng.randint(-9, 9))
        a, b = gen(rng, depth + 1), gen(rng, depth + 1)
        return f"{a} {b} {rng.choice(ops)}"

    def reference(tokens):
        stack = []
        for t in tokens:
            if t in ops:
                b, a = stack.pop(), stack.pop()
                if t == "+":
                    stack.append(a + b)
                elif t == "-":
                    stack.append(a - b)
                elif t == "*":
                    stack.append(a * b)
                else:
                    stack.append(int(a / b))
            else:
                stack.append(int(t))
        return stack[-1]

    rng = random.Random(seed)
    for _ in range(trials):
        while True:
            tokens = gen(rng).split()
            try:
                want = reference(tokens)
                break
            except ZeroDivisionError:
                continue  # в 150 деления на ноль не бывает, пропускаем такое выражение
        got = rpn_fn(tokens[:])
        if got != want:
            print(f"на {' '.join(tokens)!r} получено {got}, ожидалось {want}")
            return False
    print(f"ok: ОПЗ верна на {len(fixed)} примерах и {trials} случайных выражениях")
    return True


print("инструменты готовы")

1. Стек классом

Список-стек не защищает инвариант: данные и операции живут порознь. Класс собирает их под одним именем. Минимум синтаксиса дан на лекции: class, self, __init__, методы, __repr__, __len__.

Интерфейс: push, pop (на пустом стеке — IndexError), is_empty, len(s), печать в виде Stack([...]).

Внутри хранится список, и стек — это конец списка: append и pop() дают амортизированное $O(1)$, дополнительная память $\Theta(n)$ под сами данные.

Ловушка. print(s, s.pop()) печатает стек после извлечения: все аргументы вычисляются до вызова print. Такие однострочники со скрытой мутацией дают «странные» распечатки.

In [ ]:

class Stack:
    def __init__(self):
        self.data = []

    def push(self, x):
        """Положить x наверх."""
        return None

    def pop(self):
        """Снять верхний элемент; на пустом стеке — IndexError."""
        return None

    def is_empty(self):
        """True, если элементов нет."""
        return True

    def __len__(self):
        """Число элементов."""
        return 0

    def __repr__(self):
        """Печать вида Stack([1, 2])."""
        return "Stack([])"


s = Stack()
s.push(1)
s.push(2)
print(s, len(s))   # ожидается Stack([1, 2]) 2
print(s.pop())     # ожидается 2
print(s, len(s))   # ожидается Stack([1]) 1

check_stack(Stack)

2. Очередь: список и кольцевой буфер

Очередь — FIFO: добавляем в хвост, извлекаем из головы.

Наивно: append в хвост и pop(0) из головы. Извлечение стоит $\Theta(n)$ — все оставшиеся элементы сдвигаются; на серии из $n$ операций это $\Theta(n^2)$. Так очередь не делают.

Кольцевой буфер. Массив фиксированной ёмкости плюс head и size. Хвост стоит на позиции (head + size) % len(data), поэтому конец массива заворачивается в начало и сдвигать ничего не нужно. При заполнении ёмкость удваивается — получается амортизированное $O(1)$ на операцию.

Сравните с динамическим массивом: у стека амортизация на одном конце, у очереди нужен второй конец — отсюда head и модуль.

В контесте задача № 5 (622) — ровно эта структура, но без роста: при заполнении enQueue возвращает False, Front отвечает на front(), а isFull — на is_full().

In [ ]:

class ListQueue:
    """Наивная очередь: хвост — конец списка, голова — начало."""

    def __init__(self):
        self.data = []

    def push(self, x):
        """Добавить x в хвост."""
        return None

    def pop(self):
        """Извлечь голову; на пустой очереди — IndexError."""
        return None

    def is_empty(self):
        return not self.data

    def __len__(self):
        return len(self.data)

    def front(self):
        if not self.data:
            raise IndexError("front from empty queue")
        return self.data[0]


q = ListQueue()
for x in (1, 2, 3):
    q.push(x)
print(q.pop(), q.pop(), q.pop())   # ожидается 1 2 3
check_queue(ListQueue)

In [ ]:

# Ваш эксперимент: почему ListQueue плохо работает на длинной серии?
# Оцените число сдвигов при 10^4 парах «push + pop» и сравните с deque.
# Здесь важен вывод, а не секунды: сдвиг — это Theta(n) на каждое извлечение.

Кольцевой буфер

head — индекс головы, size — сколько элементов лежит сейчас. Хвост — (head + size) % len(data). В ячейке ниже даны _index, is_empty, __len__ и _grow; допишите push, pop, front.

Обратите внимание на порядок в _grow: элементы нужно переложить по порядку обхода, начиная с головы, а не по физическим индексам массива. После роста head становится нулём.

Рост — это то, чего нет в задаче 622: там фиксированная ёмкость и отказ при переполнении.

In [ ]:

class RingQueue:
    def __init__(self, capacity=4):
        self.data = [None] * capacity
        self.head = 0
        self.size = 0

    def _index(self, i):
        """Индекс i-го по порядку элемента в массиве ёмкости len(self.data)."""
        return (self.head + i) % len(self.data)

    def push(self, x):
        """Добавить x в хвост; при заполнении удвоить ёмкость."""
        return None

    def pop(self):
        """Извлечь голову; на пустой очереди — IndexError."""
        return None

    def front(self):
        """Голова, не извлекая; на пустой очереди — IndexError."""
        return None

    def is_empty(self):
        return self.size == 0

    def __len__(self):
        return self.size

    def _grow(self):
        """Переложить элементы по порядку в массив вдвое большей ёмкости."""
        return None


q = RingQueue(2)                 # ёмкость заведомо мала: проверим рост
for x in (1, 2, 3, 4):
    q.push(x)
print([q.pop() for _ in range(4)])   # ожидается [1, 2, 3, 4]
check_queue(lambda: RingQueue(1))

3. Дек на кольцевом буфере

Дек — очередь с двумя концами: append, appendleft, pop, popleft. На том же буфере достаточно двигать head в обе стороны и следить за size; при заполнении ёмкость удваивается, как у очереди.

В стандартной библиотеке эталон — collections.deque: внутри блоки узлов, $O(1)$ на обоих концах. В контесте им пользоваться можно; в этом упражнении — нет, иначе упражнение бессмысленно.

Минимум в скользящем окне (задача № 11, 239) на паре не разбираем: для него нужен монотонный дек, это отдельный приём.

In [ ]:

class Deque:
    def __init__(self, capacity=4):
        self.data = [None] * capacity
        self.head = 0
        self.size = 0

    def append(self, x):
        """Положить x в хвост."""
        return None

    def appendleft(self, x):
        """Положить x в голову."""
        return None

    def pop(self):
        """Извлечь хвост; на пустом деке — IndexError."""
        return None

    def popleft(self):
        """Извлечь голову; на пустом деке — IndexError."""
        return None

    def is_empty(self):
        return self.size == 0

    def __len__(self):
        return self.size

    def _grow(self):
        """Переложить элементы по порядку, начиная с головы, в массив вдвое большей ёмкости."""
        return None


d = Deque()
d.append(1)        # [1]
d.appendleft(0)    # [0, 1]
d.append(2)        # [0, 1, 2]
print(d.popleft(), d.pop(), d.popleft())   # ожидается 0 2 1
check_deque(Deque)

4. Скобочные структуры

Строка из символов ()[]{}; прочие символы игнорируем. Нужно проверить, что последовательность правильная: каждая закрывающая соответствует последней незакрытой открывающей того же типа, и в конце незакрытых не остаётся.

Одних счётчиков мало: ([)] сходится по балансу, но порядок вложенности нарушен. Нужна память о последнем незакрытом — это стек.

Время $\Theta(n)$, память $O(n)$ в худшем случае: вся строка из открывающих.

In [ ]:

LEFT_BRACKETS = "([{"
RIGHT_BRACKETS = ")]}"


def check_brackets(s):
    """True, если скобочная последовательность правильная; прочие символы игнорируем."""
    return True


for s in ["([{}])", "([)]", "())", "(", ""]:
    print(repr(s), "->", check_brackets(s))
# ожидается True False False False True

check_brackets_fn(check_brackets)

5. Обратная польская запись

Три формы одного выражения: инфиксная 3 + 4 * 2, префиксная + 3 * 4 2, постфиксная 3 4 2 * +. В постфиксной нет скобок и приоритетов, поэтому она вычисляется одним проходом: число кладём в стек, оператор снимает два верхних и кладёт результат.

Порядок операндов важен: первым снимается правый. Для 4 2 - ответ 2, для 2 4 - ответ -2. Это самая частая ошибка при сборке кода.

Ловушка деления. В задаче № 6 (150) деление должно усекаться к нулю: -7 2 / даёт -3. Оператор // в Python округляет вниз и даст -4. Берите int(a / b).

Переход от инфиксной записи к постфиксной (сортировочная станция Дейкстры) в эту пару не входит.

In [ ]:

OPS = {
    "+": lambda a, b: a + b,
    "-": lambda a, b: a - b,
    "*": lambda a, b: a * b,
    "/": lambda a, b: int(a / b),   # усечение к нулю, как в 150; // здесь неверно
}


def eval_rpn(tokens):
    """Значение выражения в обратной польской записи; tokens — список строк."""
    return 0


print(eval_rpn("3 4 2 * +".split()))   # ожидается 11
print(eval_rpn("3 4 + 2 *".split()))   # ожидается 14
print(eval_rpn("-7 2 /".split()))      # ожидается -3

check_rpn_fn(eval_rpn)

6. Необязательный хвост: связные структуры

Раздел 7 лекции, помеченный звёздочкой: на лекции он не разбирался, в обязательную часть и в оценивание не входит. Возвращайтесь сюда, только если разделы 1–5 закрыты.

Идея: у массива доступ по индексу $O(1)$, но вставка и удаление в начале стоят $\Theta(n)$ и могут требовать перевыделения. Альтернатива — хранить в элементе ссылку на следующий. Односвязный список оканчивается None: вставка в голову — $O(1)$, доступ к $k$-му элементу — $O(k)$.

In [ ]:

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

    def __repr__(self):
        return f"Node({self.value!r})"


class LinkedStack:
    def __init__(self):
        self.head = None

    def push(self, value):
        """Новый узел становится головой."""
        return None

    def pop(self):
        """Снять голову; на пустом стеке — IndexError."""
        return None

    def is_empty(self):
        return self.head is None


ls = LinkedStack()
for x in (1, 2, 3):
    ls.push(x)
print([ls.pop() for _ in range(3)])   # ожидается [3, 2, 1]

# Загадка: что напечатает a = [1]; a.append(a) и почему?
# Проверьте в отдельной ячейке и объясните, при чём тут repr.

In [ ]:

class LinkedQueue:
    def __init__(self):
        self.head = None
        self.tail = None

    def push(self, value):
        """Добавить в хвост. Отдельно разберите случай пустой очереди."""
        return None

    def pop(self):
        """Извлечь голову; на пустой — IndexError. Не забудьте сбросить tail."""
        return None

    def is_empty(self):
        return self.head is None


lq = LinkedQueue()
for x in range(1, 5):
    lq.push(x)
print([lq.pop() for _ in range(4)])       # ожидается [1, 2, 3, 4]
print("хвост сброшен:", lq.tail is None)  # ожидается True

# Проверьте ещё два случая: pop из пустой очереди и очередь из одного элемента.
# Что будет с tail, если его не сбросить при опустошении?

Контест

Задачи сдавайте в контест недели 7 на algo.ai.msu.ru. Номера LeetCode помогают найти условие.

Для зачёта семинара обязательны № 5 (622. Design Circular Queue) и № 6 (150. Evaluate Reverse Polish Notation). Разминка и задачи по желанию их не заменяют.

№	Задача	Статус на семинаре	Что из ноутбука
1	20. Valid Parentheses	Разминка	`check_brackets`; проверьте `())` и `(`
2	232. Implement Queue using Stacks	Разминка	интерфейс очереди: один стек на вход, второй на выход
3	1047. Remove All Adjacent Duplicates In String	Разминка	стек как «отложенное решение»: сравниваем верх с текущим символом
4	933. Number of Recent Calls	Разминка	очередь как окно: `popleft`, пока голова старше `t - 3000`
5	622. Design Circular Queue	Обязательная	`RingQueue`: `head`, `size`, `%`; здесь нет роста, зато нужны `Front`, `Rear`, `isFull`
6	150. Evaluate Reverse Polish Notation	Обязательная	`eval_rpn`; порядок `a`, `b` и усечение деления к нулю
7	641. Design Circular Deque	По желанию	`Deque`; парная к № 5, тот же буфер с двух концов
8	155. Min Stack	По желанию	стек с инвариантом: второй стек хранит минимумы
9	71. Simplify Path	По желанию	стек для разбора пути: `..` снимает верх
10	946. Validate Stack Sequences	По желанию	симуляция: пушим `pushed`, снимаем, когда верх совпал с `popped`
11	239. Sliding Window Maximum ★	По желанию	монотонный дек; приём вне лекции, только после обязательных

Порядок работы. Разминку № 1–4 закрывайте быстро, они на один приём каждая. Дальше № 5: в ней ровно та структура, которую вы писали в разделе 2, только без роста. Потом № 6. Остальное — по желанию и дома.

Типичный WA: в ОПЗ берут операнды в обратном порядке; делят через // и получают -4 вместо -3; в скобках проверяют только баланс; в № 5 путают Front и Rear и забывают, что при переполнении enQueue возвращает False, а не растит массив.

Типичный TLE: очередь на list.pop(0) в № 4 и № 10; поиск минимума в Min Stack линейным проходом вместо второго стека.

Про свой код и стандартную библиотеку. В контесте collections.deque разрешён. В упражнениях ноутбука — нет: RingQueue и Deque пишем сами. Проверки сравнивают результат с моделью, а не смотрят, чем вы пользовались; на паре мы спрашиваем структуру у доски.

Шпаргалка

Стек (LIFO):

внутри список, работаем с концом: append / pop() — амортизированное $O(1)$;
pop(0) — $\Theta(n)$: все оставшиеся элементы сдвигаются.

Очередь (FIFO):

кольцевой буфер: head, size, хвост (head + size) % len(data);
рост удвоением — амортизированное $O(1)$; извлечение ничего не сдвигает;
в 622 роста нет: при size == len(data) возвращаем False.

Дек:

тот же буфер, head двигается в обе стороны; эталон — collections.deque, $O(1)$ на концах.

Скобки:

стек последних незакрытых; при закрывающей стек не пуст и верх совпал по типу;
в конце стек пуст. ([)] — ловушка «одних счётчиков мало».

ОПЗ:

число — в стек; оператор снимает правый, потом левый: b = pop(); a = pop();
деление в 150 усекается к нулю: int(a / b), а не a // b.

Классы:

self — первый параметр метода; __init__ вызывается при Stack();
__repr__ управляет печатью, __len__ — функцией len;
инкапсуляции в Python нет: _data — договорённость, а не запрет.

Связные структуры (необязательно): Node(value, next), вставка в голову $O(1)$; очередь на узлах требует tail.

Сдача

Этот .ipynb семинаристу отправлять не нужно.
Для зачёта выполните № 5 — 622. Design Circular Queue и № 6 — 150. Evaluate Reverse Polish Notation в контесте на algo.ai.msu.ru.
Разминка № 1–4 и задачи № 7–11 выполняются по желанию, для зачёта не требуются.
Если обязательные задачи не закончены на паре, дорешайте их в том же контесте после занятия.
Отдельного ДЗ на этой неделе нет.
Стек, очередь и дек входят в программу коллоквиума 2 и контрольной 2: спросят интерфейс, цену операций и кольцевой буфер.