Компьютерный центр г. Светлогорска

Очередь (англ. 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())

Практические задания