Работа с очередями

Структуры данных и алгоритмы на Python

Miriam Antona

Software Engineer

Очереди

FIFO: First-In First-Out
- Первый добавленный элемент удаляется первым

Очереди

FIFO: First-In First-Out
- Первый добавленный элемент удаляется первым

Очереди

FIFO: First-In First-Out
- Первый добавленный элемент удаляется первым

Очереди — структура

Схематичное изображение очереди с названиями блюд из разных кухонь мира.

Очереди — структура

Схематичное изображение очереди с названиями блюд. Слово "head" указывает на начало очереди.

Начало: head

Очереди — структура

Схематичное изображение очереди с названиями блюд. Слово "tail" указывает на конец очереди.

Начало: head
Конец: tail

Очереди — свойства

Схематичное изображение очереди с двумя элементами. Слово "head" указывает на начало, слово "tail" — на конец очереди.

Очереди — свойства

Схематичное изображение очереди. Новый элемент добавлен в конец очереди.

Добавление — только в конец
- Enqueue

Очереди — свойства

Схематичное изображение очереди. Первый элемент перечёркнут — он будет удалён.

Добавление — только в конец
- Enqueue
Удаление — только из головы

Очереди — свойства

Схематичное изображение очереди с двумя элементами: первый элемент был удалён.

Добавление — только в конец
- Enqueue
Удаление — только из головы
- Dequeue
Другие виды очередей:
- Двусторонние очереди
- Кольцевые очереди
- Очереди с приоритетом

Очереди — применение в реальном мире

Задания на печать в принтере
- Документы печатаются в порядке поступления
Приложения, где порядок запросов важен
- Продажа билетов на концерт
- Службы такси

Очереди — реализация

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Queue:
  def __init__(self):
    self.head = None
    self.tail = None

Очереди — enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Схематичное изображение очереди с одним элементом, реализованной в виде узла.

Очереди — enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

Схематичное изображение очереди с одним элементом. Слова "head" и "tail" указывают на узел.

Очереди — enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:

Схематичное изображение очереди с двумя элементами. Новый узел готов к добавлению.

Очереди — enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:
    self.tail.next = new_node

Схематичное изображение очереди с тремя элементами. Слово "tail" по-прежнему указывает на второй узел.

Очереди — enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:
    self.tail.next = new_node
    self.tail = new_node

Схематичное изображение очереди с тремя элементами. Слово "tail" указывает на последний добавленный узел.

Очереди — dequeue

Схематичное изображение очереди с тремя элементами. Слово "head" указывает на первый узел, слово "tail" — на последний.

def dequeue(self):

  if self.head:

Очереди — dequeue

Схематичное изображение очереди с тремя элементами. Слова "head" и "current_node" указывают на первый узел, слово "tail" — на последний.

def dequeue(self):
  if self.head:
    current_node = self.head

Очереди — dequeue

Схематичное изображение очереди с тремя элементами. Слово "head" указывает на первый узел, "current_node" — на второй, слово "tail" — на последний.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next

Очереди — dequeue

Схематичное изображение очереди с двумя элементами. Слово "head" указывает на первый узел, слово "tail" — на последний. Отдельный узел вне очереди помечен словом "current_node".

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None

Очереди — dequeue

Узел, на который указывают слова "current_node" и "tail". Слово "head" указывает на null.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None


    if self.head == None:

Очереди — dequeue

Узел, на который указывает слово "current_node". Слова "head" и "tail" указывают на null.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None

    if self.head == None:
      self.tail = None

SimpleQueue в Python

Модуль: queue
- Queue
- SimpleQueue

import queue


orders_queue = queue.SimpleQueue()


orders_queue.put("Sushi")
orders_queue.put("Lasagna")
orders_queue.put("Paella")


print("The size is: ", orders_queue.qsize())

The size is: 3

print(orders_queue.get())
print(orders_queue.get())
print(orders_queue.get())

Sushi
Lasagna
Paella

print("Empty queue: ", orders_queue.empty())

Empty queue: True

Давайте потренируемся!

Структуры данных и алгоритмы на Python