Автор оригинала: Marcus Sanatan.
Стеки и очереди в Python
Вступление
Структуры данных организуют хранение в компьютерах, чтобы мы могли эффективно получать доступ к данным и изменять их. Стеки и Очереди являются одними из самых ранних структур данных, определенных в информатике.
Простые в освоении и легко реализуемые, они широко используются, и вы, скорее всего, обнаружите, что включаете их в свое программное обеспечение для различных задач.
Обычно стеки и очереди реализуются с помощью массива или Связанного списка . Мы будем полагаться на структуру данных List для размещения как стеков, так и очередей.
Как они работают?
Стек
Стеки, как следует из названия, следуют принципу Last-in-First-Out (LIFO). Как если бы мы складывали монеты одну на другую, последняя монета, которую мы кладем сверху, – это та, которая будет первой извлечена из стопки позже.
Поэтому для реализации стека нам нужны две простые операции:
push– добавляет элемент в верхнюю часть стека:
pop– удаляет элемент в верхней части стека:
Очередь
Очереди, как следует из названия, следуют принципу First-in-First-Out (FIFO). Как будто ожидая в очереди за билетами в кино, первый, кто встанет в очередь, первым купит билет и насладится фильмом.
Поэтому для реализации очереди нам нужны две простые операции:
enqueue– добавляет элемент в конец очереди:
dequeue– удаляет элемент в начале очереди:
Стеки и очереди с использованием списков
Встроенная структура данных Python List поставляется в комплекте с методами для имитации операций stack и queue .
Давайте рассмотрим стопку писем:
letters = []
# Let's push some letters into our list
letters.append('c')
letters.append('a')
letters.append('t')
letters.append('g')
# Now let's pop letters, we should get 'g'
last_item = letters.pop()
print(last_item)
# If we pop again we'll get 't'
last_item = letters.pop()
print(last_item)
# 'c' and 'a' remain
print(letters) # ['c', 'a']
Мы можем использовать те же функции для реализации очереди. Функция pop опционально принимает в качестве аргумента индекс элемента, который мы хотим получить.
Таким образом, мы можем использовать pop с первым индексом списка, т. е. 0 , чтобы получить поведение, подобное очереди.
Рассмотрим “очередь” из фруктов:
fruits = []
# Let's enqueue some fruits into our list
fruits.append('banana')
fruits.append('grapes')
fruits.append('mango')
fruits.append('orange')
# Now let's dequeue our fruits, we should get 'banana'
first_item = fruits.pop(0)
print(first_item)
# If we dequeue again we'll get 'grapes'
first_item = fruits.pop(0)
print(first_item)
# 'mango' and 'orange' remain
print(fruits) # ['c', 'a']
Опять же, здесь мы используем операции append и pop списка для имитации основных операций очереди.
Стеки и очереди с библиотекой Deque
Python имеет библиотеку deque (произносится как “палуба”), которая предоставляет последовательность с эффективными методами для работы в виде стека или очереди.
deque сокращенно от Double Ended Queue – обобщенная очередь, которая может получить первый или последний сохраненный элемент:
from collections import deque # you can initialize a deque with a list numbers = deque() # Use append like before to add elements numbers.append(99) numbers.append(15) numbers.append(82) numbers.append(50) numbers.append(47) # You can pop like a stack last_item = numbers.pop() print(last_item) # 47 print(numbers) # deque([99, 15, 82, 50]) # You can dequeue like a queue first_item = numbers.popleft() print(first_item) # 99 print(numbers) # deque([15, 82, 50])
Если вы хотите узнать больше о библиотеке deque и других типах коллекций, предоставляемых Python, вы можете прочитать нашу статью Введение в модуль коллекций Python .
Более строгие реализации в Python
Если вашему коду нужен стек и вы предоставляете List , то ничто не мешает программисту вызвать insert , remove или другие функции списка, которые повлияют на порядок вашего стека! Это в корне разрушает смысл определения стека, поскольку он больше не функционирует так, как должен.
Бывают случаи, когда мы хотим убедиться, что с нашими данными можно выполнять только допустимые операции.
Мы можем создавать классы, которые предоставляют только необходимые методы для каждой структуры данных.
Для этого создадим новый файл с именем stack_queue.py и определить два класса:
# A simple class stack that only allows pop and push operations
class Stack:
def __init__(self):
self.stack = []
def pop(self):
if len(self.stack) < 1:
return None
return self.stack.pop()
def push(self, item):
self.stack.append(item)
def size(self):
return len(self.stack)
# And a queue that only has enqueue and dequeue operations
class Queue:
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if len(self.queue) < 1:
return None
return self.queue.pop(0)
def size(self):
return len(self.queue)
Программистам, использующим наши Stack и Queue , теперь рекомендуется использовать методы, предоставляемые для манипулирования данными.
Примеры
Представьте, что вы разработчик, работающий над совершенно новым текстовым процессором. Вам поручено создать функцию отмены, позволяющую пользователям отслеживать свои действия до начала сеанса.
Стек идеально подходит для этого сценария. Мы можем записывать каждое действие пользователя, помещая его в стек. Когда пользователь захочет отменить действие, он вытащит его из стека. Мы можем быстро смоделировать эту функцию следующим образом:
document_actions = Stack()
# The first enters the title of the document
document_actions.push('action: enter; text_id: 1; text: This is my favourite document')
# Next they center the text
document_actions.push('action: format; text_id: 1; alignment: center')
# As with most writers, the user is unhappy with the first draft and undoes the center alignment
document_actions.pop()
# The title is better on the left with bold font
document_actions.push('action: format; text_id: 1; style: bold')
Очереди также широко используются в программировании. Подумайте о таких играх, как Street Fighter или Super Smash Brothers . Игроки в этих играх могут выполнять специальные движения, нажимая комбинацию кнопок. Эти комбинации кнопок можно хранить в очереди.
А теперь представьте, что вы разработчик, работающий над новым файтингом. В вашей игре каждый раз, когда нажимается кнопка, срабатывает входное событие. Тестировщик заметил, что если кнопки нажимаются слишком быстро, игра обрабатывает только первую, и специальные ходы не работают!
Вы можете исправить это с помощью очереди. Мы можем ставить в очередь все входные события по мере их поступления. Таким образом, не имеет значения, если входные события приходят с небольшим промежутком времени между ними, все они будут сохранены и доступны для обработки. Когда мы обрабатываем ходы, мы можем удалить их из очереди. Специальный ход может быть разработан так:
input_queue = Queue()
# The player wants to get the upper hand so pressing the right combination of buttons quickly
input_queue.enqueue('DOWN')
input_queue.enqueue('RIGHT')
input_queue.enqueue('B')
# Now we can process each item in the queue by dequeueing them
key_pressed = input_queue.dequeue() # 'DOWN'
# We'll probably change our player position
key_pressed = input_queue.dequeue() # 'RIGHT'
# We'll change the player's position again and keep track of a potential special move to perform
key_pressed = input_queue.dequeue() # 'B'
# This can do the act, but the game's logic will know to do the special move
Вывод
Стеки и очереди-это простые структуры данных, которые позволяют нам хранить и извлекать данные последовательно. В стеке последний элемент, который мы вводим, выходит первым. В очереди первый элемент, который мы вводим, – это первый выход.
Мы можем добавлять элементы в стек с помощью операции push и извлекать элементы с помощью операции pop . С помощью очередей мы добавляем элементы с помощью операции enqueue и извлекаем элементы с помощью операции dequeue .
В Python мы можем реализовать стеки и очереди, просто используя встроенную структуру данных List . Python также имеет библиотеку deque , которая может эффективно обеспечивать операции стека и очереди в одном объекте. Наконец, мы сделали наши классы стека и очереди для более жесткого контроля наших данных.
Существует множество реальных вариантов использования стеков и очередей, понимание которых позволяет нам легко и эффективно решать многие проблемы хранения данных.