- 6 августа 2025
- 5 минут
- 294
Значение понятия “Очередь” и техники ее реализации в Python
Статью подготовили специалисты образовательного сервиса Zaochnik.
Основные принципы очереди в программировании
Очередь (англ. – Turn) представляет собой структуру данных, из которой первым удаляется тот элемент, который был добавлен первым. Таким образом, очередь в программировании аналогична «бытовому» понятию очереди. Этот тип структуры данных также обозначается как FIFO (first in, first out — первый пришел, первый ушел).
Очередь поддерживает те же операции, что и стек, за исключением того, что операции `pop` и `top` работают с противоположным концом очереди.
- “push” — добавить новый элемент в конец очереди
- “pop” — извлечь первый элемент из очереди
- “top” — получить значение первого элемента (не удаляя его)
- “size” — узнать количество элементов в очереди
Очередь на Python
Можно предположить, что очередь можно легко реализовать, просто удаляя из списка не последний, а первый элемент:
```python
Turn = []
def push(val):
Turn.append(val)
def pop():
return Turn.pop(0)
def top():
return Turn[0]
def size():
return len(Turn)
def isempty():
return len(Turn) == 0
def clear():
Turn[:] = []
```
Однако такая реализация имеет недостаток: удаление элемента из начала списка выполняется за линейное время O(n), так как необходимо сдвинуть все последующие элементы. Это приводит к тому, что операция удаления элемента из очереди требует O(n) времени, где n — количество элементов в очереди.
Вместо этого мы можем не удалять элемент, а просто помечать его как неиспользуемый. Таким образом, в начале списке будут располагаться элементы, которые ранее находились в очереди, но были помечены как удаленные. Мы можем ввести переменную `TurnStart`, которая будет хранить индекс текущего первого элемента в очереди. Тогда извлечение элемента из очереди будет заключаться в увеличении значений `TurnStart` на 1. Длина очереди будет равна размеру списка минус количество удаленных элементов, т.е. `len(Turn) - TurnStart`. Вот как это будет выглядеть в реализации:
```python
Turn = []
TurnStart = 0
def push(val):
Turn.append(val)
def top():
return Turn[TurnStart]
def pop():
global TurnStart
TurnStart += 1
return Turn[TurnStart - 1]
def size():
return len(Turn) - TurnStart
```
У этой реализации есть другой недостаток: начало очереди может быть заполнено «ненужными» элементами, которые больше не используются. Если из очереди было удалено много элементов, то значительная часть будет состоять из этих ненужных элементов, что в итоге ведет к излишнему расходу памяти.
Техника ленивого удаления
Чтобы бороться с излишним заполнением памяти, можно время от времени очищать неиспользуемые элементы из начала очереди. Если количество неиспользуемых элементов невелико, они могут оставаться. Однако, если их накопилось много, следует выделить время для удаления неиспользуемых элементов из начала списка.
Эта техника называется «ленивое удаление». Суть заключается в том, что ненужные элементы не удаляются физически из структуры данных, а просто помечаются как неиспользуемые. Если таких элементов становится много, выполняется реальное удаление, которое требует больше времени, но делается редко.
Критерием для реального удаления неиспользуемых элементов станет условие, что они занимают более половины от общего числа размещенных в списке элементов. Следующая функция описывает реализацию операции `pop` с учетом этого принципа:
```python
def pop():
global TurnStart
result = Turn[TurnStart]
TurnStart += 1
if TurnStart > len(Turn) / 2:
Turn[:TurnStart] = []
TurnStart = 0
return result
```
Сложность данной реализации такова: в худшем случае операция удаления выполняется за O(n), однако если выполнить `k` операций с очередью, то общее время выполнения всех операций `pop` будет O(k). В этом случае говорят, что среднее время работы операции удаления составляет O(1).
Замкнутая очередь
Существует и другой способ борьбы с ненужными элементами в начале списка — это создание «замкнутой» очереди. В этом случае ограничивается максимальный размер очереди. Если очередь достигает конца выделенного массива, новые элементы будут добавляться в начало очереди. То есть реализация очереди на базе «закольцованного» массива подразумевает, что после последнего элемента массива идет первый элемент. В такой реализации необходимо хранить индекс начального элемента в очереди и индекс последнего элемента (или общее количество элементов в очереди).
Программирование
14.06.2024
120
15