{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "lec07-000",
   "metadata": {},
   "source": [
    "# Лекция 7. Стек, очередь, дек: классы, применения и связные структуры\n",
    "\n",
    "Коллоквиум 1 позади. Сегодня строим то, чем пользуются все последующие темы, — **абстрактные типы данных**. Стек и очередь — это интерфейсы, у которых может быть разная реализация, и от реализации зависят время, память и гарантии.\n",
    "\n",
    "Опираемся на лекцию 4 (стек вызовов, рекурсия) и лекцию 5 (класс `Item`, сравнение по ключу, устойчивость). В программу коллоквиума 1 этот материал не входит. Практика — семинар 7 на этой же неделе.\n",
    "\n",
    "## План\n",
    "\n",
    "**Разминка: пятиминутка по разбору контрольной 1** — пять вопросов на листочках.\n",
    "0. Что такое ADT: интерфейс и реализация.\n",
    "1. Стек на списке Python: `append` и `pop()`, амортизация.\n",
    "2. Классы: минимум синтаксиса и `class Stack`.\n",
    "3. Очередь: кольцевой буфер и `collections.deque`.\n",
    "4. Дек: интерфейс с двух концов.\n",
    "5. Скобочные структуры: где стек действительно нужен.\n",
    "6. Три нотации выражения и вычисление обратной польской записи.\n",
    "7. \\* Связные структуры на ссылках Python: пары `[значение, следующий]` и `class Node` — на лекции не разбирались, оставлены для самостоятельного чтения.\n",
    "\n",
    "Сортировочная станция Дейкстры в эту пару не входит — она вынесена за пределы занятия.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-quiz",
   "metadata": {},
   "source": [
    "## Разминка: пятиминутка по разбору контрольной 1\n",
    "\n",
    "Пять вопросов на листочках, по минуте на каждый: 40 секунд на ответ, 20 на переход. Без конспекта. Проверяем, читали ли [разбор контрольной 1](https://learn.ai.msu.ru/algo/1/06/test-solutions/).\n",
    "\n",
    "1. **Задача 1.** УК победила на этаже, где за неё 100 голосов. Сколько голосов делегатов она принесёт на собрании ЖК?\n",
    "2. **Задача 2.** В крестьянском умножении для $a = 13$: сколько строк отмечено?\n",
    "3. **Задача 5.** Почему обычный бинарный поиск прямо по входному массиву неверен?\n",
    "4. **Задача 6.** Можно ли перед поиском троек с нулевой суммой удалить из массива все повторяющиеся числа?\n",
    "5. **Задача 7.** Что минимизирует суммарную усталость: среднее, обычная медиана или взвешенная медиана?\n",
    "\n",
    "<details>\n",
    "<summary>Ответы</summary>\n",
    "\n",
    "1. **Задача 1.** Один: голос этажа считается один раз, а не по числу жильцов, проголосовавших за победившую УК.\n",
    "2. **Задача 2.** Три: $13 = 1101_2$. Число отмеченных строк — число единиц в двоичной записи первого множителя, от второго оно не зависит.\n",
    "3. **Задача 5.** Массив не отсортирован. Сначала ищут точку сдвига — индекс минимума, — затем работают с виртуальными индексами $(j+\\text{pivot}) \\bmod n$.\n",
    "4. **Задача 6.** Нельзя: пропадут решения вида $(-1, -1, 2)$.\n",
    "5. **Задача 7.** Взвешенная медиана; среднее сумму модулей не минимизирует.\n",
    "\n",
    "</details>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-001",
   "metadata": {},
   "source": [
    "## 0. Что такое ADT\n",
    "\n",
    "**Абстрактный тип данных** — это интерфейс и контракт, без представления.\n",
    "\n",
    "- Стек: последним пришёл — первым ушёл (LIFO). Операции `push`, `pop`, проверка пустоты.\n",
    "- Очередь: первым пришёл — первым ушёл (FIFO). Добавляем в хвост, извлекаем из головы.\n",
    "- Дек: добавление и извлечение с обоих концов.\n",
    "\n",
    "Один и тот же интерфейс допускает разные реализации. От выбора реализации зависят время операции, память и гарантии — худший случай против амортизированного.\n",
    "\n",
    "В лекции 4 уже был стек — **стек вызовов**: интерпретатор хранит там параметры и место продолжения. Механизм тот же, но стек вызовов ведёт интерпретатор, а стек как ADT — обычная структура, которой управляет программа.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-002",
   "metadata": {},
   "source": [
    "## 1. Стек на списке Python\n",
    "\n",
    "Список уже умеет работать как стек: `append` кладёт в конец, `pop()` снимает с конца.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "lec07-003",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pop: 2\n",
      "пусто: False\n",
      "размер: 1\n"
     ]
    }
   ],
   "source": [
    "stack = []\n",
    "stack.append(1)                 # push\n",
    "stack.append(2)\n",
    "print(\"pop:\", stack.pop())      # 2 — с конца\n",
    "print(\"пусто:\", not stack)      # False\n",
    "print(\"размер:\", len(stack))    # 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-004",
   "metadata": {},
   "source": [
    "`append` и `pop()` работают с конца и дают амортизированное $O(1)$. Дополнительная память — $\\Theta(n)$ под сами данные.\n",
    "\n",
    "А вот `pop(0)` — извлечение из начала — стоит $\\Theta(n)$: все оставшиеся элементы сдвигаются. Именно из этой цены вырастет очередь.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "lec07-005",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pop(0): 1\n",
      "осталось: [2, 3, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "a = [1, 2, 3, 4, 5]\n",
    "print(\"pop(0):\", a.pop(0))      # 1\n",
    "print(\"осталось:\", a)           # [2, 3, 4, 5] — все сдвинулись\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-006",
   "metadata": {},
   "source": [
    "## 2. Классы: минимум синтаксиса и `class Stack`\n",
    "\n",
    "Список-стек не защищает инвариант: данные и операции живут порознь. **Класс** собирает их под одним именем — это та же «капсула» из лекции 1, только теперь она хранит данные.\n",
    "\n",
    "Нужный минимум: `class`, `self`, `__init__`, атрибуты, методы и `__repr__`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "lec07-007",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "\n",
    "    def push(self, x):\n",
    "        self.data.append(x)\n",
    "\n",
    "    def pop(self):\n",
    "        if not self.data:  # the same as len(self.data) == 0\n",
    "            raise IndexError(\"pop from empty stack\")\n",
    "        return self.data.pop()\n",
    "\n",
    "    def is_empty(self):\n",
    "        return not self.data\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self.data)\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"Stack({self.data!r})\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "lec07-008",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stack([1, 2]) 2\n",
      "2\n",
      "Stack([1]) 1\n"
     ]
    }
   ],
   "source": [
    "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"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-009",
   "metadata": {},
   "source": [
    "`Stack()` вызывает `__init__`; каждый метод получает объект первым параметром `self`; `__repr__` управляет печатью — ровно как `Item` на лекции 5; `__len__` делает осмысленным `len(s)`.\n",
    "\n",
    "Честно про инкапсуляцию: в Python её нет, есть договорённость. `s.data` доступен снаружи, а имя `_data` — знак «не трогать».\n",
    "\n",
    "**Ловушка.** В `print(s, s.pop())` объект печатается уже после извлечения: все аргументы вычисляются до вызова `print`. Такие однострочники со скрытой мутацией дают «странные» распечатки.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-010",
   "metadata": {},
   "source": [
    "## 3. Очередь: кольцевой буфер и `collections.deque`\n",
    "\n",
    "Наивная очередь на списке — `append` в хвост и `pop(0)` из головы — стоит $\\Theta(n)$ на извлечение. Нужен второй конец без сдвига: **кольцевой буфер**.\n",
    "\n",
    "Массив фиксированной ёмкости плюс `head` и `size`; позиция хвоста — `(head + size) % len(data)`. Конец массива заворачивается в начало, сдвигать элементы не нужно. При заполнении ёмкость удваивается — это даёт амортизированное $O(1)$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "lec07-011",
   "metadata": {},
   "outputs": [],
   "source": [
    "class RingQueue:\n",
    "    def __init__(self, capacity):\n",
    "        self.data = [None] * capacity\n",
    "        self.head = 0\n",
    "        self.size = 0\n",
    "\n",
    "    def push(self, x):\n",
    "        if self.size == len(self.data):\n",
    "            self._grow()\n",
    "        self.data[(self.head + self.size) % len(self.data)] = x\n",
    "        self.size += 1\n",
    "\n",
    "    def pop(self):\n",
    "        if self.size == 0:\n",
    "            raise IndexError(\"pop from empty queue\")\n",
    "        x = self.data[self.head]\n",
    "        self.head = (self.head + 1) % len(self.data)\n",
    "        self.size -= 1\n",
    "        return x\n",
    "\n",
    "    def _grow(self):\n",
    "        old = [self.data[(self.head + i) % len(self.data)] for i in range(self.size)]\n",
    "        self.data = old + [None] * len(old)\n",
    "        self.head = 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "lec07-012",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4]\n",
      "пусто: True\n"
     ]
    }
   ],
   "source": [
    "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",
    "print(\"пусто:\", q.size == 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-013",
   "metadata": {},
   "source": [
    "В стандартной библиотеке есть готовая двусторонняя очередь `collections.deque`: внутри блоки узлов, $O(1)$ на обоих концах. Полную реализацию `deque` писать не нужно — достаточно понимать, чем она лучше `list.pop(0)`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "lec07-014",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "popleft: 1\n",
      "deque: deque([0, 2, 3, 4])\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "d = deque([1, 2, 3, 4])\n",
    "print(\"popleft:\", d.popleft())   # 1 — O(1), без сдвига\n",
    "d.appendleft(0)\n",
    "print(\"deque:\", d)               # deque([0, 2, 3, 4])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-015",
   "metadata": {},
   "source": [
    "## 4. Дек\n",
    "\n",
    "**Дек** — очередь с двумя концами: `push_front`, `push_back`, `pop_front`, `pop_back`. На кольцевом буфере достаточно двигать `head` в обе стороны, а на практике берут `collections.deque`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "lec07-016",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "голова: 0\n",
      "хвост: 1\n",
      "пусто: True\n"
     ]
    }
   ],
   "source": [
    "d = deque()\n",
    "d.append(1)          # в хвост\n",
    "d.appendleft(0)      # в голову\n",
    "print(\"голова:\", d.popleft())   # 0\n",
    "print(\"хвост:\", d.pop())        # 1\n",
    "print(\"пусто:\", not d)          # True"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-017",
   "metadata": {},
   "source": [
    "## 5. Скобочные структуры\n",
    "\n",
    "Строка из символов `()[]{}`. Нужно проверить, что последовательность правильная: каждая закрывающая соответствует **последней незакрытой** открывающей того же типа, и в конце незакрытых не остаётся.\n",
    "\n",
    "Одних счётчиков мало: `([)]` сходится по балансу, но порядок вложенности нарушен. Нужна память о последнем незакрытом — это стек.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "lec07-018",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "'([{}])' -> True\n",
      "'([)]' -> False\n",
      "'())' -> False\n",
      "'(' -> False\n",
      "'' -> True\n"
     ]
    }
   ],
   "source": [
    "LEFT_BRACKETS = \"([{\"\n",
    "RIGHT_BRACKETS = \")]}\"\n",
    "\n",
    "def check_brackets(s: str):\n",
    "    stack = []\n",
    "    for ch in s:\n",
    "        if ch in LEFT_BRACKETS:\n",
    "            stack.append(ch)\n",
    "        elif ch in RIGHT_BRACKETS:\n",
    "            pair = LEFT_BRACKETS[RIGHT_BRACKETS.find(ch)]\n",
    "            if not stack: # len(stack) == 0, открытых скобок больше нет, когда нашли закрывающую\n",
    "                return False\n",
    "            else:  # октрытые скобки ещё есть\n",
    "                if stack.pop() != pair:\n",
    "                    return False\n",
    "    return not stack # len(stack) == 0, будет хорошо, если открытых скобок не осталось\n",
    "\n",
    "for s in [\"([{}])\", \"([)]\", \"())\", \"(\", \"\"]:\n",
    "    print(repr(s), \"->\", check_brackets(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-019",
   "metadata": {},
   "source": [
    "Разбор: `([{}])` — правильно; `([)]` — типы перепутаны; `())` — лишняя закрывающая; `(` — осталась незакрытая; пустая строка — правильно.\n",
    "\n",
    "Время работы $\\Theta(n)$, память $O(n)$ в худшем случае — вся строка из открывающих.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-020",
   "metadata": {},
   "source": [
    "## 6. Три нотации и обратная польская запись\n",
    "\n",
    "Одно выражение можно записать тремя способами:\n",
    "\n",
    "- **инфиксная** — оператор между операндами: `3 + 4 * 2`;\n",
    "- **префиксная** (польская) — оператор до операндов: `+ 3 * 4 2`;\n",
    "- **постфиксная** (обратная польская) — оператор после операндов: `3 4 2 * +`.\n",
    "\n",
    "В постфиксной записи нет скобок и приоритетов, поэтому она вычисляется одним проходом стека: число кладём в стек, оператор снимает два верхних и кладёт результат. Порядок операндов важен: первым снимается правый.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "lec07-021",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11\n",
      "14\n"
     ]
    }
   ],
   "source": [
    "import operator\n",
    "\n",
    "OPS = {\"+\": operator.add, \"-\": operator.sub,\n",
    "       \"*\": operator.mul, \"/\": operator.floordiv}\n",
    "\n",
    "def eval_rpn(tokens):\n",
    "    stack = []\n",
    "    for t in tokens:\n",
    "        if t in OPS:\n",
    "            b = stack.pop()\n",
    "            a = stack.pop()\n",
    "            result = OPS[t](a, b)   # именно a, b, иначе минус и деление врут\n",
    "            stack.append(result)\n",
    "        else:\n",
    "            stack.append(int(t))\n",
    "    return stack[0]\n",
    "\n",
    "print(eval_rpn(\"3 4 2 * +\".split()))   # 11\n",
    "print(eval_rpn(\"3 4 + 2 *\".split()))   # 14\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-022",
   "metadata": {},
   "source": [
    "Переход от инфиксной записи к постфиксной (сортировочная станция Дейкстры) в эту пару не входит.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-023",
   "metadata": {},
   "source": [
    "## 7. * Связные структуры на ссылках Python\n",
    "\n",
    "**Этот раздел на лекции не разбирался.** Звёздочка означает, что материал предлагается для самостоятельного чтения; на семинаре к нему можно вернуться необязательным хвостом, если останется время.\n",
    "\n",
    "У массива доступ по индексу $O(1)$, но вставка и удаление в начале стоят $\\Theta(n)$ и могут требовать перевыделения. Альтернатива — хранить в элементе **ссылку на следующий**.\n",
    "\n",
    "Начнём с того, что ссылка может вести на сам объект:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "lec07-024",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1]\n",
    "a.append(a)\n",
    "print(a)          # [1, [...]] — repr распознаёт цикл\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-025",
   "metadata": {},
   "source": [
    "А теперь без цикла: односвязный список из пар `[значение, следующий]`, оканчивающийся `None`. Каждая новая пара становится головой и ссылается на прежнюю.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "lec07-026",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1, None]\n",
    "a = [2, a]\n",
    "a = [3, a]\n",
    "a = [4, a]\n",
    "\n",
    "p = a\n",
    "while p is not None:\n",
    "    print(p[0])\n",
    "    p = p[1]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-027",
   "metadata": {},
   "source": [
    "`a` держит голову; обход идёт по ссылкам, а не по индексам; печатается `4 3 2 1`; для `None` используем `is`, а не `==`. Вставка в голову — одна новая пара, $O(1)$; доступ к $k$-му элементу — $O(k)$.\n",
    "\n",
    "Оформим ту же пару классом:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "lec07-028",
   "metadata": {},
   "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"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-029",
   "metadata": {},
   "source": [
    "Стек на узлах устроен симметрично: `push` кладёт новый узел в голову, `pop` снимает голову, $O(1)$ в худшем случае и без перевыделения. Очередь нуждается ещё в `tail`, иначе добавление в хвост станет $O(n)$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "lec07-030",
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedQueue:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "\n",
    "    def push(self, value):\n",
    "        node = Node(value)\n",
    "        if self.tail is None:\n",
    "            self.head = self.tail = node\n",
    "        else:\n",
    "            self.tail.next = node\n",
    "            self.tail = node\n",
    "\n",
    "    def pop(self):\n",
    "        if self.head is None:\n",
    "            raise IndexError(\"pop from empty queue\")\n",
    "        value = self.head.value\n",
    "        self.head = self.head.next\n",
    "        if self.head is None:\n",
    "            self.tail = None\n",
    "        return value\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)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-030b",
   "metadata": {},
   "source": [
    "### Сравнение двух представлений\n",
    "\n",
    "| | Динамический массив (`list`) | Связный список на узлах |\n",
    "| --- | --- | --- |\n",
    "| Доступ по индексу | $O(1)$ | $O(k)$ |\n",
    "| Добавление в начало | $\\Theta(n)$ | $O(1)$ |\n",
    "| Добавление в конец | амортизированное $O(1)$ | $O(1)$ при наличии `tail` |\n",
    "| Память | компактно, с запасом ёмкости | узел + ссылка на каждый элемент |\n",
    "\n",
    "В Python `list` и `deque` закрывают почти все задачи; своя реализация нужна, чтобы понимать цену операции и читать чужой код.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec07-031",
   "metadata": {},
   "source": [
    "## 8. К семинару 7\n",
    "\n",
    "Собираем руками обязательную часть: `Stack` и `Queue` классами, кольцевой буфер, скобки нескольких типов, вычисление ОПЗ, дек.\n",
    "\n",
    "**Необязательный хвост.** Связные структуры на ссылках из раздела 7 (звёздочка): загадка с `a.append(a)`, обход пар `[значение, следующий]`, `class Node` и очередь на узлах. В обязательную часть и в оценивание не входит.\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
}