Робота з чергами

Структури даних і алгоритми в 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