Нажимая в браузере «Назад», ты возвращаешься на страницу, открытую последней, а в электронной очереди в сервисном центре первым обслуживают того, кто первым взял талон. Эти два бытовых правила — суть двух базовых структур данных: стека и очереди. Под ними лежат ещё более простые «кирпичики» — массив и связный список. Знание сильных и слабых сторон каждой структуры часто определяет скорость программы сильнее, чем сам алгоритм.
Массив и динамический массив
МассивОпределение
Структура, в которой элементы одинакового размера хранятся в памяти подряд, без промежутков. Адрес элемента вычисляется по индексу простой формулой, поэтому доступ к любому элементу занимает O(1).
Где
- base
- начальный адрес массива (адрес A[0])
- i
- индекс элемента (начиная с 0)
- s
- размер одного элемента, байт
Именно поэтому индексы начинаются с 0: i показывает, на сколько шагов элемент удалён от начала.
Пример 1: вычисление адреса
Задача
Массив 4-байтовых целых чисел начинается с адреса 1000. По какому адресу находится A[25]? На сколько меняется адрес при переходе от A[5] к A[6]?
Показать решениеСкрыть решение
Решение
Соседние элементы отличаются на s = 4 байта.
При любом i вычисление — одно умножение и одно сложение; поэтому доступ и занимает O(1).
Есть и цена: чтобы вставить элемент в середину массива, все элементы справа нужно сдвинуть на одно место — O(n). Кроме того, размер задаётся заранее. Динамический массив (list в Python, ArrayList в Java, vector в C++) решает это так: когда место заканчивается, он выделяет новый массив вдвое большего размера и копирует туда старые элементы.
Где
- n
- число добавленных элементов
- 1 + 2 + … + 2ᵏ
- сумма копирований при всех расширениях (< 2n)
Амортизированная стоимость: общая работа n добавлений меньше 3n, значит, одно добавление в среднем стоит O(1) — несмотря на редкие «дорогие» расширения.
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
Чтобы читать дальше, зарегистрируйся бесплатно
Остальные разделы урока, тест и заметки открываются с аккаунтом Educora. Регистрация занимает минуту, а прогресс сохраняется на всех твоих устройствах.
Связные списки
Связный списокОпределение
Цепочка, в которой каждый узел хранит значение и указатель на следующий узел. Узлы могут находиться где угодно в памяти; первый узел называют головой (head). В двусвязном списке каждый узел хранит ещё и указатель на предыдущий.
| Операция | Динамический массив | Односвязный список |
|---|---|---|
| доступ к i-му элементу | O(1) | O(n) |
| вставка / удаление в начале | O(n) | O(1) |
| добавление в конец | амортизированно O(1) | O(1) (с указателем tail) |
| вставка после известного узла | O(n) (сдвиг) | O(1) |
| поиск по значению | O(n) | O(n) |
| память | компактно, дружит с кэшем | лишний указатель на узел, разбросано |
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 - с помощью стека.
Показать решениеСкрыть решение
Решение
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).
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'] waitdeque добавляет и удаляет с обоих концов за O(1) — идеальная очередь.Очередь можно построить и на массиве фиксированного размера: кольцевой буфер хранит индексы головы (head) и хвоста (tail) и, дойдя до конца массива, «заворачивает» в начало с помощью остатка от деления. Такая очередь не выделяет память и используется в сетевых и звуковых картах, в буфере клавиатуры.
Где
- head
- индекс первого элемента очереди
- size
- число элементов в очереди
- m
- ёмкость массива
- tail
- индекс, куда запишется следующий элемент
Пример 3: кольцевой буфер
Задача
В кольцевом буфере ёмкости m = 6 head = 4, size = 3. По какому индексу запишется новый элемент? Затем извлекают два элемента. Чему станет равен head?
Показать решениеСкрыть решение
Решение
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 и даёт очередь в фиксированной памяти.