Очередь

определение
Очередь реализует быстрые операции добавления в конец и извлечения из начала очереди.

Хотя динамические массивы и не поддерживают быстрое извлечение элемента из начала массива, на них можно построить очередь. Для этого нужно добавить ещё один указатель, который будет показывать первый элемент в очереди. Когда надо извлечь элемент из начала, этот первый элемент возвращается, а указатель смещается на один элемент вправо.
Операции, связанные с очередью

  • enqueue: Добавляет в конец очереди элемент. Если очередь заполнена, вызывает исключение. Временная сложность: O(1)
  • dequeue: Удаляет первый элемент из очереди. Если очередь заполнена, вызывает исключение. Временная сложность: O(1)
  • front : получить передний элемент из очереди. Временная сложность: O(1)
  • real: получить последний элемент из очереди . Временная сложность: O (1)
способы реализации стека
  • список list
  • Сollections.deque
  • Queue.Queue
  • Создание класса односвязного списка.
Список list
Список можно использовать как очередь. Вместо enqueue() и dequeue() используются функции append() и pop(). Однако списки для этой цели довольно медленны, потому что вставка или удаление элемента в начале требует сдвига всех остальных элементов на единицу, что требует O(n) времени.
Для реализации большой очереди не рекомендуется. 

queue = []

# добавление элементов в стек
queue.append('a')

# извлечение и удаление элементов
element = queue.pop(0)
COLLECTIONS.DEQUE
Очередь можно реализовать с помощью класса deque из модуля collections.

Deque имеет более быстрые операции добавления и извлечения элементов с обоих концов контейнера.

from collections import deque
 
stack = deque()

# добавление элементов в стек
stack.append(1)

# извлечение и удаление элементов
element = stack.pop()
Queue.LifoQueue
Модуль Queue имеет структуру данных Queue.

В этом модуле доступны различные функции:

  • maxsize — допустимое количество элементов в очереди.
  • empty() — возвращает True, если очередь пуста, в противном случае — False.
  • full() — возвращает True, если в очереди есть элементы максимального размера .
  • get() — удалить и вернуть элемент из очереди. Если очередь пуста, блокирует на время указанного тайм-аута.
  • get_nowait () — вернуть элемент, если он доступен сразу, в противном случае поднять исключение QueueEmpty.
  • put(item) – поместить предмет в очередь. Если очередь заполнена, подождите, пока освободится свободный слот.
  • put_nowait(item) – Поместить предмет в очередь без блокировки. Если нет свободных мест, поднять исключение QueueFull.
  • qsize() — возвращает количество элементов в очереди. 

from queue import Queue
 
stack = LifoQueue(maxsize=3)

# добавление элементов в стек
stack.put('a')

# извлечение и удаление элементов
element = stack.get()
Создание очереди на классе
Реализуем Очередь с использованием класса и реализацией кольцевого буфера. Класс будет иметь методы:

  • push(item) — добавляет элемент в конец очереди;
  • pop() — берёт элемент из начала очереди и удаляет его

class Queue:
    def __init__(self, n):
        self.queue = [None] * n
        self.max_n = n
        self.head = 0
        self.tail = 0
        self.size = 0

def is_empty(self):
    return self.size == 0
  
def push(self, x):
    if self.size != self.max_n:
        self.queue[self.tail] = x
        self.tail = (self.tail + 1) % self.max_n
        self.size += 1

def pop(self):
    if self.is_empty():
        return None
    x = self.queue[self.head]
    self.queue[self.head] = None
    self.head = (self.head + 1) % self.max_n
    self.size -= 1
    return x
КОГДА ЛУЧШЕ ИСПОЛЬЗОВАТЬ Очередь
Хорошим примером очереди является любая очередь потребителей ресурса, в которой потребитель, пришедший первым, обслуживается первым.

Очередь используется в алгоритме графов поиск в ширину.