Queue

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.

Der Gegensatz zum FIFO-Verfahren ist das LIFO (Last In First Out)-Verfahren, auf dem der ADT Stack beruht.

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.

Queue Operationen

In der folgenden Tabelle werden Dir die wichtigsten Queue-Operationen und deren Zeitkomplexität näher gebracht.

Enqueue()

Dequeue()

isEmpty()

isFull()

peek()

Damit Du Dir das ganze noch besser vorstellen kannst, folgt ein Beispiel:

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ückt

Queue 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.

Eine häufige Implementierung erfolgt durch heaps.

In folgender Tabelle siehst Du die Operationen einer Priority Queue.

isEmpty()

insert_with_priority()

pull_highest_priority_element()

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.

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ügt

In folgender Tabelle siehst Du auch anderen Operationen, die für die deque verwendet werden.

append()

appendleft()

pop()

popleft()

insert(i, a)

index(ele, beg, end)

remove()

count()

reverse()