Werken met wachtrijen

Datastructuren en algoritmen in Python

Miriam Antona

Software Engineer

Wachtrijen

FIFO: First-In First-Out
- Het eerst ingevoegde item wordt als eerste verwijderd

Wachtrijen

FIFO: First-In First-Out
- Het eerst ingevoegde item wordt als eerste verwijderd

Wachtrijen

FIFO: First-In First-Out
- Het eerst ingevoegde item wordt als eerste verwijderd

Wachtrijen - structuur

Schematische weergave van een wachtrij met de namen van enkele internationale gerechten.

Wachtrijen - structuur

Schematische weergave van een wachtrij met de namen van enkele internationale gerechten. Het woord "head" wijst naar het begin van de rij.

Begin: head

Wachtrijen - structuur

Schematische weergave van een wachtrij met namen van internationale gerechten. Het woord "tail" wijst naar het einde van de rij.

Begin: head
Einde: tail

Wachtrijen - kenmerken

Schematische weergave van een wachtrij met de namen van twee internationale gerechten. Het woord "head" wijst naar het begin van de rij en het woord "tail" naar het einde.

Wachtrijen - kenmerken

Schematische weergave van een wachtrij. Een nieuw element is aan het einde van de rij ingevoegd.

Je kunt alleen aan het einde invoegen
- Enqueue

Wachtrijen - kenmerken

Schematische weergave van een wachtrij. Het eerste element is doorgestreept omdat het wordt verwijderd.

Je kunt alleen aan het einde invoegen
- Enqueue
Je kunt alleen aan het begin verwijderen

Wachtrijen - kenmerken

Schematische weergave van een wachtrij. De wachtrij heeft slechts twee elementen omdat het eerste is verwijderd.

Je kunt alleen aan het einde invoegen
- Enqueue
Je kunt alleen aan het begin verwijderen
- Dequeue
Andere soorten wachtrijen:
- Dubbelzijdige wachtrijen
- Circulaire wachtrijen
- Prioriteitswachtrijen

Wachtrijen - praktijkvoorbeelden

Printtaken in een printer
- Documenten worden geprint in de volgorde van binnenkomst
Toepassingen waar de volgorde van verzoeken telt
- Concertkaartjes
- Taxiservices

Wachtrijen - implementatie

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

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

Wachtrijen - enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Schematische weergave van een wachtrij met één element. De wachtrij is geïmplementeerd met een node.

Wachtrijen - enqueue

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

Schematische weergave van een wachtrij met één element. De wachtrij is geïmplementeerd met een node. De woorden "head" en "tail" wijzen naar de node.

Wachtrijen - enqueue

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

  else:

Schematische weergave van een wachtrij met twee elementen. De wachtrij is geïmplementeerd met nodes. Een nieuwe node staat klaar om ingevoegd te worden.

Wachtrijen - 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

Schematische weergave van een wachtrij met drie elementen. Het woord "tail" wijst nog naar de tweede node.

Wachtrijen - 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

Schematische weergave van een wachtrij met drie elementen. Het woord "tail" wijst naar de laatst ingevoegde node.

Wachtrijen - dequeue

Schematische weergave van een wachtrij met drie elementen. Het woord "head" wijst naar de eerste node en het woord "tail" naar de laatste node.

def dequeue(self):

  if self.head:

Wachtrijen - dequeue

Schematische weergave van een wachtrij met drie elementen. De woorden "head" en "current_node" wijzen naar de eerste node en het woord "tail" naar de laatste node.

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

Wachtrijen - dequeue

Schematische weergave van een wachtrij met drie elementen. Het woord "head" wijst naar de eerste node, het woord "current_node" naar de tweede, en het woord "tail" naar de laatste node.

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

Wachtrijen - dequeue

Schematische weergave van een wachtrij met twee elementen. Het woord "head" wijst naar de eerste node en het woord "tail" naar de laatste node. Er is nog een node buiten de wachtrij met het woord "current_node" dat ernaar wijst.

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

Wachtrijen - dequeue

Een node met de woorden "current_node" en "tail" die ernaar wijzen. Het woord "head" wijst naar null.

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


    if self.head == None:

Wachtrijen - dequeue

Een node met het woord "current_node" dat ernaar wijst. De woorden "head" en "tail" wijzen naar 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 in Python

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

Laten we oefenen!

Datastructuren en algoritmen in Python