Неделя 4 — Структуры данных: списки, стеки и очереди

На этой неделе курса мы изучим базовые структуры данных, которые позволяют эффективно хранить и обрабатывать данные. Мы рассмотрим списки, стеки, очереди, методы их реализации, применение и базовые алгоритмы на них.

Списки в Python

Списки — упорядоченные изменяемые коллекции. Примеры:

```python```

numbers = [1, 2, 3]

print(numbers[0])   # 1

numbers.append(4)

Операции:

- добавление: `append()`, `insert()`

- удаление: `pop()`, `remove()`

- сортировка: `sort()`, `reverse()`

Перебор списков и списковые включения

```python```

for x in numbers:

print(x)

squares = [x**2 for x in range(10)]

Стек (LIFO)

Стек — структура «последним пришёл — первым вышел». В Python можно реализовать через список:

```python```

stack = []

stack.append("a")

stack.append("b")

print(stack.pop())  # b

Применения: возврат из функций, обработка скобок, отмена действий.

Очередь (FIFO)

Очередь — структура «первым пришёл — первым вышел». Для очередей лучше использовать `collections.deque`:

```python```

from collections import deque

queue = deque()

queue.append("a")

queue.append("b")

print(queue.popleft())  # a

Применения: планирование задач, буферизация, обработка событий.

Приоритетная очередь

Элементы с более высоким приоритетом извлекаются первыми. Реализация:

```python```

import heapq

pq = []

heapq.heappush(pq, (1, "low"))

heapq.heappush(pq, (0, "high"))

print(heapq.heappop(pq))  # (0, 'high')