Структуры данных Очередь и Дек

В прошлом уроке вы познакомились со стеком, а этот посвящён очереди. В отличие от стека, который работает по принципу LIFO (Last In First Out), очередь основана на концепции FIFO (с англ. First In First Out — «первый вошёл, первый вышел»). То есть первым извлекают элемент, который добавили раньше всех. Сложность этой операции должна быть O(1).
image
На основе этой структуры данных реализованы многие сущности в программировании.
Если несколько процессов хотят получить доступ к одному ресурсу, в общем случае они встают в очередь. На работу с этим ресурсом операционная система выделяет каждому процессу по очереди небольшой квант времени. Это время настолько мало, что нам кажется, будто несколько программ работают параллельно. В один и тот же момент можно писать письмо, слушать музыку, скачивать файл из интернета. Но количество действительно одновременно работающих программ не превышает количество ядер в процессоре.
Другой пример.
Возможно, вы слышали об очередях сообщений — например, RabbitMQ или kafka. В их основе лежит концепция очередей. Этот пример концептуально похож на предыдущий. В очередь становятся объекты, которые хотят получить доступ к какому-то ресурсу.
С очередями в повседневной жизни сталкиваемся мы все.
Кассир в магазине может одновременно обслуживать только одного покупателя, поэтому приходится стоять в очереди.
Если мы звоним по горячей линии и все операторы заняты, тоже нужно ждать.
При моделировании подобных сценариев в программировании удобно применять структуру данных очередь.
Например, в стандартной библиотеке Python есть модуль queue (с англ. «‎очередь»), а в этом модуле — объект Queue, реализация очереди.
Аналогичный объект есть не во всех языках программирования. Но мы его рассмотрим, так как на этом примере можно разобраться, как работают очереди.
Скопировать кодPYTHON
from queue import Queue

queue = Queue()
queue.put('a')
queue.put('b')
Чтобы добавить элемент в очередь, применяют метод put(), а чтобы извлечь — метод get().
Извлечём элемент из очереди:
Скопировать кодPYTHON
elem = queue.get()
Как вы думаете, что вернётся при вызове метода get()?
Размер очереди определяют методом qsize():
Скопировать кодPYTHON
size_of_queue = queue.qsize()
Что выведется, если напечатать значение переменной size_of_queue?
Существует несколько способов реализации очереди.
Например, можно использовать массив.
Идея: создадим динамический массив. Если нужно добавить элемент в очередь, добавим его в конец. Если нужно извлечь элемент, удалим элемент на позиции 0.
Сработает ли эта идея для реализации очереди?
Тем не менее с использованием массива можно реализовать очередь, которая вместит не более n элементов.
Разберёмся, как это можно сделать:
Создадим класс очередь. У объекта будут поля:
  • head — индекс, по которому нужно извлекать элемент, если очередь не пустая;
  • tail — индекс, по которому нужно добавлять элемент, если в очереди есть место;
  • max_n — максимально возможное число элементов в очереди;
  • size — размер очереди.
Скопировать кодPYTHON
class Queue:
    def __init__(self, n):
        self.queue = [None for _ in range(n)] 
        self.max_n = n
        self.head = 0
        self.tail = 0
        self.size = 0
Добавим методы:
  • put() — добавляет элемент в очередь;
  • get() — извлекает элемент;
  • is_empty() — говорит о том, пуста ли очередь.
Скопировать кодPYTHON
def is_empty(self):
    return self.size == 0
  
def put(self, x):
    if self.size != self.max_n:
        self.queue[self.tail] = x
        self.tail = (self.tail + 1) % self.max_n
        self.size += 1
При добавлении элемента увеличиваем значение поля tail. Это значит, что при попытке добавить новый элемент, он запишется в следующую ячейку. Значение берётся по модулю max_n. Это делается для того, чтобы первая ячейка следовала за последней. Для наглядности можно представить, что массив зациклен.
Также при добавлении элемента размер очереди увеличивается на 1.
Скопировать кодPYTHON
def get(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
При извлечении удаляется добавленный ранее всех элемент. Значение поля head изменяется аналогично полю tail в методе push. Если мы удалили элемент на какой-то позиции i в массиве, то следующий раз нужно извлекать из ячейки i+1 по циклу.
Посмотрим на пример работы с получившейся очередью.
Скопировать кодPYTHON
q = Queue(3) 
q.put(1)
print(q.queue) # [1, None, None]
q.put(2)
print(q.queue) # [1, 2, None]
print(q.get()) # 1
q.put(3)
print(q.queue) # [None, 2, 3]
q.put(4)
print(q.queue) # [4, 2, 3]
print(q.get()) # 2
Из-за того, что не нужно снова выделять память, каждая операция выполняется за O(1).
Однако, у этой очереди есть существенный недостаток: ограничение на максимальный размер.
Конечно, при переполнении очереди можно расширять массив. Но это добавит сложности в реализации.
Также создать очередь можно при помощи связного списка. При добавлении элемента в очередь нужно вставить новый узел в хвост списка. В случае извлечения — удалить голову списка.
Вам предстоит реализовать такую очередь самостоятельно.
Какие вы видите недостатки очереди на списке в сравнении с очередью, реализованной при помощи массива? Выберите все верные ответы.
2 из 3 правильно и 1 неправильно
Есть и другие способы реализации очереди. Например, вам предстоит написать вариант на двух стеках.
Существует структура данных, которая объединяет в себе возможности стека и очереди, — дек. Это список элементов, в который добавить новые элементы и удалить существующие можно с обоих концов со сложностью О(1).
image
Дек можно воспринимать как двустороннюю очередь. В нём реализованы следующие методы:
Скопировать кодPYTHON
push_back - операция вставки нового элемента в конец
pop_back — операция удаления последнего элемента
push_front — операция вставки нового элемента в начало
pop_front — операция удаления первого элемента
is_empty — проверка на наличие элементов
Время решить задачи M, N, O, P, Q из контеста.