{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "intro",
   "metadata": {},
   "source": [
    "# Семинар 7. Стек, очередь, дек\n",
    "\n",
    "Лекция 7 дала ADT, синтаксис `class`, готовые `class Stack` и `class RingQueue`, `collections.deque`, проверку скобок и вычисление обратной польской записи. Связные структуры (`class Node`, очередь на узлах) остались помеченным звёздочкой разделом: на лекции их не разбирали.\n",
    "\n",
    "Здесь вы собираете это руками: `Stack` и `Queue` классами, кольцевой буфер, дек, скобки и ОПЗ.\n",
    "\n",
    "**Договор пары: свою структуру пишем сами.** `collections.deque` и `list` допустимы как **эталон проверки** — они стоят внутри `check_queue` и `check_deque` — и как рабочий инструмент в контесте, но в упражнениях 1–5 структуру собираем руками. Это условие пары, а не ограничение тестера.\n",
    "\n",
    "Ноутбук — тетрадь пары. **Его семинаристу не отправляйте.** Зачёт пары — прорешанность задач контеста на [algo.ai.msu.ru](https://algo.ai.msu.ru).\n",
    "\n",
    "Заглушки возвращают неверный ответ — так и задумано, их надо переписать.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "jupyter",
   "metadata": {},
   "source": [
    "## Как устроен ноутбук\n",
    "\n",
    "Как на семинарах 1–5: ячейки **Markdown** и **Code**; командный режим — `Esc`, правка — `Enter`; `Shift+Enter` выполняет ячейку.\n",
    "\n",
    "Скачайте с сайта курса [этот файл `.ipynb`](https://learn.ai.msu.ru/algo/1/07/seminar.ipynb). Отдельного файла тестов на этой неделе нет: проверки встроены в ноутбук, зачёт — контест на платформе.\n",
    "\n",
    "Ячейки с комментарием «Ваш эксперимент» никто автоматически не проверяет.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "roadmap",
   "metadata": {},
   "source": [
    "## Порядок работы\n",
    "\n",
    "- инструменты проверки: `check_stack`, `check_queue`, `check_deque`, `check_brackets_fn`, `check_rpn_fn`;\n",
    "- **1.** стек классом;\n",
    "- **2.** очередь: наивная на списке и кольцевой буфер;\n",
    "- **3.** дек на кольцевом буфере;\n",
    "- **4.** скобочные структуры;\n",
    "- **5.** обратная польская запись;\n",
    "- **6.** необязательный хвост: связные структуры на ссылках;\n",
    "- контест на [algo.ai.msu.ru](https://algo.ai.msu.ru).\n",
    "\n",
    "Разделы 1–5 — обязательная часть пары. Раздел 6 — только для тех, кто закрыл обязательное; в оценивание он не входит.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "tools_md",
   "metadata": {},
   "source": [
    "## Инструменты проверки\n",
    "\n",
    "Эти функции уже написаны, их менять не нужно. Каждая гоняет вашу реализацию на случайных последовательностях операций и сверяет её с моделью — обычным списком, который ведёт себя как стек, очередь или дек.\n",
    "\n",
    "`collections.deque` и `list` стоят **внутри проверок**, а не внутри решения: сравнивать свой ответ с эталоном — нормальная практика, сдавать эталон вместо решения — нет.\n"
   ]
  },
  {
   "cell_type": "code",
   "id": "tools_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import random\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "def check_stack(Stack, trials=200, seed=0):\n",
    "    \"\"\"Стек: push/pop/is_empty/__len__ против списка-эталона.\n",
    "\n",
    "    seed фиксирован, поэтому неудача воспроизводится.\n",
    "    \"\"\"\n",
    "    rng = random.Random(seed)\n",
    "    for _ in range(trials):\n",
    "        s = Stack()\n",
    "        model = []\n",
    "        for _ in range(rng.randint(0, 30)):\n",
    "            if model and rng.random() < 0.45:\n",
    "                got, want = s.pop(), model.pop()\n",
    "                if got != want:\n",
    "                    print(\"pop:\", got, \"ожидалось\", want)\n",
    "                    return False\n",
    "            else:\n",
    "                x = rng.randint(-10, 10)\n",
    "                s.push(x)\n",
    "                model.append(x)\n",
    "            if len(s) != len(model) or s.is_empty() != (not model):\n",
    "                print(\"размер или is_empty расходятся:\", len(s), len(model))\n",
    "                return False\n",
    "        while model:\n",
    "            if s.pop() != model.pop():\n",
    "                print(\"порядок извлечения не LIFO\")\n",
    "                return False\n",
    "        if not s.is_empty():\n",
    "            print(\"после опустошения is_empty() должно быть True\")\n",
    "            return False\n",
    "    try:\n",
    "        Stack().pop()\n",
    "    except IndexError:\n",
    "        pass\n",
    "    else:\n",
    "        print(\"pop на пустом стеке должен поднимать IndexError\")\n",
    "        return False\n",
    "    print(f\"ok: стек прошёл {trials} прогонов\")\n",
    "    return True\n",
    "\n",
    "\n",
    "def check_queue(make_queue, trials=200, seed=0):\n",
    "    \"\"\"Очередь: push/pop/is_empty/__len__/front против списка-эталона.\n",
    "\n",
    "    make_queue — функция без аргументов, создающая новую очередь.\n",
    "    Если у очереди есть front(), проверяем и его.\n",
    "    \"\"\"\n",
    "    rng = random.Random(seed)\n",
    "    for _ in range(trials):\n",
    "        q = make_queue()\n",
    "        model = []\n",
    "        for _ in range(rng.randint(0, 40)):\n",
    "            if model and rng.random() < 0.45:\n",
    "                got, want = q.pop(), model.pop(0)\n",
    "                if got != want:\n",
    "                    print(\"pop:\", got, \"ожидалось\", want)\n",
    "                    return False\n",
    "            else:\n",
    "                x = rng.randint(-10, 10)\n",
    "                q.push(x)\n",
    "                model.append(x)\n",
    "            if len(q) != len(model) or q.is_empty() != (not model):\n",
    "                print(\"размер или is_empty расходятся:\", len(q), len(model))\n",
    "                return False\n",
    "            if model and hasattr(q, \"front\") and q.front() != model[0]:\n",
    "                print(\"front:\", q.front(), \"ожидалось\", model[0])\n",
    "                return False\n",
    "        while model:\n",
    "            if q.pop() != model.pop(0):\n",
    "                print(\"порядок извлечения не FIFO\")\n",
    "                return False\n",
    "        if not q.is_empty():\n",
    "            print(\"после опустошения is_empty() должно быть True\")\n",
    "            return False\n",
    "    try:\n",
    "        make_queue().pop()\n",
    "    except IndexError:\n",
    "        pass\n",
    "    else:\n",
    "        print(\"pop на пустой очереди должен поднимать IndexError\")\n",
    "        return False\n",
    "    print(f\"ok: очередь прошла {trials} прогонов\")\n",
    "    return True\n",
    "\n",
    "\n",
    "def check_deque(Deque, trials=200, seed=0):\n",
    "    \"\"\"Дек: append/appendleft/pop/popleft против списка-эталона.\"\"\"\n",
    "    rng = random.Random(seed)\n",
    "    for _ in range(trials):\n",
    "        d = Deque()\n",
    "        model = []\n",
    "        for _ in range(rng.randint(0, 40)):\n",
    "            left = rng.random() < 0.5\n",
    "            if model and rng.random() < 0.4:\n",
    "                got = d.popleft() if left else d.pop()\n",
    "                want = model.pop(0) if left else model.pop()\n",
    "                if got != want:\n",
    "                    print(\"извлечение:\", got, \"ожидалось\", want)\n",
    "                    return False\n",
    "            else:\n",
    "                x = rng.randint(-10, 10)\n",
    "                if left:\n",
    "                    d.appendleft(x)\n",
    "                    model.insert(0, x)\n",
    "                else:\n",
    "                    d.append(x)\n",
    "                    model.append(x)\n",
    "            if len(d) != len(model) or d.is_empty() != (not model):\n",
    "                print(\"размер или is_empty расходятся:\", len(d), len(model))\n",
    "                return False\n",
    "        while model:\n",
    "            if d.popleft() != model.pop(0):\n",
    "                print(\"остаток извлекается в неверном порядке\")\n",
    "                return False\n",
    "        if not d.is_empty():\n",
    "            print(\"после опустошения is_empty() должно быть True\")\n",
    "            return False\n",
    "    try:\n",
    "        Deque().pop()\n",
    "    except IndexError:\n",
    "        pass\n",
    "    else:\n",
    "        print(\"pop на пустом деке должен поднимать IndexError\")\n",
    "        return False\n",
    "    print(f\"ok: дек прошёл {trials} прогонов\")\n",
    "    return True\n",
    "\n",
    "\n",
    "def check_brackets_fn(brackets_fn, trials=500, seed=0):\n",
    "    \"\"\"Скобки: фиксированные случаи и случайные строки против эталона.\"\"\"\n",
    "    fixed = {\n",
    "        \"([{}])\": True, \"([)]\": False, \"())\": False, \"(\": False, \"\": True,\n",
    "        \"()[]{}\": True, \"{[()]}\": True, \"}\": False, \"(((\": False, \"())(\": False,\n",
    "        \"a(b)c\": True, \"[(])\": False,\n",
    "    }\n",
    "    for s, want in fixed.items():\n",
    "        got = brackets_fn(s)\n",
    "        if got != want:\n",
    "            print(f\"на {s!r} получено {got}, ожидалось {want}\")\n",
    "            return False\n",
    "\n",
    "    def reference(s):\n",
    "        left, right = \"([{\", \")]}\"\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if ch in left:\n",
    "                stack.append(ch)\n",
    "            elif ch in right:\n",
    "                if not stack or stack.pop() != left[right.find(ch)]:\n",
    "                    return False\n",
    "        return not stack\n",
    "\n",
    "    rng = random.Random(seed)\n",
    "    alphabet = \"()[]{}abc\"\n",
    "    for _ in range(trials):\n",
    "        s = \"\".join(rng.choice(alphabet) for _ in range(rng.randint(0, 12)))\n",
    "        got, want = brackets_fn(s), reference(s)\n",
    "        if got != want:\n",
    "            print(f\"на {s!r} получено {got}, ожидалось {want}\")\n",
    "            return False\n",
    "    print(f\"ok: скобки верны на {len(fixed)} примерах и {trials} случайных строках\")\n",
    "    return True\n",
    "\n",
    "\n",
    "def check_rpn_fn(rpn_fn, trials=500, seed=0):\n",
    "    \"\"\"ОПЗ: фиксированные примеры и случайные выражения.\n",
    "\n",
    "    Деление — с усечением к нулю, как в задаче 150: int(a / b), а не a // b.\n",
    "    \"\"\"\n",
    "    fixed = [\n",
    "        ([\"3\", \"4\", \"2\", \"*\", \"+\"], 11),\n",
    "        ([\"3\", \"4\", \"+\", \"2\", \"*\"], 14),\n",
    "        ([\"4\", \"2\", \"-\"], 2),\n",
    "        ([\"2\", \"4\", \"-\"], -2),\n",
    "        ([\"7\", \"2\", \"/\"], 3),\n",
    "        ([\"-7\", \"2\", \"/\"], -3),\n",
    "        ([\"3\", \"-4\", \"*\"], -12),\n",
    "        ([\"5\"], 5),\n",
    "    ]\n",
    "    for tokens, want in fixed:\n",
    "        got = rpn_fn(tokens[:])\n",
    "        if got != want:\n",
    "            print(f\"на {' '.join(tokens)!r} получено {got}, ожидалось {want}\")\n",
    "            return False\n",
    "\n",
    "    ops = [\"+\", \"-\", \"*\", \"/\"]\n",
    "\n",
    "    def gen(rng, depth=0):\n",
    "        # Глубина ограничена: ветвящийся процесс с вероятностью оператора 0.5\n",
    "        # и больше не заканчивается.\n",
    "        if depth >= 3 or rng.random() < 0.5:\n",
    "            return str(rng.randint(-9, 9))\n",
    "        a, b = gen(rng, depth + 1), gen(rng, depth + 1)\n",
    "        return f\"{a} {b} {rng.choice(ops)}\"\n",
    "\n",
    "    def reference(tokens):\n",
    "        stack = []\n",
    "        for t in tokens:\n",
    "            if t in ops:\n",
    "                b, a = stack.pop(), stack.pop()\n",
    "                if t == \"+\":\n",
    "                    stack.append(a + b)\n",
    "                elif t == \"-\":\n",
    "                    stack.append(a - b)\n",
    "                elif t == \"*\":\n",
    "                    stack.append(a * b)\n",
    "                else:\n",
    "                    stack.append(int(a / b))\n",
    "            else:\n",
    "                stack.append(int(t))\n",
    "        return stack[-1]\n",
    "\n",
    "    rng = random.Random(seed)\n",
    "    for _ in range(trials):\n",
    "        while True:\n",
    "            tokens = gen(rng).split()\n",
    "            try:\n",
    "                want = reference(tokens)\n",
    "                break\n",
    "            except ZeroDivisionError:\n",
    "                continue  # в 150 деления на ноль не бывает, пропускаем такое выражение\n",
    "        got = rpn_fn(tokens[:])\n",
    "        if got != want:\n",
    "            print(f\"на {' '.join(tokens)!r} получено {got}, ожидалось {want}\")\n",
    "            return False\n",
    "    print(f\"ok: ОПЗ верна на {len(fixed)} примерах и {trials} случайных выражениях\")\n",
    "    return True\n",
    "\n",
    "\n",
    "print(\"инструменты готовы\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "stack_md",
   "metadata": {},
   "source": [
    "## 1. Стек классом\n",
    "\n",
    "Список-стек не защищает инвариант: данные и операции живут порознь. Класс собирает их под одним именем. Минимум синтаксиса дан на лекции: `class`, `self`, `__init__`, методы, `__repr__`, `__len__`.\n",
    "\n",
    "Интерфейс: `push`, `pop` (на пустом стеке — `IndexError`), `is_empty`, `len(s)`, печать в виде `Stack([...])`.\n",
    "\n",
    "Внутри хранится список, и стек — это **конец** списка: `append` и `pop()` дают амортизированное $O(1)$, дополнительная память $\\Theta(n)$ под сами данные.\n",
    "\n",
    "**Ловушка.** `print(s, s.pop())` печатает стек **после** извлечения: все аргументы вычисляются до вызова `print`. Такие однострочники со скрытой мутацией дают «странные» распечатки.\n"
   ]
  },
  {
   "cell_type": "code",
   "id": "stack_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "\n",
    "    def push(self, x):\n",
    "        \"\"\"Положить x наверх.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def pop(self):\n",
    "        \"\"\"Снять верхний элемент; на пустом стеке — IndexError.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def is_empty(self):\n",
    "        \"\"\"True, если элементов нет.\"\"\"\n",
    "        return True\n",
    "\n",
    "    def __len__(self):\n",
    "        \"\"\"Число элементов.\"\"\"\n",
    "        return 0\n",
    "\n",
    "    def __repr__(self):\n",
    "        \"\"\"Печать вида Stack([1, 2]).\"\"\"\n",
    "        return \"Stack([])\"\n",
    "\n",
    "\n",
    "s = Stack()\n",
    "s.push(1)\n",
    "s.push(2)\n",
    "print(s, len(s))   # ожидается Stack([1, 2]) 2\n",
    "print(s.pop())     # ожидается 2\n",
    "print(s, len(s))   # ожидается Stack([1]) 1\n",
    "\n",
    "check_stack(Stack)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "queue_md",
   "metadata": {},
   "source": [
    "## 2. Очередь: список и кольцевой буфер\n",
    "\n",
    "Очередь — FIFO: добавляем в хвост, извлекаем из головы.\n",
    "\n",
    "Наивно: `append` в хвост и `pop(0)` из головы. Извлечение стоит $\\Theta(n)$ — все оставшиеся элементы сдвигаются; на серии из $n$ операций это $\\Theta(n^2)$. Так очередь не делают.\n",
    "\n",
    "**Кольцевой буфер.** Массив фиксированной ёмкости плюс `head` и `size`. Хвост стоит на позиции `(head + size) % len(data)`, поэтому конец массива заворачивается в начало и сдвигать ничего не нужно. При заполнении ёмкость удваивается — получается амортизированное $O(1)$ на операцию.\n",
    "\n",
    "Сравните с динамическим массивом: у стека амортизация на одном конце, у очереди нужен второй конец — отсюда `head` и модуль.\n",
    "\n",
    "В контесте задача № 5 (622) — ровно эта структура, но **без роста**: при заполнении `enQueue` возвращает `False`, `Front` отвечает на `front()`, а `isFull` — на `is_full()`.\n"
   ]
  },
  {
   "cell_type": "code",
   "id": "listqueue_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class ListQueue:\n",
    "    \"\"\"Наивная очередь: хвост — конец списка, голова — начало.\"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "\n",
    "    def push(self, x):\n",
    "        \"\"\"Добавить x в хвост.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def pop(self):\n",
    "        \"\"\"Извлечь голову; на пустой очереди — IndexError.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def is_empty(self):\n",
    "        return not self.data\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self.data)\n",
    "\n",
    "    def front(self):\n",
    "        if not self.data:\n",
    "            raise IndexError(\"front from empty queue\")\n",
    "        return self.data[0]\n",
    "\n",
    "\n",
    "q = ListQueue()\n",
    "for x in (1, 2, 3):\n",
    "    q.push(x)\n",
    "print(q.pop(), q.pop(), q.pop())   # ожидается 1 2 3\n",
    "check_queue(ListQueue)\n"
   ]
  },
  {
   "cell_type": "code",
   "id": "listqueue_exp",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Ваш эксперимент: почему ListQueue плохо работает на длинной серии?\n",
    "# Оцените число сдвигов при 10^4 парах «push + pop» и сравните с deque.\n",
    "# Здесь важен вывод, а не секунды: сдвиг — это Theta(n) на каждое извлечение.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ring_md",
   "metadata": {},
   "source": [
    "### Кольцевой буфер\n",
    "\n",
    "`head` — индекс головы, `size` — сколько элементов лежит сейчас. Хвост — `(head + size) % len(data)`. В ячейке ниже даны `_index`, `is_empty`, `__len__` и `_grow`; допишите `push`, `pop`, `front`.\n",
    "\n",
    "Обратите внимание на порядок в `_grow`: элементы нужно переложить **по порядку обхода**, начиная с головы, а не по физическим индексам массива. После роста `head` становится нулём.\n",
    "\n",
    "Рост — это то, чего нет в задаче 622: там фиксированная ёмкость и отказ при переполнении.\n"
   ]
  },
  {
   "cell_type": "code",
   "id": "ring_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class RingQueue:\n",
    "    def __init__(self, capacity=4):\n",
    "        self.data = [None] * capacity\n",
    "        self.head = 0\n",
    "        self.size = 0\n",
    "\n",
    "    def _index(self, i):\n",
    "        \"\"\"Индекс i-го по порядку элемента в массиве ёмкости len(self.data).\"\"\"\n",
    "        return (self.head + i) % len(self.data)\n",
    "\n",
    "    def push(self, x):\n",
    "        \"\"\"Добавить x в хвост; при заполнении удвоить ёмкость.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def pop(self):\n",
    "        \"\"\"Извлечь голову; на пустой очереди — IndexError.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def front(self):\n",
    "        \"\"\"Голова, не извлекая; на пустой очереди — IndexError.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.size == 0\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "\n",
    "    def _grow(self):\n",
    "        \"\"\"Переложить элементы по порядку в массив вдвое большей ёмкости.\"\"\"\n",
    "        return None\n",
    "\n",
    "\n",
    "q = RingQueue(2)                 # ёмкость заведомо мала: проверим рост\n",
    "for x in (1, 2, 3, 4):\n",
    "    q.push(x)\n",
    "print([q.pop() for _ in range(4)])   # ожидается [1, 2, 3, 4]\n",
    "check_queue(lambda: RingQueue(1))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "deque_md",
   "metadata": {},
   "source": [
    "## 3. Дек на кольцевом буфере\n",
    "\n",
    "Дек — очередь с двумя концами: `append`, `appendleft`, `pop`, `popleft`. На том же буфере достаточно двигать `head` в обе стороны и следить за `size`; при заполнении ёмкость удваивается, как у очереди.\n",
    "\n",
    "В стандартной библиотеке эталон — `collections.deque`: внутри блоки узлов, $O(1)$ на обоих концах. В контесте им пользоваться можно; в этом упражнении — нет, иначе упражнение бессмысленно.\n",
    "\n",
    "Минимум в скользящем окне (задача № 11, 239) на паре не разбираем: для него нужен **монотонный** дек, это отдельный приём.\n"
   ]
  },
  {
   "cell_type": "code",
   "id": "deque_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class Deque:\n",
    "    def __init__(self, capacity=4):\n",
    "        self.data = [None] * capacity\n",
    "        self.head = 0\n",
    "        self.size = 0\n",
    "\n",
    "    def append(self, x):\n",
    "        \"\"\"Положить x в хвост.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def appendleft(self, x):\n",
    "        \"\"\"Положить x в голову.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def pop(self):\n",
    "        \"\"\"Извлечь хвост; на пустом деке — IndexError.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def popleft(self):\n",
    "        \"\"\"Извлечь голову; на пустом деке — IndexError.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.size == 0\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "\n",
    "    def _grow(self):\n",
    "        \"\"\"Переложить элементы по порядку, начиная с головы, в массив вдвое большей ёмкости.\"\"\"\n",
    "        return None\n",
    "\n",
    "\n",
    "d = Deque()\n",
    "d.append(1)        # [1]\n",
    "d.appendleft(0)    # [0, 1]\n",
    "d.append(2)        # [0, 1, 2]\n",
    "print(d.popleft(), d.pop(), d.popleft())   # ожидается 0 2 1\n",
    "check_deque(Deque)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "brackets_md",
   "metadata": {},
   "source": [
    "## 4. Скобочные структуры\n",
    "\n",
    "Строка из символов `()[]{}`; прочие символы игнорируем. Нужно проверить, что последовательность правильная: каждая закрывающая соответствует **последней незакрытой** открывающей того же типа, и в конце незакрытых не остаётся.\n",
    "\n",
    "Одних счётчиков мало: `([)]` сходится по балансу, но порядок вложенности нарушен. Нужна память о последнем незакрытом — это стек.\n",
    "\n",
    "Время $\\Theta(n)$, память $O(n)$ в худшем случае: вся строка из открывающих.\n"
   ]
  },
  {
   "cell_type": "code",
   "id": "brackets_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "LEFT_BRACKETS = \"([{\"\n",
    "RIGHT_BRACKETS = \")]}\"\n",
    "\n",
    "\n",
    "def check_brackets(s):\n",
    "    \"\"\"True, если скобочная последовательность правильная; прочие символы игнорируем.\"\"\"\n",
    "    return True\n",
    "\n",
    "\n",
    "for s in [\"([{}])\", \"([)]\", \"())\", \"(\", \"\"]:\n",
    "    print(repr(s), \"->\", check_brackets(s))\n",
    "# ожидается True False False False True\n",
    "\n",
    "check_brackets_fn(check_brackets)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "rpn_md",
   "metadata": {},
   "source": [
    "## 5. Обратная польская запись\n",
    "\n",
    "Три формы одного выражения: инфиксная `3 + 4 * 2`, префиксная `+ 3 * 4 2`, постфиксная `3 4 2 * +`. В постфиксной нет скобок и приоритетов, поэтому она вычисляется одним проходом: число кладём в стек, оператор снимает **два верхних** и кладёт результат.\n",
    "\n",
    "Порядок операндов важен: первым снимается **правый**. Для `4 2 -` ответ `2`, для `2 4 -` ответ `-2`. Это самая частая ошибка при сборке кода.\n",
    "\n",
    "**Ловушка деления.** В задаче № 6 (150) деление должно **усекаться к нулю**: `-7 2 /` даёт `-3`. Оператор `//` в Python округляет вниз и даст `-4`. Берите `int(a / b)`.\n",
    "\n",
    "Переход от инфиксной записи к постфиксной (сортировочная станция Дейкстры) в эту пару не входит.\n"
   ]
  },
  {
   "cell_type": "code",
   "id": "rpn_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "OPS = {\n",
    "    \"+\": lambda a, b: a + b,\n",
    "    \"-\": lambda a, b: a - b,\n",
    "    \"*\": lambda a, b: a * b,\n",
    "    \"/\": lambda a, b: int(a / b),   # усечение к нулю, как в 150; // здесь неверно\n",
    "}\n",
    "\n",
    "\n",
    "def eval_rpn(tokens):\n",
    "    \"\"\"Значение выражения в обратной польской записи; tokens — список строк.\"\"\"\n",
    "    return 0\n",
    "\n",
    "\n",
    "print(eval_rpn(\"3 4 2 * +\".split()))   # ожидается 11\n",
    "print(eval_rpn(\"3 4 + 2 *\".split()))   # ожидается 14\n",
    "print(eval_rpn(\"-7 2 /\".split()))      # ожидается -3\n",
    "\n",
    "check_rpn_fn(eval_rpn)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "extra_md",
   "metadata": {},
   "source": [
    "## 6. Необязательный хвост: связные структуры\n",
    "\n",
    "Раздел 7 лекции, помеченный звёздочкой: на лекции он не разбирался, в обязательную часть и в оценивание не входит. Возвращайтесь сюда, только если разделы 1–5 закрыты.\n",
    "\n",
    "Идея: у массива доступ по индексу $O(1)$, но вставка и удаление в начале стоят $\\Theta(n)$ и могут требовать перевыделения. Альтернатива — хранить в элементе **ссылку на следующий**. Односвязный список оканчивается `None`: вставка в голову — $O(1)$, доступ к $k$-му элементу — $O(k)$.\n"
   ]
  },
  {
   "cell_type": "code",
   "id": "node_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, value, next=None):\n",
    "        self.value = value\n",
    "        self.next = next\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"Node({self.value!r})\"\n",
    "\n",
    "\n",
    "class LinkedStack:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def push(self, value):\n",
    "        \"\"\"Новый узел становится головой.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def pop(self):\n",
    "        \"\"\"Снять голову; на пустом стеке — IndexError.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.head is None\n",
    "\n",
    "\n",
    "ls = LinkedStack()\n",
    "for x in (1, 2, 3):\n",
    "    ls.push(x)\n",
    "print([ls.pop() for _ in range(3)])   # ожидается [3, 2, 1]\n",
    "\n",
    "# Загадка: что напечатает a = [1]; a.append(a) и почему?\n",
    "# Проверьте в отдельной ячейке и объясните, при чём тут repr.\n"
   ]
  },
  {
   "cell_type": "code",
   "id": "linkqueue_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class LinkedQueue:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "\n",
    "    def push(self, value):\n",
    "        \"\"\"Добавить в хвост. Отдельно разберите случай пустой очереди.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def pop(self):\n",
    "        \"\"\"Извлечь голову; на пустой — IndexError. Не забудьте сбросить tail.\"\"\"\n",
    "        return None\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.head is None\n",
    "\n",
    "\n",
    "lq = LinkedQueue()\n",
    "for x in range(1, 5):\n",
    "    lq.push(x)\n",
    "print([lq.pop() for _ in range(4)])       # ожидается [1, 2, 3, 4]\n",
    "print(\"хвост сброшен:\", lq.tail is None)  # ожидается True\n",
    "\n",
    "# Проверьте ещё два случая: pop из пустой очереди и очередь из одного элемента.\n",
    "# Что будет с tail, если его не сбросить при опустошении?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "contest",
   "metadata": {},
   "source": [
    "## Контест\n",
    "\n",
    "Задачи сдавайте в контест недели 7 на [algo.ai.msu.ru](https://algo.ai.msu.ru). Номера LeetCode помогают найти условие.\n",
    "\n",
    "**Для зачёта семинара обязательны № 5 (622. Design Circular Queue) и № 6 (150. Evaluate Reverse Polish Notation).** Разминка и задачи по желанию их не заменяют.\n",
    "\n",
    "| № | Задача | Статус на семинаре | Что из ноутбука |\n",
    "| --- | --- | --- | --- |\n",
    "| 1 | 20. Valid Parentheses | Разминка | `check_brackets`; проверьте `())` и `(` |\n",
    "| 2 | 232. Implement Queue using Stacks | Разминка | интерфейс очереди: один стек на вход, второй на выход |\n",
    "| 3 | 1047. Remove All Adjacent Duplicates In String | Разминка | стек как «отложенное решение»: сравниваем верх с текущим символом |\n",
    "| 4 | 933. Number of Recent Calls | Разминка | очередь как окно: `popleft`, пока голова старше `t - 3000` |\n",
    "| 5 | 622. Design Circular Queue | **Обязательная** | `RingQueue`: `head`, `size`, `%`; здесь нет роста, зато нужны `Front`, `Rear`, `isFull` |\n",
    "| 6 | 150. Evaluate Reverse Polish Notation | **Обязательная** | `eval_rpn`; порядок `a`, `b` и усечение деления к нулю |\n",
    "| 7 | 641. Design Circular Deque | По желанию | `Deque`; парная к № 5, тот же буфер с двух концов |\n",
    "| 8 | 155. Min Stack | По желанию | стек с инвариантом: второй стек хранит минимумы |\n",
    "| 9 | 71. Simplify Path | По желанию | стек для разбора пути: `..` снимает верх |\n",
    "| 10 | 946. Validate Stack Sequences | По желанию | симуляция: пушим `pushed`, снимаем, когда верх совпал с `popped` |\n",
    "| 11 | 239. Sliding Window Maximum ★ | По желанию | монотонный дек; приём **вне лекции**, только после обязательных |\n",
    "\n",
    "**Порядок работы.** Разминку № 1–4 закрывайте быстро, они на один приём каждая. Дальше № 5: в ней ровно та структура, которую вы писали в разделе 2, только без роста. Потом № 6. Остальное — по желанию и дома.\n",
    "\n",
    "Типичный **WA**: в ОПЗ берут операнды в обратном порядке; делят через `//` и получают `-4` вместо `-3`; в скобках проверяют только баланс; в № 5 путают `Front` и `Rear` и забывают, что при переполнении `enQueue` возвращает `False`, а не растит массив.\n",
    "\n",
    "Типичный **TLE**: очередь на `list.pop(0)` в № 4 и № 10; поиск минимума в `Min Stack` линейным проходом вместо второго стека.\n",
    "\n",
    "**Про свой код и стандартную библиотеку.** В контесте `collections.deque` разрешён. В упражнениях ноутбука — нет: `RingQueue` и `Deque` пишем сами. Проверки сравнивают результат с моделью, а не смотрят, чем вы пользовались; на паре мы спрашиваем структуру у доски.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cheatsheet",
   "metadata": {},
   "source": [
    "## Шпаргалка\n",
    "\n",
    "Стек (LIFO):\n",
    "\n",
    "- внутри список, работаем с **концом**: `append` / `pop()` — амортизированное $O(1)$;\n",
    "- `pop(0)` — $\\Theta(n)$: все оставшиеся элементы сдвигаются.\n",
    "\n",
    "Очередь (FIFO):\n",
    "\n",
    "- кольцевой буфер: `head`, `size`, хвост `(head + size) % len(data)`;\n",
    "- рост удвоением — амортизированное $O(1)$; извлечение ничего не сдвигает;\n",
    "- в 622 роста нет: при `size == len(data)` возвращаем `False`.\n",
    "\n",
    "Дек:\n",
    "\n",
    "- тот же буфер, `head` двигается в обе стороны; эталон — `collections.deque`, $O(1)$ на концах.\n",
    "\n",
    "Скобки:\n",
    "\n",
    "- стек последних незакрытых; при закрывающей стек не пуст и верх совпал по типу;\n",
    "- в конце стек пуст. `([)]` — ловушка «одних счётчиков мало».\n",
    "\n",
    "ОПЗ:\n",
    "\n",
    "- число — в стек; оператор снимает **правый**, потом **левый**: `b = pop(); a = pop()`;\n",
    "- деление в 150 усекается к нулю: `int(a / b)`, а не `a // b`.\n",
    "\n",
    "Классы:\n",
    "\n",
    "- `self` — первый параметр метода; `__init__` вызывается при `Stack()`;\n",
    "- `__repr__` управляет печатью, `__len__` — функцией `len`;\n",
    "- инкапсуляции в Python нет: `_data` — договорённость, а не запрет.\n",
    "\n",
    "Связные структуры (необязательно): `Node(value, next)`, вставка в голову $O(1)$; очередь на узлах требует `tail`.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "submit",
   "metadata": {},
   "source": [
    "## Сдача\n",
    "\n",
    "- **Этот** `.ipynb` семинаристу отправлять не нужно.\n",
    "- Для зачёта выполните **№ 5 — 622. Design Circular Queue** и **№ 6 — 150. Evaluate Reverse Polish Notation** в контесте на [algo.ai.msu.ru](https://algo.ai.msu.ru).\n",
    "- Разминка № 1–4 и задачи № 7–11 выполняются по желанию, для зачёта не требуются.\n",
    "- Если обязательные задачи не закончены на паре, дорешайте их в том же контесте после занятия.\n",
    "- Отдельного ДЗ на этой неделе нет.\n",
    "- Стек, очередь и дек входят в программу коллоквиума 2 и контрольной 2: спросят интерфейс, цену операций и кольцевой буфер.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}