Стеки и очереди в Python
Изучите 2 популярные линейные структуры данных.
Зачем это читать?
Стеки и очереди (произносится как kyo͞o или kiu) - это простые, но мощные структуры данных, которые могут помочь вам справиться с различными ситуациями, когда требуется некоторая упорядоченная операция или логика, и ваши данные аккуратно помещаются в стек или очередь аналогия. Они также довольно популярны в качестве вопросов на собеседовании по кодированию, поэтому, скорее всего, они будут на экзамене.
ℹ️ Linear data structures maintain a sequence and ordered relationship to the previous/next element, non linear data structures on the other hand can branch like a tree or have multiple relationships, let's keep it simple and use some graphic examples to explain both...
Основы: объяснение стопок с блинами:
# Using lists: pancakeStack = []
# The operation of adding things to a stack is called PUSH, but it's implemented with append in lists:
pancakeStack.append('Pancake #1')
pancakeStack.append('Pancake #2')
pancakeStack.append('Pancake #3')
print(pancakeStack) >> ['Pancake #1', 'Pancake #2', 'Pancake #3']
Ключевым поведением стека как структуры данных является способ добавления и удаления элементов, поэтому теперь, когда мы добавили некоторые элементы, удаление элементов выполняется по принципу последний пришел - первый ушел LIFO:
# The operation of removing things from a stack is called POP and matches the list method: pancakeStack.pop() print(pancakeStack) >> ['Pancake #1', 'Pancake #2']
# If you repeat the pop operation, you remove the next element on the stack... pancakeStack.pop() print(pancakeStack) >> ['Pancake #1']
# One last pop operation and you are left with an empty p̶l̶a̶t̶e̶ stack:
pancakeStack.pop()
print(pancakeStack)
>> []
👋👋 Hi there 👋👋 all my content is free for Medium subscribers, if you are already a subscriber I wanted to say thank you ! 🎉 If not and you are considering subscribing, you can use my membership referral link, you will be supporting this and other high quality content, Thank you ! ⭐️⭐ Subscribe to Medium ! ⭐️⭐️
Основы: объяснение очередей с билетной кассой:
# Let's start once more with an empty list which will be our queue. ticket_queue = []
# Adding elements is the same as with stacks, only here it's called enqueue or enqueuing (but still uses the append list method):
ticket_queue.append('Customer # 1')
# Let's add 2 more customers:
ticket_queue.append('Customer # 2')
ticket_queue.append('Customer # 3')
print(ticket_queue)
>> ['Customer # 1', 'Customer # 2', 'Customer # 3']
В отличие от стека, при удалении элементов очередь удаляет их с самого начала в режиме первым пришел FIFO, это также называется dequeue или dequeuing:
# The only difference here is the index given to pop(), which refers to the first element in the list: print(“Served:" + ticket_queue.pop(0)) Served:Customer # 1 print(ticket_queue) >> ['Customer # 2', 'Customer # 3']
You can continue removing or dequeuing elements in the same way:
print("Served: " + ticket_queue.pop(0))
>> Served: Customer # 2
print("Served: " + ticket_queue.pop(0))
>> Served: Customer # 3
print(ticket_queue)
>> []
Вот краткое абстрактное сравнение обоих:
Использует
Если бы вы где-нибудь в своей программе реализовали функцию undo, идеально подошла бы stack. Вы могли бы нажимать операции, когда они происходят в пользовательском интерфейсе, и выдавать их, когда вызывается команда отмены.
Допустим, вам нужно выполнить серию операций с некоторыми данными по мере их поступления или ввода в ваш скрипт. queue - хорошее место для хранения (постановки в очередь) данных и последующей их отправки для обработки.
Таким образом, в основном используются последовательные операции FIFO (первым пришел - первым ушел), LIFO (последний пришел - первым ушел). Прочтите другие мнения о причинах возникновения стеков и очередей здесь:
Сложности и альтернативные реализации:
The original reason (for me at least) to write this article came when reviewing someone else's code and finding an import for collections deque, the good news is that if you've been following the examples, you already know most of what collections deque does , so what follows is a brief overview...
В то время как списки [], кажется, отлично подходят для ваших средних потребностей в стеке и очереди. Если вам нужна более высокая производительность и некоторые дополнительные функции, есть другие варианты, популярный вариант - collections deque:
# STACK: The syntax is identical (except the deque object), but as mentioned you get better performance...
from collections import deque
pancakeStack = deque()
Adding elements:
pancakeStack.append('Pancake #1')
pancakeStack.append('Pancake #2')
pancakeStack.append('Pancake #3')
print(pancakeStack)
# >> deque(['Pancake #1', 'Pancake #2', 'Pancake #3'])
Removing elements:
pancakeStack.pop()
print(pancakeStack)
# >> deque(['Pancake #1', 'Pancake #2'])
Get removed element:
print(pancakeStack.pop())
# >> Pancake #2
---------------------||---------------------
# QUEUE: The syntax is also similar,the only difference is when removing elements you use popleft.
from collections import deque
ticket_queue = deque()
Adding elements:
ticket_queue.append('Customer # 1')
ticket_queue.append('Customer # 2')
ticket_queue.append('Customer # 3')
print(ticket_queue)
# >>> deque(['Customer # 1', 'Customer # 2', 'Customer # 3'])
Removing elements:
print(ticket_queue.popleft())
# >>> Customer # 1
print(ticket_queue)
# >>> deque(['Customer # 2', 'Customer # 3'])
Есть также несколько других функций, которые могут оказаться вам полезными. Они работают для списков и двухсторонней очереди:
# Length of queue or stack
print(len(pancakeStack))
# >> 3
# count items that match x:
print(pancakeStack.count('Pancake #1'))
# >> 1
# Add a bunch of pancakes in one go:
pancakes = ['Pancake #4','Pancake #5','Pancake #6']
pancakeStack.extend(pancakes)
['Pancake #1', 'Pancake #2', 'Pancake #3', 'Pancake #4', 'Pancake #5', 'Pancake #6']
# Reverse the queue or stack:
pancakeStack.reverse()
# >> ['Pancake #6', 'Pancake #5', 'Pancake #4', 'Pancake #3’...
------------- Deque only: -------------
# Rotate the stack... Move N elements from the end to the start :
pancakeStack.rotate(1)
>> ['Pancake #6', 'Pancake #1', 'Pancake #2', 'Pancake #3', 'Pancake #4', 'Pancake #5']
pancakeStack.rotate(2) # on the original order...
>> ['Pancake #5', 'Pancake #6', 'Pancake #1', 'Pancake #2', 'Pancake #3', 'Pancake #4']
#You can also do the inverse, moving elements from the front of the stack or queue to the back:
pancakeStack.rotate(-1)
['Pancake #2', 'Pancake #3', 'Pancake #4', 'Pancake #5', 'Pancake #6', 'Pancake #1']
# For the full feature set of deque, check the docs:
More complex: While beyond this overview, there is yet another way of implementing stacks and queues in python, only this time it is aimed at threaded programming : Python queue class: https://docs.python.org/3/library/queue.html
Заключение:
Как и многие другие вещи в кодировании, стеки и очереди могут сначала показаться пугающими, но при правильных аналогиях их становится легче понять. Здесь аналогии работают особенно хорошо, потому что эти структуры данных встречаются в повседневной жизни и идеально подходят. Если вы выпили кофе сегодня утром, вы, скорее всего, были частью очереди и стопки, как будто предметы и ситуации повсюду.
Реализация стеков и очередей также на удивление проста в python с использованием списков, и я надеюсь, что покрытие deque также поможет вам, если вы когда-нибудь столкнетесь с этим в дикой природе.
Спасибо за прочтение!
