Лекция. Стек, очередь, дек: классы и применения

Лекция 7. Стек, очередь, дек: классы, применения и связные структуры

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

Опираемся на лекцию 4 (стек вызовов, рекурсия) и лекцию 5 (класс Item, сравнение по ключу, устойчивость). В программу коллоквиума 1 этот материал не входит. Практика — семинар 7 на этой же неделе.

План

Разминка: пятиминутка по разбору контрольной 1 — пять вопросов на листочках. 0. Что такое ADT: интерфейс и реализация.

Стек на списке Python: append и pop(), амортизация.
Классы: минимум синтаксиса и class Stack.
Очередь: кольцевой буфер и collections.deque.
Дек: интерфейс с двух концов.
Скобочные структуры: где стек действительно нужен.
Три нотации выражения и вычисление обратной польской записи.
* Связные структуры на ссылках Python: пары [значение, следующий] и class Node — на лекции не разбирались, оставлены для самостоятельного чтения.

Сортировочная станция Дейкстры в эту пару не входит — она вынесена за пределы занятия.

Разминка: пятиминутка по разбору контрольной 1

Пять вопросов на листочках, по минуте на каждый: 40 секунд на ответ, 20 на переход. Без конспекта. Проверяем, читали ли разбор контрольной 1.

Задача 1. УК победила на этаже, где за неё 100 голосов. Сколько голосов делегатов она принесёт на собрании ЖК?
Задача 2. В крестьянском умножении для $a = 13$: сколько строк отмечено?
Задача 5. Почему обычный бинарный поиск прямо по входному массиву неверен?
Задача 6. Можно ли перед поиском троек с нулевой суммой удалить из массива все повторяющиеся числа?
Задача 7. Что минимизирует суммарную усталость: среднее, обычная медиана или взвешенная медиана?

Ответы

Задача 1. Один: голос этажа считается один раз, а не по числу жильцов, проголосовавших за победившую УК.
Задача 2. Три: $13 = 1101_2$. Число отмеченных строк — число единиц в двоичной записи первого множителя, от второго оно не зависит.
Задача 5. Массив не отсортирован. Сначала ищут точку сдвига — индекс минимума, — затем работают с виртуальными индексами $(j+\text{pivot}) \bmod n$.
Задача 6. Нельзя: пропадут решения вида $(-1, -1, 2)$.
Задача 7. Взвешенная медиана; среднее сумму модулей не минимизирует.

0. Что такое ADT

Абстрактный тип данных — это интерфейс и контракт, без представления.

Стек: последним пришёл — первым ушёл (LIFO). Операции push, pop, проверка пустоты.
Очередь: первым пришёл — первым ушёл (FIFO). Добавляем в хвост, извлекаем из головы.
Дек: добавление и извлечение с обоих концов.

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

В лекции 4 уже был стек — стек вызовов: интерпретатор хранит там параметры и место продолжения. Механизм тот же, но стек вызовов ведёт интерпретатор, а стек как ADT — обычная структура, которой управляет программа.

1. Стек на списке Python

Список уже умеет работать как стек: append кладёт в конец, pop() снимает с конца.

In [4]:

stack = []
stack.append(1)                 # push
stack.append(2)
print("pop:", stack.pop())      # 2 — с конца
print("пусто:", not stack)      # False
print("размер:", len(stack))    # 1

pop: 2
пусто: False
размер: 1

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

А вот pop(0) — извлечение из начала — стоит $\Theta(n)$: все оставшиеся элементы сдвигаются. Именно из этой цены вырастет очередь.

In [5]:

a = [1, 2, 3, 4, 5]
print("pop(0):", a.pop(0))      # 1
print("осталось:", a)           # [2, 3, 4, 5] — все сдвинулись

pop(0): 1
осталось: [2, 3, 4, 5]

2. Классы: минимум синтаксиса и `class Stack`

Список-стек не защищает инвариант: данные и операции живут порознь. Класс собирает их под одним именем — это та же «капсула» из лекции 1, только теперь она хранит данные.

Нужный минимум: class, self, __init__, атрибуты, методы и __repr__.

In [6]:

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

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

    def pop(self):
        if not self.data:  # the same as len(self.data) == 0
            raise IndexError("pop from empty stack")
        return self.data.pop()

    def is_empty(self):
        return not self.data

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

    def __repr__(self):
        return f"Stack({self.data!r})"

In [8]:

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

Stack([1, 2]) 2
2
Stack([1]) 1

Stack() вызывает __init__; каждый метод получает объект первым параметром self; __repr__ управляет печатью — ровно как Item на лекции 5; __len__ делает осмысленным len(s).

Честно про инкапсуляцию: в Python её нет, есть договорённость. s.data доступен снаружи, а имя _data — знак «не трогать».

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

3. Очередь: кольцевой буфер и `collections.deque`

Наивная очередь на списке — append в хвост и pop(0) из головы — стоит $\Theta(n)$ на извлечение. Нужен второй конец без сдвига: кольцевой буфер.

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

In [9]:

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

    def push(self, x):
        if self.size == len(self.data):
            self._grow()
        self.data[(self.head + self.size) % len(self.data)] = x
        self.size += 1

    def pop(self):
        if self.size == 0:
            raise IndexError("pop from empty queue")
        x = self.data[self.head]
        self.head = (self.head + 1) % len(self.data)
        self.size -= 1
        return x

    def _grow(self):
        old = [self.data[(self.head + i) % len(self.data)] for i in range(self.size)]
        self.data = old + [None] * len(old)
        self.head = 0

In [10]:

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

