Queues

Eine Queue ist ein Container für Daten. Es gilt das first in - first out (FIFO) Verfahren. Die Daten, die als erstes in die Queue kommen, verlassen diese auch wieder als erstes. Das Einordnen in die Queue bezeichnet man als „Enqueue“, das Ausscheiden aus der Queue ist das „Dequeue“. Die Queue kann am besten mit einer Warteschlange im Supermarkt verglichen werden. Derjenige der zuerst zur Kassa kommt, verlässt diese auch wieder als erstes.

Aufbau einer Queue

Eine Queue ist ähnlich einer Liste aufgebaut. Es gibt ein erstes und letztes Element. Das Einfügen bzw. Entfernen von Elementen nennt man, wie oben schon erwähnt, „Enqueue“ und „Dequeue“

C - Implementierung

Eine Queue wird in C für gewöhnlich wie folgt implementiert:

struct Node 
{
  Node* next;
  Node* prev;
  struct Data value;
};
 
struct MyQueue 
{
  Node* head;
  Node* tail;
};


  • bool isEmpty()
    • Hier wird überprüft ob die angegebene Queue Elemente enthält, falls ja, wirt hier true zurückgeliefert
  • void pop()
    • Hier wird ein Dequeue durchgeführt. Es gibt auch die Möglichkeit, einen Boolean-Wert zurückzuliefern ob die Operation erfolgreich war. Je nach Implementierung besteht auch die Möglichkeit, den Wert des gelöschten Elements zu liefern.
  • void push(T value)
    • Mit dieser Funktion wird ein Enqueue durchgeführt. Hier besteht ebenfalls die Möglichkeit, sich einen Boolean-Wert zur Kontrolle zurückzuliefern lassen.

Eine komplett implementierte Queue für Integer findet man hier.

C++ Implementierung

template<class T>
class MyNode 
{
  public:
    MyNode<T>* next;
    MyNode<T>* prev;
    T value;
};
 
template <class T>
class MyQueue 
{
  public:
    MyNode<T>* head;
    MyNode<T>* tail;
};


Eine Queue in C++ wird für gewöhnlich wie folgt implementiert:

  • bool isEmpty()
    • Hier wird überprüft ob die angegebene Queue Elemente enthält, falls ja, wirt hier true zurückgeliefert
  • MyNode<T>* getHead()
    • Mit dieser Funktion wird eine Referenz auf den „Head“ der Queue zurückgeliefert. Das „T“ steht für ein Template (somit kann jeder beliebige Datentyp zurückgegeben werden).
  • MyNode<T>* getTail()
    • Das gleiche wie MyNode<T>* getHead() nur wird hier unser „Tail“ zurückgeliefert.
  • void pop()
    • Hier wird ein Dequeue durchgeführt. Es gibt auch die Möglichkeit, einen Boolean-Wert zurückzuliefern ob die Operation erfolgreich war. Je nach Implementierung besteht auch die Möglichkeit, den Wert des gelöschten Elements zu liefern.
  • void push(T& value)
    • Mit dieser Funktion wird ein Enqueue durchgeführt. Hier besteht ebenfalls die Möglichkeit, sich einen Boolean-Wert zur Kontrolle zurückzuliefern lassen.

Eine komplett implementierte Queue findet man hier.

Anwendung von Queues

Queues, wie der Name schon vermüten lässt, werden in der Programmierung als Warteschlangen verwendet. Ein Beispiel dafür wäre ein externes Gerät wie ein Fax oder Drucker. Wenn der Befehl zum Drucken gegeben wird und der Drucker ist zur Zeit nicht verfügbar, steht trotzdem „wird gedruckt“. Der Druckbefehl befindet sich ein einer Queue und wartet, bis der Drucker verfügbar ist um dann den Befehl auszuführen. Ein anderes Beispiel für eine Queue ist die Event-Queue. Sie verwaltet die Aktionen des Users wie zum Beispiel eine Mausbewegung oder ein Mausklick.

Priority Queue

Eine Priority Queue ist eine spezielle Form von Queue. Hier wird zu jedem Element nicht nur der Wert sondern auch die Priorität gespeichert. Zuerst werden alle Elemente mit der höchsten Priorität die Queue verlassen. Dann die Elemente mit der zweithöchsten Priorität usw. Zu beachten ist dabei, dass es egal ist wie viele andere Elemente in der Queue bereits vorhanden sind. Es wird zuerst immer nur auf die Priorität geachtet. Falls es mehrere Elemente mit der gleichen Priorität gibt, wird das FIFO Verfahren angewandt. Jenes Element, welches weiter vorne steht, verlässt die Queue als erstes.

Double Ended Queue (Deque)

Die Double Ended Queue unterscheidet sich nur in einem Punkt von der normalen Queue. Bei ihr kann man nämlich sowohl am Anfang, als auch am Ende der Queue, Elemente löschen bzw. einfügen.

Buffer Queue

Eine Buffer Queue ist eine ringförmige Queue. (Anfang = Ende)

Funktionsweise

Bei einer Buffer Queue wird irgendwo zu schreiben begonnen. Von dort weg werden dann immer wieder Werte in den Buffer geschrieben. Beim Löschen der Daten, werden immer zuerst die ältesten Daten gelöscht. Falls der Buffer voll ist, werden einfach die ältesten Daten überschrieben.

Ähnliche Strukturen wie Queues

Pipes

Mit Pipes (Pipelines) wird die Abarbeitung von Befehlen in kleine Teilaufgaben zerlegt, sodass parallel mehrere Anweisungen durchgeführt werden können.

Stacks

Stacks sind das Gegenteil von Queues, sie praktizieren ein first-in, last-out Verfahren (FILO). Dabei, wie der Name schon vermuten lässt, wird das zuletzt eingefügte Element, als erstes wieder entfernt.