#import "/utils/math.typ": *

= Введение

<NAME>

$ "Накоп" = 0.25 dot "Кол" + 0.25 dot "КР" + 0.4 dot "ДЗ" + 0.1 dot "Сем" $

$
    "Итог" = cases(
        round("Накоп")\, &" if НЕ идти на экзамен",
        0.5 dot "Накоп" + 0.5 dot "Экз"\, &" if идти на экзамен"
    )
$

Контесты на 1--2 недели

= Структуры данных

#def[
    #defitem[Абстрактный тип данных] --- определяем, какие операции делает структура, но не
    определяем конкретную реализацию
]

Контейнеры:
- Последовательные (напр, вектор)
- Ассоциативные (напр, map)
- Адаптеры (не имеют итераторов)

= Линейные структуры данных

== Стек и очередь

#figure(table(
    columns: 2,
    table.header("Стек", "Очередь"),
    "LIFO", "FIFO",
))

Реализации:
- Массив
- Список
- Deque
- (для очереди) на двух стеках

== Список

Односвязный:
- `begin()` указывает на первый эл-т
- каждый элемент указывает на следующий
- `end()` указывает в пустоту

Двусвязный:
- каждый элемент указывает ещё и на прошлый эл-т

Список может быть зациклен

Зацикленный список может иметь незацикленное начало

== Стек с минимумом

Помимо основного стека поддерживаем стек минимумов (на префиксе)

#figure(table(
    columns: 2,
    table.header(`st`, `min_st`),
    $2$, $2$,
    $5$, $3$,
    $3$, $3$,
    $6$, $4$,
    $4$, $4$,
))

Минимум в стеке -- `min_st.top()`

== Очередь через два стека

Имеем два стека: `st1` и `st2`

Push:
```
st1.push(x)
```

Pop:
```
if st2 is empty:
    переложить весь st1 в st2
st2.pop()
```

=== Асимптотика

аморт. $O(1)$

Над каждым элементом совершается не более 3 операций:
+ Положить в `st1`
+ Переложить из `st1` в `st2`
+ Вытащить из `st2`

== Вектор

+ Изначально выделяется память под несколько эл-в
+ Можем `push`-ить, пока `v.size() < v.capacity()`
+ Когда место кончается, вектор выделяет в два раза больше памяти и копирует
     туда элементы
+ При удалении `capacity()` не меняется

=== Асимптотика

аморт. $O(1)$

На $n$ операций уходит $n + n/2 + n/4 + ... + 1 -> 2n = O(n)$ копирований

= Метод потенциалов

Метод подсчета асимптотики

$ phi_0 -> phi_1 -> ... -> phi_n $

#def[
    #defitem[Потенциал] --- функция от наших структур данных
]

#def[
    #defitem[Аморт. время работы] --- $a_i = t_i + Delta phi$
]

$ sum a_i = sum (t_i + Delta phi) = sum t_i + (phi_n - phi_0) $

$
    (sum t_i) / n
        = (phi_0 - phi_n) / n + (sum a_i) / n
        <= (phi_0 - phi_n) / n + max(a_i)
$

Хотим минимизировать $max(a_i)$ и $(phi_0 - phi_n) / n$

== Для стека

$ phi_i := 2n_1 $

#figure(table(
    columns: 2,
    table.header(`push`, `pop`),
    $t_i = 1$, $t_i = 1 " или " 2n_1 + 1$,
    $a_i = 1 + 2 = 3$, $a_i = 1 " или " 2n_1 + 1 + (0 - 2n_1) = 1$,
))