[1, 2, 3, 4]
пусто: True

В стандартной библиотеке есть готовая двусторонняя очередь collections.deque: внутри блоки узлов, $O(1)$ на обоих концах. Полную реализацию deque писать не нужно — достаточно понимать, чем она лучше list.pop(0).

In [11]:

from collections import deque

d = deque([1, 2, 3, 4])
print("popleft:", d.popleft())   # 1 — O(1), без сдвига
d.appendleft(0)
print("deque:", d)               # deque([0, 2, 3, 4])

popleft: 1
deque: deque([0, 2, 3, 4])

4. Дек

Дек — очередь с двумя концами: push_front, push_back, pop_front, pop_back. На кольцевом буфере достаточно двигать head в обе стороны, а на практике берут collections.deque.

In [12]:

d = deque()
d.append(1)          # в хвост
d.appendleft(0)      # в голову
print("голова:", d.popleft())   # 0
print("хвост:", d.pop())        # 1
print("пусто:", not d)          # True

голова: 0
хвост: 1
пусто: True

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

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

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

In [13]:

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

def check_brackets(s: str):
    stack = []
    for ch in s:
        if ch in LEFT_BRACKETS:
            stack.append(ch)
        elif ch in RIGHT_BRACKETS:
            pair = LEFT_BRACKETS[RIGHT_BRACKETS.find(ch)]
            if not stack: # len(stack) == 0, открытых скобок больше нет, когда нашли закрывающую
                return False
            else:  # октрытые скобки ещё есть
                if stack.pop() != pair:
                    return False
    return not stack # len(stack) == 0, будет хорошо, если открытых скобок не осталось

for s in ["([{}])", "([)]", "())", "(", ""]:
    print(repr(s), "->", check_brackets(s))

'([{}])' -> True
'([)]' -> False
'())' -> False
'(' -> False
'' -> True

Разбор: ([{}]) — правильно; ([)] — типы перепутаны; ()) — лишняя закрывающая; ( — осталась незакрытая; пустая строка — правильно.

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

6. Три нотации и обратная польская запись

Одно выражение можно записать тремя способами:

инфиксная — оператор между операндами: 3 + 4 * 2;
префиксная (польская) — оператор до операндов: + 3 * 4 2;
постфиксная (обратная польская) — оператор после операндов: 3 4 2 * +.

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

In [14]:

import operator

OPS = {"+": operator.add, "-": operator.sub,
       "*": operator.mul, "/": operator.floordiv}

def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in OPS:
            b = stack.pop()
            a = stack.pop()
            result = OPS[t](a, b)   # именно a, b, иначе минус и деление врут
            stack.append(result)
        else:
            stack.append(int(t))
    return stack[0]

print(eval_rpn("3 4 2 * +".split()))   # 11
print(eval_rpn("3 4 + 2 *".split()))   # 14

11
14

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

7. * Связные структуры на ссылках Python

Этот раздел на лекции не разбирался. Звёздочка означает, что материал предлагается для самостоятельного чтения; на семинаре к нему можно вернуться необязательным хвостом, если останется время.

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

Начнём с того, что ссылка может вести на сам объект:

In [ ]:

a = [1]
a.append(a)
print(a)          # [1, [...]] — repr распознаёт цикл

А теперь без цикла: односвязный список из пар [значение, следующий], оканчивающийся None. Каждая новая пара становится головой и ссылается на прежнюю.

In [ ]:

a = [1, None]
a = [2, a]
a = [3, a]
a = [4, a]

p = a
while p is not None:
    print(p[0])
    p = p[1]

a держит голову; обход идёт по ссылкам, а не по индексам; печатается 4 3 2 1; для None используем is, а не ==. Вставка в голову — одна новая пара, $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})"

Стек на узлах устроен симметрично: push кладёт новый узел в голову, pop снимает голову, $O(1)$ в худшем случае и без перевыделения. Очередь нуждается ещё в tail, иначе добавление в хвост станет $O(n)$.

In [ ]:

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

    def push(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def pop(self):
        if self.head is None:
            raise IndexError("pop from empty queue")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        return value

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)

Сравнение двух представлений

	Динамический массив (`list`)	Связный список на узлах
Доступ по индексу	$O(1)$	$O(k)$
Добавление в начало	$\Theta(n)$	$O(1)$
Добавление в конец	амортизированное $O(1)$	$O(1)$ при наличии `tail`
Память	компактно, с запасом ёмкости	узел + ссылка на каждый элемент

В Python list и deque закрывают почти все задачи; своя реализация нужна, чтобы понимать цену операции и читать чужой код.

8. К семинару 7

Собираем руками обязательную часть: Stack и Queue классами, кольцевой буфер, скобки нескольких типов, вычисление ОПЗ, дек.

Необязательный хвост. Связные структуры на ссылках из раздела 7 (звёздочка): загадка с a.append(a), обход пар [значение, следующий], class Node и очередь на узлах. В обязательную часть и в оценивание не входит.

Лекция. Стек, очередь, дек: классы и применения

Лекция 7. Стек, очередь, дек: классы, применения и связные структуры

План

Разминка: пятиминутка по разбору контрольной 1

0. Что такое ADT

1. Стек на списке Python

2. Классы: минимум синтаксиса и class Stack

3. Очередь: кольцевой буфер и collections.deque

4. Дек

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

6. Три нотации и обратная польская запись

7. * Связные структуры на ссылках Python

Сравнение двух представлений

8. К семинару 7

2. Классы: минимум синтаксиса и `class Stack`

3. Очередь: кольцевой буфер и `collections.deque`