Arbeiten mit Queues

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software Engineer

Queues

FIFO: First-In First-Out
- Das zuerst eingefügte Element wird zuerst entfernt

Queues

FIFO: First-In First-Out
- Das zuerst eingefügte Element wird zuerst entfernt

Queues

FIFO: First-In First-Out
- Das zuerst eingefügte Element wird zuerst entfernt

Queues – Struktur

Schematische Darstellung einer Queue mit den Namen internationaler Gerichte.

Queues – Struktur

Schematische Darstellung einer Queue mit den Namen internationaler Gerichte. Das Wort „head“ zeigt auf den Anfang der Queue.

Anfang: head

Queues – Struktur

Schematische Darstellung einer Queue mit den Namen internationaler Gerichte. Das Wort „tail“ zeigt auf das Ende der Queue.

Anfang: head
Ende: tail

Queues – Merkmale

Schematische Darstellung einer Queue mit den Namen zweier internationaler Gerichte. Das Wort „head“ zeigt auf den Anfang der Queue und „tail“ auf das Ende.

Queues – Merkmale

Schematische Darstellung einer Queue. Ein neues Element wurde am Ende (tail) eingefügt.

Einfügen nur am Ende
- Enqueue

Queues – Merkmale

Schematische Darstellung einer Queue. Das erste Element ist durchgestrichen, da es entfernt wird.

Einfügen nur am Ende
- Enqueue
Entfernen nur am Anfang

Queues – Merkmale

Schematische Darstellung einer Queue. Die Queue hat nur zwei Elemente, da das erste entfernt wurde.

Einfügen nur am Ende
- Enqueue
Entfernen nur am Anfang
- Dequeue
Weitere Queue-Typen:
- Doppelt beendete Queues
- Ring-Queues
- Prioritäts-Queues

Queues – Praxisbeispiele

Druckaufträge bei einem Drucker
- Dokumente werden in Eingangsreihenfolge gedruckt
Anwendungen, bei denen die Reihenfolge der Anfragen zählt
- Konzerttickets
- Taxi-Dienste

Queues – Implementierung

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

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

Queues – Enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Schematische Darstellung einer Queue mit einem Element. Die Queue wurde mit einem Node implementiert.

Queues – Enqueue

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

Schematische Darstellung einer Queue mit einem Element. Die Queue wurde mit einem Node implementiert. Die Wörter „head“ und „tail“ zeigen auf den Node.

Queues – Enqueue

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

  else:

Schematische Darstellung einer Queue mit zwei Elementen. Die Queue wurde mit Nodes implementiert. Ein neuer Node wird zum Einfügen vorbereitet.

Queues – 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 Darstellung einer Queue mit drei Elementen. Das Wort „tail“ zeigt noch auf den zweiten Node.

Queues – 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 Darstellung einer Queue mit drei Elementen. Das Wort „tail“ zeigt auf den zuletzt eingefügten Node.

Queues – Dequeue

Schematische Darstellung einer Queue mit drei Elementen. „head“ zeigt auf den ersten Node und „tail“ auf den letzten.

def dequeue(self):

  if self.head:

Queues – Dequeue

Schematische Darstellung einer Queue mit drei Elementen. Die Wörter „head“ und „current_node“ zeigen auf den ersten Node und „tail“ auf den letzten.

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

Queues – Dequeue

Schematische Darstellung einer Queue mit drei Elementen. „head“ zeigt auf den ersten Node, „current_node“ auf den zweiten, und „tail“ auf den letzten.

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

Queues – Dequeue

Schematische Darstellung einer Queue mit zwei Elementen. „head“ zeigt auf den ersten Node und „tail“ auf den letzten. Ein weiterer Node außerhalb der Queue ist mit „current_node“ markiert.

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

Queues – Dequeue

Ein Node mit den Markierungen „current_node“ und „tail“. „head“ zeigt auf null.

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


    if self.head == None:

Queues – Dequeue

Ein Node mit der Markierung „current_node“. „head“ und „tail“ zeigen auf 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

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

Lass uns üben!

Datenstrukturen und Algorithmen in Python