Структуры данных организуют хранилище на компьютерах, чтобы мы могли эффективно получать доступ к данным и изменять их. Стеки и очереди – одни из самых ранних структур данных, определенных в информатике.
Их легко изучить и легко реализовать, они широко используются, и вы, скорее всего, обнаружите, что включаете их в свое программное обеспечение для различных задач.
Обычно стеки и очереди реализуются с помощью массива или связанного списка. Мы будем полагаться на структуру данных List для размещения, как стеков, так и очередей.
Как они работают?
Стеки, как следует из названия, следуют принципу Last-in-First-Out (LIFO). Как будто укладывая монеты одна на другую, последняя монета, которую мы кладем на вершину, — это та, которая будет первой удаляться из стопки позже.
Поэтому для реализации стека нам нужны две простые операции:
- push – добавляет элемент в начало стека:
- pop – удаляет элемент вверху стека:
Очереди
Очереди, как следует из названия, следуют принципу «первым пришел – первым обслужен» (FIFO). Как будто ожидая в очереди за билетами в кино, первым в очереди встает тот, кто первым покупает билет и наслаждается просмотром.
Поэтому для реализации очереди нам понадобятся две простые операции:
- enqueue – добавляет элемент в конец очереди:
- dequeue – удаляет элемент в начале очереди:
С использованием списков
Встроенная в Python структура данных List поставляется в комплекте с методами для имитации операций стека и очереди.
Рассмотрим стопку букв:
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']
Опять же, здесь мы используем операции добавления и извлечения списка для имитации основных операций очереди.
С библиотекой 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])
Более строгие реализации
Если вашему коду нужен стек, а вы предоставляете список, ничто не мешает программисту вызывать функции вставки, удаления или другие функции списка, которые повлияют на порядок вашего стека! Это в корне нарушает суть определения стека, поскольку он больше не работает так, как должен.
Бывают случаи, когда мы хотим убедиться, что с нашими данными могут выполняться только допустимые операции.
Мы можем создавать классы, которые предоставляют только необходимые методы для каждой структуры данных.
Для этого давайте создадим новый файл с именем 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)
Программистам, использующим наши стек и очередь, теперь предлагается использовать вместо этого методы, предоставленные для управления данными.
Примеры
Представьте, что вы разработчик, работающий над новым текстовым процессором. Вам поручено создать функцию отмены, позволяющую пользователям отменять свои действия до начала сеанса.
Стек идеально подходит для этого скрипта. Мы можем записывать каждое действие пользователя, помещая его в стек. Когда пользователь хочет отменить действие, он выталкивает его из стека. Мы можем быстро смоделировать эту функцию следующим образом:
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. С очередями мы добавляем элементы с помощью операции постановки в очередь и получаем элементы с помощью операции постановки из очереди.
В Python мы можем реализовать стеки и очереди, просто используя встроенную структуру данных List. Python также имеет библиотеку deque, которая может эффективно предоставлять операции стека и очереди в одном объекте. Наконец, мы создали классы стека и очереди для более жесткого контроля над нашими данными.
Существует множество реальных вариантов использования стеков и очередей, понимание которых позволяет нам легко и эффективно решать многие проблемы с хранением данных.