Это сообщение было впервые опубликовано в моем блоге: Структура данных очереди

Структура данных очереди - это набор элементов, соответствующих принципу first-in first out. Первый добавленный элемент будет первым элементом, который будет удален из очереди. Итак, элементы добавляются сзади и удаляются спереди.

В качестве аналогии можно привести простую очередь людей, ожидающих следующего поезда. В контексте разработки программного обеспечения примером является веб-сервер, получающий и отвечающий на запросы.

Основными методами API являются enqueue (добавить) и dequeue (удалить). Но мы также можем добавить другие методы как часть реализации API: size, front, back и is_empty.

Реализация очереди

Мы можем создать класс Queue в качестве оболочки и использовать список Python для хранения данных очереди. Этот класс будет иметь реализацию методов enqueue, dequeue, size, front, back и is_empty.

Первый шаг - создать определение класса и то, как мы ушли хранить наши предметы.

class Queue:
    def __init__(self):
        self.items = []

Это в основном то, что нам нужно сейчас. Просто класс и его конструктор. Когда экземпляр будет создан, у него будет items список для хранения элементов очереди.

Для метода enqueue нам просто нужно использовать метод list append для добавления новых элементов. Новые элементы будут помещены в последний индекс этого itemslist. Таким образом, первый элемент в очереди всегда будет первым.

def enqueue(self, item):
    self.items.append(item)

Он получает новый элемент и добавляет его в список.

Метод size подсчитывает количество элементов очереди только с помощью функции len.

def size(self):
    return len(self.items)

Идея метода is_empty состоит в том, чтобы проверить, есть ли в списке элементы или нет. Если есть, возвращает False. В противном случае True. Чтобы подсчитать количество элементов в очереди, мы можем просто использовать уже реализованный метод size.

def is_empty(self):
    return self.size() == 0

Метод pop из структуры данных списка также может использоваться для удаления элемента из очереди. Он удаляет первый элемент из очереди, как и ожидалось для очереди. Первый добавленный элемент.

def dequeue(self):
    return self.items.pop(0)

Но нам нужно справиться с пустотой очереди. Для пустого списка метод pop вызывает исключение IndexError: poop from empty list. Таким образом, мы можем создать класс исключения для решения этой проблемы.

class Emptiness(Exception):
    pass

И использует его, когда список пуст:

def dequeue(self):
    if self.is_empty():
        raise Emptiness('The Queue is empty')
    return self.items.pop(0)

Если он пуст, мы возбуждаем это исключение. В противном случае мы можем исключить передний элемент из очереди.

Мы используем ту же стратегию пустоты для метода front:

def front(self):
    if self.is_empty():
        raise Emptiness('The Queue is empty')
    return self.items[0]

Если в нем есть хотя бы один элемент, мы получаем передний, первый добавленный элемент в очереди.

Также такая же стратегия пустоты для метода back:

def back(self):
    if self.is_empty():
        raise Emptiness('The Queue is empty')
    return self.items[-1]

Если у него есть хотя бы один элемент, мы получаем последний элемент, добавленный последним в очереди.

Использование очереди

Я создал несколько вспомогательных функций, чтобы помочь проверить использование очереди.

def test_enqueue(queue, item):
    queue.enqueue(item)
    print(queue.items)

def test_dequeue(queue):
    queue.dequeue()
    print(queue.items)

def test_emptiness(queue):
    is_empty = queue.is_empty()
    print(is_empty)

def test_size(queue):
    size = queue.size()
    print(size)

def test_front(queue):
    front = queue.front()
    print(front)

def test_back(queue):
    back = queue.back()
    print(back)

По сути, они вызывают метод очереди и выводят ожидаемый результат от вызова метода.

Использование будет примерно таким:

queue = Queue()
test_emptiness(queue)  # True
test_size(queue)  # 0
test_enqueue(queue, 1)  # [1]
test_enqueue(queue, 2)  # [1, 2]
test_enqueue(queue, 3)  # [1, 2, 3]
test_enqueue(queue, 4)  # [1, 2, 3, 4]
test_enqueue(queue, 5)  # [1, 2, 3, 4, 5]
test_emptiness(queue)  # False
test_size(queue)  # 5
test_front(queue)  # 1
test_back(queue)  # 5
test_dequeue(queue)  # [2, 3, 4, 5]
test_dequeue(queue)  # [3, 4, 5]
test_dequeue(queue)  # [4, 5]
test_dequeue(queue)  # [5]
test_emptiness(queue)  # False
test_size(queue)  # 1
test_front(queue)  # 5
test_back(queue)  # 5
test_dequeue(queue)  # []
test_emptiness(queue)  # True
test_size(queue)  # 0

Сначала мы создаем новую очередь из класса Queue.

  • Итак, теперь мы можем убедиться в его пустоте: да, это так!
  • Проверить размер: 0.
  • Поставить в очередь 5 новых элементов: [1, 2, 3, 4, 5].
  • Проверить пустоту еще раз: больше нет!
  • Проверить размер: 5.
  • Получите передний элемент: 1, потому что это был первый добавленный элемент.
  • Получите задний элемент: 5, потому что это был последний добавленный элемент.
  • Удалите из очереди 4 элемента: 1, 2, 3 и 4.
  • Проверьте пустоту: она еще не пуста!
  • Размер 1, а сзади и спереди одинаковое число: 5.
  • Удалите оставшийся элемент из очереди.
  • Проверьте пустоту: теперь она пуста!
  • Размер вернулся к 0.

Другой способ проверить это

Поставить в очередь 5 новых предметов:

queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)

Пройдитесь по элементам и распечатайте каждый из них.

for item in queue.items:
    print(item)

Проверьте переднюю и заднюю части.

test_front(queue)
test_back(queue)

Убрать все из очереди.

queue.dequeue()
test_front(queue)

Размер теста.

test_size(queue) # *0*

Сложности времени выполнения и пространства

Теперь о сложностях пространства и времени выполнения для каждого реализованного метода.

Пространство довольно простое. Это список, поэтому это O(n), где n - текущее количество элементов в стеке.

Время выполнения для каждого метода O(1), постоянное время.

Ресурсы