Очередь
Очередь (англ. queue) — это структура данных, добавление и удаление элементов в которой происходит путём операций \(push\) и \(pop\) соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. first-in, first-out — FIFO). У очереди имеется голова (англ. head) и хвост (англ. tail). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.
Примером очереди в реальной жизни может являться очередь в магазине: первый покупатель в ней обслуживается первым, а другие покупатели занимают очередь с конца и ожидают, когда их обслужат.
Очередь поддерживает следующие операции:
● empty — проверка очереди на наличие в нем элементов,
● push (запись в очередь) — операция вставки нового элемента,
● pop (снятие с очереди) — операция удаления нового элемента,
● size — операция получения количества элементов в очереди.
Реализация циклической очереди на массиве
Очередь, способную вместить не более \(n\) элементов, можно реализовать с помощью массива \(array[0 \ldots n-1]\). Она будет обладать следующими полями:
● \(array[0 \ldots n-1] \) — массив, с помощью которого реализуется циклическая очередь, способная одновременно хранить не более \(n\) элементов,
● \(head\) — голова очереди,
● \(tail\) — хвост очереди.
class Queue:
def __init__(self, n):
self.array_size = n
self.queue = [0] * n
self.head = 0
self.tail = 0
def empty(self):
return self.head == self.tail
def push(self, x):
self.queue[self.tail] = x
self.tail = (self.tail + 1) % self.array_size
def pop(self):
if not self.is_empty():
x = self.queue[self.head]
self.head = (self.head + 1) % self.array_size
return x
def size(self):
if self.head > self.tail:
return self.array_size - self.head + self.tail
return self.tail - self.head
Реализация на двух стеках
Очередь можно реализовать на двух стеках: \(left\_stack\) и \(right\_stack\). Поступим следующим образом: \(left\_stack\) будем использовать для операции \(push\), \(right\_stack\) для операции \(pop\). При этом, если при попытке извлечения элемента из \(right\_stack\) он оказался пустым, просто перенесем все элементы из \(left\_stack\) в него (при этом элементы в \(right\_stack\) получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а \(left\_stack\) станет пустым).
class Queue:
def __init__(self):
self.left_stack = Stack()
self.right_stack = Stack()
def empty(self):
return self.left_stack.empty() and self.right_stack.empty()
def push(self, element):
self.left_stack.push(element)
def pop(self):
if self.right_stack.empty():
while not self.left_stack.empty():
self.right_stack.push(self.left_stack.pop())
if self.empty():
return 'UnderflowError'
return self.right_stack.pop()
Модификация очереди
Рассмотрим способ модификации очереди для нахождения минимума за \(O(1)\). Идея заключается в том, чтобы свести задачу к задаче на двух стеках.
Заведём два модифицированных для нахождения минимума за \(O(1)\) стека: \(s_1\) и \(s_2\). Нахождение минимума в очереди будет фактически заключаться в нахождении минимума из минимума в стеке \(s_1\) и минимума в стеке \(s_2\).
class MinQueue:
def __init__(self):
self.left_stack = MinStack()
self.right_stack = MinStack()
def empty(self):
return self.left_stack.empty() and self.right_stack.empty()
def push(self, element):
self.left_stack.push(element)
def pop(self):
if self.right_stack.empty():
while not self.left_stack.empty():
self.right_stack.push(self.left_stack.pop()[0])
if self.empty():
return 'UnderflowError'
return self.right_stack.pop()[0]
def get_min(self):
if self.empty():
return float('inf')
return min(self.left_stack.get_min(), self.right_stack.get_min())