Flbkwikiadmin am 4. September 2026 um 07:26 Uhr

2026-09-04T07:26:10Z

← Nächstältere Version		Version vom 4. September 2026, 09:26 Uhr
Zeile 113:		Zeile 113:

	== Laufzeitanalyse (Komplexität) ==		== Laufzeitanalyse (Komplexität) ==
	Warteschlangen lassen sich in der Praxis äußerst effizient über Arrays mit Ringpuffer-Logik oder über einfach verkettete Listen implementieren. Eine Zeigerstruktur, die stets den Anfang (Front) und das Ende (Tail) speichert, garantiert hochperformante Speicher- und Lesezugriffe. Für die oben genannten Methoden ergibt sich gemäß der [[~~Landau~~-~~Symbole~~\|~~Landau~~-Notation]] folgende Laufzeitkomplexität:		Warteschlangen lassen sich in der Praxis äußerst effizient über Arrays mit Ringpuffer-Logik oder über einfach verkettete Listen implementieren. Eine Zeigerstruktur, die stets den Anfang (Front) und das Ende (Tail) speichert, garantiert hochperformante Speicher- und Lesezugriffe. Für die oben genannten Methoden ergibt sich gemäß der [[O-Notation\|O-Notation]] folgende Laufzeitkomplexität:

	{\| class="wikitable"		{\| class="wikitable"

Flbkwikiadmin: Die Seite wurde neu angelegt: „== Einführung == In der Informatik bezeichnet eine '''Warteschlange''' oder '''Schlange''' (englisch ''Queue'') eine grundlegende und häufig eingesetzte dynamische Datenstruktur. Sie dient der geordneten Zwischenspeicherung von Datenobjekten, bevor diese systematisch weiterverarbeitet werden. Warteschlangen verwalten beliebige Objekte nach dem strengen '''FIFO-Prinzip''' (''First-In-First-Out''). Das bedeutet: Das Element, welches zuerst in die Datens…“

2026-09-04T07:25:32Z

Die Seite wurde neu angelegt: „== Einführung == In der Informatik bezeichnet eine '''Warteschlange''' oder '''Schlange''' (englisch ''Queue'') eine grundlegende und häufig eingesetzte dynamische Datenstruktur. Sie dient der geordneten Zwischenspeicherung von Datenobjekten, bevor diese systematisch weiterverarbeitet werden. Warteschlangen verwalten beliebige Objekte nach dem strengen '''FIFO-Prinzip''' (''First-In-First-Out''). Das bedeutet: Das Element, welches zuerst in die Datens…“

Neue Seite

== Einführung ==
In der Informatik bezeichnet eine '''Warteschlange''' oder '''Schlange''' (englisch ''Queue'') eine grundlegende und häufig eingesetzte dynamische Datenstruktur. Sie dient der geordneten Zwischenspeicherung von Datenobjekten, bevor diese systematisch weiterverarbeitet werden.

Warteschlangen verwalten beliebige Objekte nach dem strengen '''FIFO-Prinzip''' (''First-In-First-Out''). Das bedeutet: Das Element, welches zuerst in die Datenstruktur eingefügt wurde, wird auch als erstes wieder entnommen.

'''Alltagsanalogie:'''
Man kann sich diese Datenstruktur wie eine Warteschlange von Kunden an einer Supermarktkasse vorstellen. Der Letzte, der sich in die Schlange stellt, wird am Kopfende (''Back'') als Letzter bedient. Umgekehrt wird derjenige, der sich als Erstes an die Spitze (''Front'') angestellt hat, als Erster bedient.

== Funktionsweise und Visualisierung ==
Die grundlegenden Operationen einer Warteschlange verändern ihren Zustand, indem Elemente eingefügt oder entnommen werden. In der Abbildung unten ist die Funktionsweise schematisch dargestellt:

* Mit <code>enter</code> (bzw. <code>enqueue</code>) wird ein neuer Wert (im Beispiel die Zahl <code>3</code>) am Ende der Schlange (''Back'') hinzugefügt.
* Mit <code>leave</code> (bzw. <code>dequeue</code>) wird das am längsten gespeicherte Element (im Beispiel <code>37</code>) an der Spitze der Schlange (''Front'') herausgenommen.
* Der einzige lesende Zugriff erfolgt über die Operation <code>front</code>. Diese liefert das erste gespeicherte Element der Queue (hier <code>37</code>), unter der Annahme, dass die entnehmende Operation noch nicht ausgeführt wurde.

<html>
<svg width="600" height="200" viewBox="0 0 600 200" xmlns="http://www.w3.org/2000/svg" style="background-color: transparent;">

<g transform="translate(150, 80)">
<rect x="0" y="0" width="40" height="40" fill="#ffffff" stroke="#000000" stroke-width="3"/>
<text x="20" y="25" text-anchor="middle" font-family="Arial" font-weight="bold" font-size="16">2</text>
<rect x="40" y="0" width="40" height="40" fill="#ffffff" stroke="#000000" stroke-width="3"/>
<text x="60" y="25" text-anchor="middle" font-family="Arial" font-weight="bold" font-size="16">4</text>
<rect x="80" y="0" width="40" height="40" fill="#ffffff" stroke="#000000" stroke-width="3"/>
<text x="100" y="25" text-anchor="middle" font-family="Arial" font-weight="bold" font-size="16">7</text>
<rect x="120" y="0" width="40" height="40" fill="#ffffff" stroke="#000000" stroke-width="3"/>
<text x="140" y="25" text-anchor="middle" font-family="Arial" font-weight="bold" font-size="16">9</text>
<rect x="160" y="0" width="40" height="40" fill="#ffffff" stroke="#000000" stroke-width="3"/>
<text x="180" y="25" text-anchor="middle" font-family="Arial" font-weight="bold" font-size="16">12</text>
<rect x="200" y="0" width="40" height="40" fill="#ffffff" stroke="#000000" stroke-width="3"/>
<text x="220" y="25" text-anchor="middle" font-family="Arial" font-weight="bold" font-size="16">21</text>
<rect x="240" y="0" width="40" height="40" fill="#ffffff" stroke="#000000" stroke-width="3"/>
<text x="260" y="25" text-anchor="middle" font-family="Arial" font-weight="bold" font-size="16">26</text>
<rect x="280" y="0" width="40" height="40" fill="#ffffff" stroke="#000000" stroke-width="3"/>
<text x="300" y="25" text-anchor="middle" font-family="Arial" font-weight="bold" font-size="16">31</text>
<rect x="320" y="0" width="40" height="40" fill="#ffffff" stroke="#000000" stroke-width="3"/>
<text x="340" y="25" text-anchor="middle" font-family="Arial" font-weight="bold" font-size="16">37</text>
</g>

<g transform="translate(40, 20)">
<rect x="0" y="0" width="40" height="40" fill="#ffffff" stroke="#000000" stroke-width="3"/>
<text x="20" y="25" text-anchor="middle" font-family="Arial" font-weight="bold" font-size="16">3</text>
</g>
<path d="M 60 60 Q 60 100 130 100" fill="none" stroke="#8b0000" stroke-width="8" marker-end="url(#arrow-red)"/>
<text x="50" y="105" fill="#8b0000" font-family="Arial" font-size="14" font-weight="bold">enter</text>

<g transform="translate(520, 20)">
<rect x="0" y="0" width="40" height="40" fill="#ffffff" stroke="#000000" stroke-width="3"/>
<text x="20" y="25" text-anchor="middle" font-family="Arial" font-weight="bold" font-size="16">37</text>
</g>
<path d="M 470 80 Q 470 40 505 40" fill="none" stroke="#8b0000" stroke-width="8" marker-end="url(#arrow-red)"/>
<text x="440" y="55" fill="#8b0000" font-family="Arial" font-size="14" font-weight="bold">leave</text>

<path d="M 490 180 L 490 135" fill="none" stroke="#006400" stroke-width="4" marker-end="url(#arrow-green)"/>
<text x="500" y="165" fill="#006400" font-family="Arial" font-size="14" font-weight="bold">front</text>
<defs>
<marker id="arrow-red" viewBox="0 0 10 10" refX="5" refY="5" markerWidth="6" markerHeight="6" orient="auto">
<path d="M 0 0 L 10 5 L 0 10 z" fill="#8b0000"/>
</marker>
<marker id="arrow-green" viewBox="0 0 10 10" refX="5" refY="5" markerWidth="6" markerHeight="6" orient="auto">
<path d="M 0 0 L 10 5 L 0 10 z" fill="#006400"/>
</marker>
</defs>
</svg>
</html>

Auch vertikal lässt sich das Konzept einer Queue anhand von Elementblöcken veranschaulichen. Hierbei rücken die Elemente wie auf einem Fließband weiter:

<html>
<svg width="500" height="200" viewBox="0 0 500 200" xmlns="http://www.w3.org/2000/svg" style="background-color: transparent;">

<g transform="translate(180, 80)">
<rect x="0" y="0" width="30" height="80" fill="#4d4dff" stroke="#000000" stroke-width="2"/>
<rect x="40" y="0" width="30" height="80" fill="#4d4dff" stroke="#000000" stroke-width="2"/>
<rect x="80" y="0" width="30" height="80" fill="#4d4dff" stroke="#000000" stroke-width="2"/>
<rect x="120" y="0" width="30" height="80" fill="#4d4dff" stroke="#000000" stroke-width="2"/>
<rect x="160" y="0" width="30" height="80" fill="#4d4dff" stroke="#000000" stroke-width="2"/>
<text x="15" y="-10" text-anchor="middle" font-family="Arial" font-size="16" font-weight="bold">Back</text>
<text x="175" y="-10" text-anchor="middle" font-family="Arial" font-size="16" font-weight="bold">Front</text>
</g>

<rect x="80" y="10" width="30" height="80" fill="#4d4dff" stroke="#000000" stroke-width="2"/>
<path d="M 95 90 Q 95 120 160 120" fill="none" stroke="#000000" stroke-width="2" marker-end="url(#arrow-black)"/>
<text x="150" y="145" text-anchor="end" font-family="Arial" font-size="18" font-weight="bold">Enqueue</text>

<path d="M 390 100 Q 430 100 445 130" fill="none" stroke="#000000" stroke-width="2" marker-end="url(#arrow-black)"/>
<text x="400" y="90" font-family="Arial" font-size="18" font-weight="bold">Dequeue</text>
<rect x="430" y="140" width="30" height="80" fill="#4d4dff" stroke="#000000" stroke-width="2"/>
<defs>
<marker id="arrow-black" viewBox="0 0 10 10" refX="5" refY="5" markerWidth="6" markerHeight="6" orient="auto">
<path d="M 0 0 L 10 5 L 0 10 z" fill="#000000"/>
</marker>
</defs>
</svg>
</html>

== Aufbau und Spezifikation (API) ==
Im Kontext der objektorientierten Programmierung wird die abstrakte Datenstruktur (ADT) formal über eine wohldefinierte Schnittstelle abgebildet. Eine <code>Queue</code> sollte über die folgenden Methoden und Konstruktoren verfügen:

=== Konstruktor ===
* <code>Queue()</code>
** Eine leere Schlange wird erzeugt. Der Zustand der initialisierten Schlange ist leer.

=== Methoden ===
* <code>boolean isEmpty()</code>
** Die Anfrage liefert den Wert <code>true</code>, wenn die Schlange keine Objekte enthält. Andernfalls liefert sie <code>false</code>.
* <code>void enqueue(Object pObject)</code>
** Das Objekt <code>pObject</code> wird an die Schlange (hinten) angehängt. Falls <code>pObject</code> gleich <code>null</code> ist, bleibt die Schlange unverändert.
* <code>void dequeue()</code>
** Das erste Objekt (vorne) wird aus der Schlange entfernt. Falls die Schlange bereits leer ist, wird sie nicht verändert.
* <code>Object front()</code>
** Die Anfrage liefert das erste Objekt der Schlange zurück, ohne dieses aus der Schlange zu entfernen (die Schlange bleibt unverändert). Falls die Schlange leer ist, wird <code>null</code> zurückgegeben.

== Laufzeitanalyse (Komplexität) ==
Warteschlangen lassen sich in der Praxis äußerst effizient über Arrays mit Ringpuffer-Logik oder über einfach verkettete Listen implementieren. Eine Zeigerstruktur, die stets den Anfang (Front) und das Ende (Tail) speichert, garantiert hochperformante Speicher- und Lesezugriffe. Für die oben genannten Methoden ergibt sich gemäß der [[Landau-Symbole|Landau-Notation]] folgende Laufzeitkomplexität:

{| class="wikitable"
|-
! Operation !! 1. Best-Case !! 2. Average-Case !! 3. Worst-Case
|-
| <code>enqueue(Object pObject)</code> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math>
|-
| <code>dequeue()</code> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math>
|-
| <code>front()</code> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math>
|-
| <code>isEmpty()</code> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math>
|}

== Implementierungsbeispiel (Java) ==
Die grundlegende Struktur einer objektorientierten Implementierung als Rumpf-Klasse orientiert sich exakt an den curricularen Vorgaben.

<syntaxhighlight lang="java">
public class Queue {

// Verweise auf den Anfang und das Ende der Queue
private Node head;
private Node tail;

// Innere Knoten-Klasse für verkettete Listenstruktur
private class Node {
Object content;
Node nextNode;

public Node(Object pContent) {
content = pContent;
nextNode = null;
}
}

/**
* Konstruktor: Eine leere Schlange wird erzeugt.
*/
public Queue() {
head = null;
tail = null;
}

/**
* Prüft, ob die Schlange leer ist.
*/
public boolean isEmpty() {
return head == null;
}

/**
* Fügt ein Objekt hinten an die Schlange an.
*/
public void enqueue(Object pObject) {
if (pObject != null) {
Node newNode = new Node(pObject);
if (this.isEmpty()) {
head = newNode;
tail = newNode;
} else {
tail.nextNode = newNode;
tail = newNode;
}
}
}

/**
* Entfernt das vorderste Element aus der Schlange.
*/
public void dequeue() {
if (!this.isEmpty()) {
head = head.nextNode;
if (this.isEmpty()) {
tail = null;
}
}
}

/**
* Gibt das vorderste Element zurück.
*/
public Object front() {
if (this.isEmpty()) {
return null;
} else {
return head.content;
}
}
}
</syntaxhighlight>

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik LK]]
[[Kategorie:FI I SDM]]

Schlange - Versionsgeschichte

Flbkwikiadmin am 4. September 2026 um 07:26 Uhr