Práce s frontami

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software Engineer

Fronty

FIFO: First-In First-Out
- První vložený prvek je první odebraný

Fronty

FIFO: First-In First-Out
- První vložený prvek je první odebraný

Fronty

FIFO: First-In First-Out
- První vložený prvek je první odebraný

Fronty – struktura

Schematické znázornění fronty s názvy mezinárodních jídel.

Fronty – struktura

Schematické znázornění fronty s názvy mezinárodních jídel. Slovo „head" ukazuje na začátek fronty.

Začátek: head

Fronty – struktura

Schematické znázornění fronty s názvy mezinárodních jídel. Slovo „tail" ukazuje na konec fronty.

Začátek: head
Konec: tail

Fronty – vlastnosti

Schematické znázornění fronty s názvy dvou mezinárodních jídel. Slovo „head" ukazuje na začátek fronty a slovo „tail" na konec.

Fronty – vlastnosti

Schematické znázornění fronty. Nový prvek byl vložen na konec fronty.

Vkládání pouze na konec
- Enqueue

Fronty – vlastnosti

Schematické znázornění fronty. První prvek je přeškrtnut, protože bude odebrán.

Vkládání pouze na konec
- Enqueue
Odebírání pouze ze začátku

Fronty – vlastnosti

Schematické znázornění fronty. Fronta má jen dva prvky, protože první byl odebrán.

Vkládání pouze na konec
- Enqueue
Odebírání pouze ze začátku
- Dequeue
Další typy front:
- Oboustranné fronty
- Kruhové fronty
- Prioritní fronty

Fronty – využití v praxi

Tiskové úlohy v tiskárně
- Dokumenty se tisknou v pořadí, v jakém byly přijaty
Aplikace, kde záleží na pořadí požadavků
- Lístky na koncert
- Taxislužby

Fronty – implementace

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

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

Fronty – enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Schematické znázornění fronty s jedním prvkem. Fronta je implementována pomocí uzlu.

Fronty – enqueue

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

Schematické znázornění fronty s jedním prvkem. Fronta je implementována pomocí uzlu. Slova „head" a „tail" ukazují na uzel.

Fronty – enqueue

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

  else:

Schematické znázornění fronty se dvěma prvky. Fronta je implementována pomocí uzlů. Nový uzel je připraven k vložení.

Fronty – 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

Schematické znázornění fronty se třemi prvky. Slovo „tail" stále ukazuje na druhý uzel.

Fronty – 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

Schematické znázornění fronty se třemi prvky. Slovo „tail" ukazuje na naposledy vložený uzel.

Fronty – dequeue

Schematické znázornění fronty se třemi prvky. Slovo „head" ukazuje na první uzel a slovo „tail" na poslední uzel.

def dequeue(self):

  if self.head:

Fronty – dequeue

Schematické znázornění fronty se třemi prvky. Slova „head" a „current_node" ukazují na první uzel a slovo „tail" na poslední uzel.

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

Fronty – dequeue

Schematické znázornění fronty se třemi prvky. Slovo „head" ukazuje na první uzel, slovo „current_node" na druhý uzel a slovo „tail" na poslední uzel.

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

Fronty – dequeue

Schematické znázornění fronty se dvěma prvky. Slovo „head" ukazuje na první uzel a slovo „tail" na poslední uzel. Mimo frontu je další uzel, na který ukazuje slovo „current_node".

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

Fronty – dequeue

Uzel, na který ukazují slova „current_node" a „tail". Slovo „head" ukazuje na null.

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


    if self.head == None:

Fronty – dequeue

Uzel, na který ukazuje slovo „current_node". Slova „head" a „tail" ukazují na 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 v Pythonu

Modul: 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

Let's practice!

Datové struktury a algoritmy v Pythonu