Массивы, связные списки, стеки и очереди

Узнай, как массив хранится в памяти, почему динамический массив добавляет элемент за амортизированное O(1), как устроены связные списки и где применяются стеки и очереди.

  • Университет
  • 25 мин
  • 10 вопросов
  • Урок 47 из 59

В этом уроке ты узнаешь

  • Вычислять адрес элемента массива и объяснять доступ за O(1)
  • Доказывать амортизированную стоимость добавления в динамический массив
  • Сравнивать массив и связный список по сложности операций
  • Выбирать для задачи стек или очередь и применять их

Нажимая в браузере «Назад», ты возвращаешься на страницу, открытую последней, а в электронной очереди в сервисном центре первым обслуживают того, кто первым взял талон. Эти два бытовых правила — суть двух базовых структур данных: стека и очереди. Под ними лежат ещё более простые «кирпичики» — массив и связный список. Знание сильных и слабых сторон каждой структуры часто определяет скорость программы сильнее, чем сам алгоритм.

Массив и динамический массив

МассивОпределение

Структура, в которой элементы одинакового размера хранятся в памяти подряд, без промежутков. Адрес элемента вычисляется по индексу простой формулой, поэтому доступ к любому элементу занимает O(1).

addr(A[i]) = base + i · s

Где

base
начальный адрес массива (адрес A[0])
i
индекс элемента (начиная с 0)
s
размер одного элемента, байт

Именно поэтому индексы начинаются с 0: i показывает, на сколько шагов элемент удалён от начала.

Пример 1: вычисление адреса

Задача

Массив 4-байтовых целых чисел начинается с адреса 1000. По какому адресу находится A[25]? На сколько меняется адрес при переходе от A[5] к A[6]?

Показать решениеСкрыть решение

Решение

addr(A[25]) = 1000 + 25 · 4 = 1000 + 100 = 1100.
Соседние элементы отличаются на s = 4 байта.
При любом i вычисление — одно умножение и одно сложение; поэтому доступ и занимает O(1).

Есть и цена: чтобы вставить элемент в середину массива, все элементы справа нужно сдвинуть на одно место — O(n). Кроме того, размер задаётся заранее. Динамический массив (list в Python, ArrayList в Java, vector в C++) решает это так: когда место заканчивается, он выделяет новый массив вдвое большего размера и копирует туда старые элементы.

(n + 1 + 2 + 4 + … + 2ᵏ) / n < (n + 2n) / n = 32ᵏ < n(n + 1 + 2 + 4 + … + 2ᵏ) / n < (n + 2n) / n = 32ᵏ < n

Где

n
число добавленных элементов
1 + 2 + … + 2ᵏ
сумма копирований при всех расширениях (< 2n)

Амортизированная стоимость: общая работа n добавлений меньше 3n, значит, одно добавление в среднем стоит O(1) — несмотря на редкие «дорогие» расширения.

Python
class DynamicArray:
    def __init__(self):
        self.cap, self.n, self.copies = 1, 0, 0
        self.data = [None]

    def append(self, x):
        if self.n == self.cap:
            self.cap *= 2
            new = [None] * self.cap
            for i in range(self.n):
                new[i] = self.data[i]
                self.copies += 1
            self.data = new
        self.data[self.n] = x
        self.n += 1

arr = DynamicArray()
for k in range(1, 1025):
    arr.append(k)
    if k in (1, 2, 3, 5, 9, 17, 1024):
        print(k, arr.cap, arr.copies)
print('copies per append:', arr.copies / arr.n)
Ожидаемый результат
1 1 0
2 2 1
3 4 3
5 8 7
9 16 15
17 32 31
1024 1024 1023
copies per append: 0.9990234375
Столбцы: число элементов, ёмкость, общее число копирований. Расширение происходит только на 2-м, 3-м, 5-м, 9-м, 17-м… добавлении; после 1024 добавлений было всего 1023 копирования — меньше одного на добавление.

Чтобы читать дальше, зарегистрируйся бесплатно

Остальные разделы урока, тест и заметки открываются с аккаунтом Educora. Регистрация занимает минуту, а прогресс сохраняется на всех твоих устройствах.

Связные списки

Связный списокОпределение

Цепочка, в которой каждый узел хранит значение и указатель на следующий узел. Узлы могут находиться где угодно в памяти; первый узел называют головой (head). В двусвязном списке каждый узел хранит ещё и указатель на предыдущий.

