Hast Du Dich schon mal gefragt, wieso Du bei einem Anruf beim Internetanbieter so lange in der Warteschlange sitzen musst? Und weißt Du, in was für einer Reihenfolge Deine Anliegen bearbeitet werden? In einer Warteschlange wird nach dem FIFO-Prinzip gehandelt. Das heißt, wer zuerst kommt, kommt auch als Erster dran.
Queue Bedeutung
Unter der Bedeutung von Queue in der Informatik versteht man einen abstrakten Datentyp, der als Puffer für die Zwischenspeicherung von Objekten in einer bestimmten Reihenfolge verwendet wird.
Queues sind spezielle Listen, in denen Elemente an einem Ende eingefügt und nur an einem anderen Ende entnommen werden. Die Warteschlange ist der deutsche Begriff.
Ein abstrakter Datentyp, auch ADT genannt, bezeichnet eine oder mehrere Mengen von Objekten und den darauf definierten Operationen.
FIFO-Verfahren
Das FIFO-Verfahren steht für First In First Out-Verfahren und bezeichnet in der Informatik eine bestimmte Reihenfolge, in der Daten, die am längsten warten, zuerst bearbeitet bzw. ausgelesen werden.
Das Prinzip von FIFO wird auch in anderen Bereichen der Informatik verwendet. Datenmengen, die nach dem FIFO-Prinzip arbeiten, werden im Bereich der Betriebssysteme auch Pipes genannt. In der praktischen Informatik kommt FIFO vor allem bei Controllern zum Einsatz.
Der Gegensatz zum FIFO-Verfahren ist das LIFO (Last In First Out)-Verfahren, auf dem der ADT Stack beruht.
Mehr zu Stacks und dem LIFO-Verfahren findest Du in einer eigenständigen Erklärung auf StudySmarter!
Queue – Informatik
Die Queue ist ein wichtiger Bestandteil der Informatik. In den nächsten Abschnitten folgen die Anwendungsbereiche der Queue inklusive den Operationen.
Anwendung
Das Konzept der Queue wird auch in verschiedenen Bereichen außerhalb der Informatik angewendet. Druckaufträge, Telefon-Wartezeiten und das Vergeben von Kindergartenplätzen erfolgen nach dem FIFO-Prinzip und entsprechend der Warteschlange/Queue. In der Informatik wird die Queue vor allem bei Middleware-Lösungen benutzt. Zudem bildet es auch die Grundlage für verschiedenste Algorithmen, wie der Breitensuche.
Du findest eine eigenständige Erklärung zu der Breitensuche auf StudySmarter!
Queue Operationen
In der folgenden Tabelle werden Dir die wichtigsten Queue-Operationen und deren Zeitkomplexität näher gebracht.
Unter der Zeitkomplexität versteht man in der Informatik die optimale Anzahl an Rechenschritten, die ein Algorithmus zur Ausführung und Lösen eines Problems benötigt. Dargestellt wird dies anhand der O-Notation, die Du auch in der unten stehenden Tabelle wiederfindest. Eigenständige Erklärungen dazu gibt es auf StudySmarter!
| Operation | Beschreibung | Zeitkomplexität |
Enqueue() | Einfügen eines Elements am Ende der Schlange. Eine andere Bezeichnung, die dafür verwendet wird, ist pushtail(). | O (1) |
Dequeue() | Entnehmen eines Elements am Kopf der Schlange. Eine andere Bezeichnung, die dafür verwendet wird, ist pophead(). | O (1) |
isEmpty() | Überprüft, ob die Schlange leer ist und gibt einen booleschen Wert zurück. | O (1) |
isFull() | Überprüft, ob die Schlange voll ist und gibt einen booleschen Wert zurück. | O (1) |
peek() | Gibt das Element am Kopf der Schlange wieder, ohne diesen zu entfernen. | O (1) |
Damit Du Dir das ganze noch besser vorstellen kannst, folgt ein Beispiel:
In Abb. 1 siehst Du eine Queue, die verschiedene Zahlenelemente enthält.
Anhand der Operation Dequeue() wurde das Element 2 am Kopf der Schlange entfernt, da die 2 als allererstes eingefügt worden ist. Das Element 1 wird anhand der Enqueue() Operation am Ende eingefügt und würde somit auch als allerletztes bearbeitet werden. Wenn Du jetzt das oberste Element der Queue sehen möchtest, müsstest Du die Operation peek() verwenden. Dies würde Dir dann die Zahl 5 zeigen.
Du kannst als Übung auch eine Queue mithilfe einer anderen ADT, wie Stacks implementieren:
Dazu müssen die Operationen von Stack geschickt angewendet werden. Die Idee ist, einen Stack (q.s1) nur für das Einfügen, den anderen für das Entfernen (q.s2) der Elemente zu verwenden. Die Elemente werden anhand der Stack Operation pop() ausgegeben und auf q.s2 gedrückt. Im Folgenden siehst Du, wie es im Pseudocode aussieht.
Stack q.s1, q.s2 // zwei Stacks innerhalb einer Queue mit n Elementen
If ( isEmpty(q.s1) and isEmpty(q.s2) then {
return TRUE
} // Zuerst wird überprüft, ob die beiden Stacks leer sind
dequeue(q) {
else {
return FALSE
else {
if (isEmpty(q.s2)) then {
while NOT isEmpty(q.s1) do
push(pop(q.s2), q.s1)
}
return(pop(q.s2))
}
}
}
// solange q.s2 nicht leer ist, wird immer das oberste Element von s1 entnommen und in s2 gedrücktQueue Programmieren
Eine Queue zu programmieren, kann auf unterschiedlicher Weise und in verschiedenen Sprachen erfolgen. In Java und C/++ wird dies in der Regel mithilfe von Arrays getan. Im folgenden Abschnitt wirst Du eine Python-Implementierung sehen, die auf einer Liste beruht.
Queue – Python
Wie wird also die Queue in Python programmiert? Am einfachsten wäre es die Deque Operationen zu benutzen. Dazu wirst Du aber später mehr erfahren. Eine weitere Möglichkeit wäre wie bereits erwähnt die Verwendung von Listen. Wichtig ist die Einhaltung des FIFO-Prinzips!
Folgend siehst Du ein Codebeispiel.
class Queue:
def __init__(self):
self.items = [ ]
#es folgt die Implementierung der wichtigsten Operationen
def isEmpty(self):
return self.items == [ ]
def enqueue(self, item):
self.items.insert(0,item) def dequeue(self):
if not self.isEmpty():
return self.items.pop()
else:
return None
def size(self):
return len(self.items)
def display(self): #Anzeigen der Queue
print(self.items)
#Erzeugen einer Klasseninstanz für die Queue. Danach kannst Du die Operationen selbst ausprobieren!
q = Queue()
q.enqueue(1)
q.enqueue('name')
q.enqueue(True)
q.enqueue(4)
q.dequeue()
q.display()Verwandte Datenstrukturen
Datenstrukturen, die der Queue ähneln, gibt es viele. Die Queue an sich ist ja schließlich wieder eine etwas spezielle Liste. In den nächsten Abschnitten werden Dir die zwei wichtigsten verwandten Datenstrukturen näher gebracht!
Priority Queue
Die Priority Queue ist eine weiterer ADT, die der regulären Queue ähnelt. Allerdings geschieht das Einfügen nicht am Ende, sondern unter Beachtung einer speziellen Sortierreihenfolge (Priorität der Bearbeitung). Die Elemente können als Attribut im Verbund gespeichert werden.
Als reelles Beispiel kannst Du Dir die Notfallklinik Warteschlange vorstellen. Patienten und Patientinnen in Lebensgefahr wird selbstverständlich eine höhere Priorität gegenüber solchen mit nicht so dringenden Problemen gegeben und sie werden eher behandelt.
Eine häufige Implementierung erfolgt durch heaps.
In folgender Tabelle siehst Du die Operationen einer Priority Queue.
| Operation | Erklärung |
isEmpty() | Überprüft, ob die Schlange leer ist und gibt einen booleschen Wert zurück. |
insert_with_priority() | Einfügen eines Elements mit einer spezifischen Priorität. |
pull_highest_priority_element() | Entfernt das Element mit der höchsten Priorität und gibt es wieder. |
Wie bereits erwähnt, wird die Priority Queue häufig anhand von heaps implementiert. Daher erhält sie für das Einfügen und Entfernen eines Elements, eine Laufzeit von O(log n) und O(n) für die Bildung des heaps aus n Datensätzen.
Deque
Deque steht für "Double-Ended-Queue" und ist eine weitere Datenstruktur, die der Queue ähnelt. Ganz konkret besteht sie aus einer Liste, wobei Elemente sowohl vorn als auch hinten eingefügt werden können. Zudem kann sie als Queue und Stack eingesetzt werden. Je nach Bedarf kann es sich also, nachdem FIFO- oder LIFO-Prinzip richten. Dabei bist Du allerdings nicht auf eines beschränkt und kannst die Elemente an einer beliebigen Stelle einfügen!
In Python wird die Deque über das Modul "collections" implementiert und ist in der Regel effizienter als eine reguläre Liste, da hier die Operationen, analog zur Queue, jeweils nur eine Zeitkomplexität von O(1) besitzen.
Natürlich kannst Du die Deque auch als eine Liste definieren. Hier musst Du aber bedenken, dass die Komplexität auf O(n) steigen kann. Mehr zur Komplexität und den O-Notionen kannst Du ebenfalls auf StudySmarter nachlesen!
Sicherlich möchtest Du wissen, wie das Deque Modul verwendet wird und es auch bestimmt selbst ausprobieren. Folgend werden Dir die wichtigsten Funktionen näher gebracht:
from collections import deque # zunächst musst Du Dir Zugriff auf das Modul verschaffen
q = deque([ 'name' , 14, ' alter', 'adresse' ])
print (q) //Deine deque wird initialisiert und ausgegeben
#Anhand dieser Operation kannst Du ein Element am Ende der Liste einfügen
q.append('HausNr')
#Einfügen am Anfang der Liste
q.appendleft(4)
print("Die deque nach dem Einfügen am Anfang und Ende ist : " , q)
#Du kannst Elemente genau wie bei einer Liste auch an einer bestimmten Position einfügen
q.insert(2, 3) //An Position 2 wird die Zahl 3 eingefügtIn folgender Tabelle siehst Du auch anderen Operationen, die für die deque verwendet werden.
| Operationen | Erklärung |
append() | Einfügen eines Elements am Ende der deque |
appendleft() | Einfügen am Anfang der deque |
pop() | Löschen eines Elements am Ende der deque |
popleft() | Löschen eines Elements am Anfang der deque |
insert(i, a) | Einfügen eines Elements an einer bestimmten Position (i) |
index(ele, beg, end) | Gibt die Position wieder, wo das Element (ele) als Erstes gefunden wird, vom Anfang (beg) bis zum End-index (end) |
remove() | Entfernt das gegebene Element, an der ersten Position, wo es auftaucht |
count() | Zählt wie oft das gegebene Element auftaucht |
reverse() | Kehrt die Reihenfolge der Elemente um |
Queue - Das Wichtigste
- Queue Bedeutung: Die Queue in der Informatik ist ein abstrakter Datentyp, der die Grundlage für verschiedene Algorithmen, wie die Breitensuche bildet.
- Eine Queue richtet sich nach dem First In First Out (kurz: FIFO) Prinzip.
- Elemente werden, wie bei einer Warteschlange, an einem Ende eingefügt und am anderen Ende entnommen.
- Verwandte Datenstrukturen sind die Priority-Queue und die Deque.
- Eine Queue zu programmieren, kann je nach Sprache unterschiedlich erfolgen. In java und C/++ werden öfter Arrays benutzt.
- Eine Queue Python Implementierung erfolgt in der Regel anhand von Listen oder durch Implementieren einer Deque mithilfe des Moduls collections.
Nachweise
- H. Knebl (2021). Algorithmen und Datenstrukturen. Springer.
- runestone.academy: Implementing a Queue in Python. (18.10.2022)
- Geeksforgeeks.org: Deque in Python. (18.10.2022)
Erklärungen 
Magazine 
