4.2 Queue

Eine Queue ist ein First-In First-Out Behälter. D.h. das Element, das als erstes Element in die Queue getan wurde, ist das erste Element, das wieder ausgelesen wird. Anschaulich betrachtet ist die Queue eine Schlange. Jedes Element, das eingefügt wird, wird hinten angehängt. Wenn ein Element aus der Queue gelesen wird, wird das vorderste Element gelesen.

Queues dienen z.B. dem Zwischenspeichern von Werten, die eine Hardware wie die Tastatur liefert. Diese Werte werden in der Reihenfolge verarbeitet, in der sie auch anfallen.

Um mit einer beliebigen Anzahl Elemente umzugehen, kann für die Queue eine einfach verkettete Liste benutzt werden. Ein neues Element wird immer am Listenende eingefügt. Gelesen wird immer das erste Element der Liste. Das Beispiel enthält im Unterschied zu der einfach verketteten Liste noch einen Zeiger auf das letzte Element, um dadurch das Einfügen in die Liste zu beschleunigen. Zusätzlich wird noch zwischen dem Lesen und dem Entfernen des ersten Elements unterschieden.

English version not yet available.