ОперацияДинамический массивОдносвязный список
доступ к i-му элементуO(1)O(n)
вставка / удаление в началеO(n)O(1)
добавление в конецамортизированно O(1)O(1) (с указателем tail)
вставка после известного узлаO(n) (сдвиг)O(1)
поиск по значениюO(n)O(n)
памятькомпактно, дружит с кэшемлишний указатель на узел, разбросано
Выбор: если часто читаешь по индексу — массив; если часто вставляешь и удаляешь в начале или середине — список.
Python
class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next
class LinkedList:
    def __init__(self):
        self.head = None
    def push_front(self, value):
        self.head = Node(value, self.head)
    def reverse(self):
        prev, cur = None, self.head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev, cur = cur, nxt
        self.head = prev
    def items(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next
lst = LinkedList()
for city in ['Shaki', 'Ganja', 'Baku']: lst.push_front(city)
print(list(lst.items()))
lst.reverse()
print(list(lst.items()))
Ожидаемый результат
['Baku', 'Ganja', 'Shaki']
['Shaki', 'Ganja', 'Baku']
push_front присоединяет новый узел в голову за O(1). reverse разворачивает список за один проход — O(n) времени и O(1) дополнительной памяти, поворачивая указатель каждого узла назад. Это классическая задача на собеседованиях.

Стек (LIFO) и очередь (FIFO)

СтруктураПринципОперации (все O(1))Применения
СтекLIFO — последним пришёл, первым вышелpush, pop, peekстек вызовов, отмена действий, проверка скобок, DFS
ОчередьFIFO — первым пришёл, первым вышелenqueue, dequeue, frontочередь печати, сетевые буферы, планировщики задач, BFS

Пример 2: вычисление постфиксного выражения стеком

Задача

В постфиксной (обратной польской) записи оператор стоит после операндов. Вычисли 5 1 2 + 4 * + 3 - с помощью стека.

Показать решениеСкрыть решение

Решение

Правило: число → push; оператор → pop двух чисел, push результата.
5 → [5]
1 → [5, 1]
2 → [5, 1, 2]
+ → 1 + 2 = 3 → [5, 3]
4 → [5, 3, 4]
* → 3 · 4 = 12 → [5, 12]
+ → 5 + 12 = 17 → [17]
3 → [17, 3]
- → 17 − 3 = 14 → [14]
Ответ: 14 (в обычной записи 5 + (1 + 2) · 4 − 3). Каждый символ обрабатывается один раз → O(n).
Python
from collections import deque

def balanced(text):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in text:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

for s in ['(a[i] + b) * {c}', '(]', '((x)']:
    print(s, balanced(s))

queue = deque(['Aysel', 'Murad', 'Leyla'])
queue.append('Elvin')
print(queue.popleft(), 'is served;', list(queue), 'wait')
Ожидаемый результат
(a[i] + b) * {c} True
(] False
((x) False
Aysel is served; ['Murad', 'Leyla', 'Elvin'] wait
Стек хранит открывающие скобки: каждая закрывающая должна совпасть с вершиной стека, а в конце стек должен быть пуст. deque добавляет и удаляет с обоих концов за O(1) — идеальная очередь.

Очередь можно построить и на массиве фиксированного размера: кольцевой буфер хранит индексы головы (head) и хвоста (tail) и, дойдя до конца массива, «заворачивает» в начало с помощью остатка от деления. Такая очередь не выделяет память и используется в сетевых и звуковых картах, в буфере клавиатуры.

tail = (head + size) mod mnext(i) = (i + 1) mod m

Где

head
индекс первого элемента очереди
size
число элементов в очереди
m
ёмкость массива
tail
индекс, куда запишется следующий элемент

Пример 3: кольцевой буфер

Задача

В кольцевом буфере ёмкости m = 6 head = 4, size = 3. По какому индексу запишется новый элемент? Затем извлекают два элемента. Чему станет равен head?

Показать решениеСкрыть решение

Решение

Элементы занимают индексы 4, 5, 0.
tail = (4 + 3) mod 6 = 7 mod 6 = 1 → новый элемент запишется в A[1], size = 4.
Два извлечения: head = (4 + 1) mod 6 = 5, затем (5 + 1) mod 6 = 0; size = 2.

Классический вопрос на собеседовании: построить очередь из двух стеков. Новые элементы кладутся (push) в стек in. Для извлечения, если стек out пуст, все элементы из in по одному перекладываются в out — порядок при этом переворачивается, и самый старый элемент оказывается сверху. Отдельное извлечение может стоить O(n), но каждый элемент перекладывается не более одного раза, поэтому n операций стоят O(n), то есть амортизированно O(1) каждая.

Запомни

  • Адрес элемента массива — base + i · s: доступ O(1), вставка в середину O(n).
  • Динамический массив увеличивает ёмкость геометрически, поэтому добавление в конец — амортизированно O(1).
  • В связном списке вставка в голову или после известного узла — O(1), а доступ по индексу — O(n).
  • Стек — LIFO (вызовы, отмена, скобки), очередь — FIFO (буферы, BFS); операции обоих — O(1).
  • Кольцевой буфер заворачивает индексы по mod m и даёт очередь в фиксированной памяти.
Заметил ошибку или неточность в уроке?

Проверь себя

Вопросов: 10. Каждый правильный ответ приносит XP.

Вопрос 1 / 10

Вопрос 1 / 10. В динамический массив, ёмкость которого начинается с 1 и каждый раз удваивается, добавляют 64 элемента. Сколько всего копирований элементов будет?