Queue - Versionsgeschichte

Akaibel am 23. Januar 2022 um 16:46 Uhr

2022-01-23T16:46:39Z

← Nächstältere Version		Version vom 23. Januar 2022, 16:46 Uhr
Zeile 73:		Zeile 73:
	Wenn man einen Queue durchläuft, dann muss man die Inhalte auf einen Hilfs-Queue "retten" und am Ende wieder zurück auf den eigentlichen Queue übertragen!		Wenn man einen Queue durchläuft, dann muss man die Inhalte auf einen Hilfs-Queue "retten" und am Ende wieder zurück auf den eigentlichen Queue übertragen!
	== Methode anzahl ==		== Methode anzahl ==
	<code>		<code>
	public int anzahl(Queue<Buch> pQueue) {		public int anzahl(Queue<Buch> pQueue) {
	int ergebnis = 0;		int ergebnis = 0;
Zeile 90:		Zeile 90:
	return ergebnis;		return ergebnis;
	}		}
	</code>		</code>

	== Methode enthaelt==		== Methode enthaelt==
	<code>		<code>
	public boolean enthaelt(Queue<Buch> pQueue, String pTitel) {		public boolean enthaelt(Queue<Buch> pQueue, String pTitel) {
	boolean ergebnis = false;		boolean ergebnis = false;
Zeile 112:		Zeile 112:
	return ergebnis;		return ergebnis;
	}		}
	</code>		</code>

	== Methode loeschen ==		== Methode loeschen ==
	<code>		<code>
	public void loeschen(Queue<Buch> pQueue, String pTitel) {		public void loeschen(Queue<Buch> pQueue, String pTitel) {
	Queue<Buch> hilfs = new Queue<Buch>();		Queue<Buch> hilfs = new Queue<Buch>();
Zeile 131:		Zeile 131:
	}		}
	}		}
	</code>		</code>

	== Methode alphabetischErstes ==		== Methode alphabetischErstes ==
	<code>		<code>
	private Buch alphabetischErstes(Queue<Buch> pQueue) {		private Buch alphabetischErstes(Queue<Buch> pQueue) {
	Queue<Buch> hilfs = new Queue<Buch>();		Queue<Buch> hilfs = new Queue<Buch>();
Zeile 155:		Zeile 155:
	return ergebnis;		return ergebnis;
	}		}
	</code>		</code>

	== Methode alphabetischRichtigEinfuegen ==		== Methode alphabetischRichtigEinfuegen ==
	<code>		<code>
	// '''Die Methode setzt voraus, dass pQueue schon alphabetisch sortiert und mit Strings gefüllt ist.'''		// '''Die Methode setzt voraus, dass pQueue schon alphabetisch sortiert und mit Strings gefüllt ist.'''
	private void alphabetischRichtigEinfuegen(Queue<String> pQueue, String pString) {		private void alphabetischRichtigEinfuegen(Queue<String> pQueue, String pString) {
Zeile 177:		Zeile 177:
	}		}
	}		}
	</code>		</code>

	= Implementationsdiagramm =		= Implementationsdiagramm =
Zeile 191:		Zeile 191:

	[[File:Klassendiagramm-Node.png\|thumb\|Klassendiagramm Node\|322px]]		[[File:Klassendiagramm-Node.png\|thumb\|Klassendiagramm Node\|322px]]
	<code>		<code>
	public class Queue<ContentType>{		public class Queue<ContentType>{
	private Node<ContentType> front;		private Node<ContentType> front;
Zeile 266:		Zeile 266:
	}		}
	}		}
	</code>		</code>

Akaibel: /* Funktionsweise */

2019-06-23T13:54:58Z

Funktionsweise

← Nächstältere Version		Version vom 23. Juni 2019, 13:54 Uhr
Zeile 4:		Zeile 4:
	[[Kategorie:Datenstrukturen(IF)]]		[[Kategorie:Datenstrukturen(IF)]]


			=Fachbegriffe=

			Schlange (Queue), hinten anhängen (enqueue()), vorne entfernen (dequeue()), ist leer (isEmpty())

	= Funktionsweise =		= Funktionsweise =

	Die Datenstruktur Schlange (engl. queue) entspricht einer Warteschlange mit höflichen Menschen: Jeder Neuankömmling stellt sich hinten an und wartet geduldig, bis er ganz vorne steht und an der Reihe ist. Wer also zuerst kommt, ist auch zuerst dran. Entsprechend spricht man bei Schlangen in Anlehnung an die englische Kurzform first in, first out vom FIFO-Prinzip.		Die Datenstruktur Schlange (engl. queue) entspricht einer Warteschlange mit höflichen Menschen: Jeder Neuankömmling stellt sich hinten an und wartet geduldig, bis er ganz vorne steht und an der Reihe ist. Wer also zuerst kommt, ist auch zuerst dran. Entsprechend spricht man bei Schlangen in Anlehnung an die englische Kurzform first in, first out vom FIFO-Prinzip.

Akaibel: /* Verwendung von Queues */

2019-02-08T18:09:29Z

Verwendung von Queues

← Nächstältere Version		Version vom 8. Februar 2019, 18:09 Uhr
Zeile 64:		Zeile 64:
	Die Verwendung von Queues wird hier aufgezeigt für Queues, die Objekte vom Typ Buch enthalten (vgl. Klassendiagramm rechts)		Die Verwendung von Queues wird hier aufgezeigt für Queues, die Objekte vom Typ Buch enthalten (vgl. Klassendiagramm rechts)

			'''Vorsicht:'''<br/>

			Wenn man einen Queue durchläuft, dann muss man die Inhalte auf einen Hilfs-Queue "retten" und am Ende wieder zurück auf den eigentlichen Queue übertragen!
	== Methode anzahl ==		== Methode anzahl ==
	<code>		<code>

Akaibel am 8. Februar 2019 um 18:07 Uhr

2019-02-08T18:07:32Z

← Nächstältere Version		Version vom 8. Februar 2019, 18:07 Uhr
Zeile 3:		Zeile 3:
	[[Kategorie:Informatik-Abitur]]		[[Kategorie:Informatik-Abitur]]
	[[Kategorie:Datenstrukturen(IF)]]		[[Kategorie:Datenstrukturen(IF)]]
	~~<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>~~

	= Funktionsweise =		= Funktionsweise =

Akaibel am 8. Februar 2019 um 18:07 Uhr

2019-02-08T18:07:18Z

← Nächstältere Version		Version vom 8. Februar 2019, 18:07 Uhr
Zeile 52:		Zeile 52:
	Die Queue funktioniert wie eine Warteschlange an einer (englischen!!) Bushaltestelle: Man kann sich hinten anstellen und vorne wieder eine Person entnehmen.		Die Queue funktioniert wie eine Warteschlange an einer (englischen!!) Bushaltestelle: Man kann sich hinten anstellen und vorne wieder eine Person entnehmen.

	~~(In der Animation heißen die beiden Attribute der Klasse <code>Queue</code> ''front'' und ''last'' (statt ''head'' und ''tail'' wie in der Abi-Schnittstelle).)~~

	====Veranschaulichung: enqueue(ContentType pContent)====		====Veranschaulichung: enqueue(ContentType pContent)====
Zeile 176:		Zeile 175:
	''Wie ist die Klasse <code>Queue</code> implementiert?''<br/>		''Wie ist die Klasse <code>Queue</code> implementiert?''<br/>
	[[File:Implementationsdiagramm_Queue.png\|thumb\|Implementationsdiagramm Queue \|628px]]		[[File:Implementationsdiagramm_Queue.png\|thumb\|Implementationsdiagramm Queue \|628px]]
	* Die Queue ''hat'' zwei [[Node\|Nodes]]: <code>~~head~~</code> und <code>~~tail~~</code> (Wenn nur ein Node enthalten ist, ist dieser sowohl <code>~~head~~</code> als auch <code>~~tail~~</code>).		* Die Queue ''hat'' zwei [[Node\|Nodes]]: <code>front</code> und <code>last</code> (Wenn nur ein Node enthalten ist, ist dieser sowohl <code>front</code> als auch <code>last</code>).
	* Jeder der Nodes hat einen <code>content</code>; darin wird der eigentliche Inhalt gespeichert (z.B. ein Objekt vom Typ <code>Person</code> oder ein <code>String</code>).		* Jeder der Nodes hat einen <code>content</code>; darin wird der eigentliche Inhalt gespeichert (z.B. ein Objekt vom Typ <code>Person</code> oder ein <code>String</code>).
	* Außerdem hat jeder [[Node\|Node]] einen Verweis <code>next</code> auf den Nachfolgerknoten.		* Außerdem hat jeder [[Node\|Node]] einen Verweis <code>next</code> auf den Nachfolgerknoten.

Akaibel: /* Objektdiagramm einer Queue */

2019-02-08T18:03:02Z

Objektdiagramm einer Queue

← Nächstältere Version		Version vom 8. Februar 2019, 18:03 Uhr
Zeile 45:		Zeile 45:
	= Objektdiagramm einer Queue =		= Objektdiagramm einer Queue =

	[[Datei:~~Queue_ab_Abi2017~~.png]]		[[Datei:Queue.png]]

	Die Queue selbst hat nur die beiden Attribute <code>'''front'''</code> und <code>'''last'''</code>, sie kann demnach nur auf den ersten und den letzten Knoten direkt zugreifen. Dies reicht aus, da Queue-Operationen immer nur ganz vorne (Anschauen, Löschen) bzw. ganz hinten (Hinzufügen) möglich sind und die <code>[[Node\|Nodes]]</code> untereinander verbunden sind (jeder <code>[[Node]]</code> hat ein Attribut <code>next</code>, in dem eine Referenz auf das darunter liegende <code>[[Node]]</code>-Objekt gespeichert ist).		Die Queue selbst hat nur die beiden Attribute <code>'''front'''</code> und <code>'''last'''</code>, sie kann demnach nur auf den ersten und den letzten Knoten direkt zugreifen. Dies reicht aus, da Queue-Operationen immer nur ganz vorne (Anschauen, Löschen) bzw. ganz hinten (Hinzufügen) möglich sind und die <code>[[Node\|Nodes]]</code> untereinander verbunden sind (jeder <code>[[Node]]</code> hat ein Attribut <code>next</code>, in dem eine Referenz auf das darunter liegende <code>[[Node]]</code>-Objekt gespeichert ist).

Akaibel: /* Objektdiagramm einer Queue */

2019-02-08T17:52:02Z

Objektdiagramm einer Queue

← Nächstältere Version		Version vom 8. Februar 2019, 17:52 Uhr
Zeile 47:		Zeile 47:
	[[Datei:Queue_ab_Abi2017.png]]		[[Datei:Queue_ab_Abi2017.png]]

	Die Queue selbst hat nur die beiden Attribute <code>'''~~head~~'''</code> und <code>'''~~tail~~'''</code>, sie kann demnach nur auf den ersten und den letzten Knoten direkt zugreifen. Dies reicht aus, da Queue-Operationen immer nur ganz vorne (Anschauen, Löschen) bzw. ganz hinten (Hinzufügen) möglich sind und die <code>[[Node\|Nodes]]</code> untereinander verbunden sind (jeder <code>[[Node]]</code> hat ein Attribut <code>~~nextNode~~</code>, in dem eine Referenz auf das darunter liegende <code>[[Node]]</code>-Objekt gespeichert ist).		Die Queue selbst hat nur die beiden Attribute <code>'''front'''</code> und <code>'''last'''</code>, sie kann demnach nur auf den ersten und den letzten Knoten direkt zugreifen. Dies reicht aus, da Queue-Operationen immer nur ganz vorne (Anschauen, Löschen) bzw. ganz hinten (Hinzufügen) möglich sind und die <code>[[Node\|Nodes]]</code> untereinander verbunden sind (jeder <code>[[Node]]</code> hat ein Attribut <code>next</code>, in dem eine Referenz auf das darunter liegende <code>[[Node]]</code>-Objekt gespeichert ist).

	= Veranschaulichung: Warteschlange =		= Veranschaulichung: Warteschlange =

Akaibel: /* Implementierung */

2019-02-08T17:51:06Z

Implementierung

← Nächstältere Version		Version vom 8. Februar 2019, 17:51 Uhr
Zeile 186:		Zeile 186:
	<code>		<code>
	public class Queue<ContentType>{		public class Queue<ContentType>{
	private Node<ContentType> ~~head~~;		private Node<ContentType> front;
	private Node<ContentType> ~~tail~~;		private Node<ContentType> last;

	/**		/**
Zeile 195:		Zeile 195:
	*/		*/
	public Queue() {		public Queue() {
	~~head~~ = null;		front = null;
	~~tail~~ = null;		last = null;
	}		}

Zeile 206:		Zeile 206:
	*/		*/
	public boolean isEmpty() {		public boolean isEmpty() {
	return ~~head~~ == null;		return front == null;
	}		}

Zeile 220:		Zeile 220:
	Node<ContentType> newNode = new Node<ContentType>(pContent);		Node<ContentType> newNode = new Node<ContentType>(pContent);
	if (this.isEmpty()) {		if (this.isEmpty()) {
	~~head~~ = newNode;		front = newNode;
	~~tail~~ = newNode;		last = newNode;
	} else {		} else {
	~~tail~~.setNext(newNode);		last.setNext(newNode);
	~~tail~~ = newNode;		last = newNode;
	}		}
	}		}
Zeile 235:		Zeile 235:
	public void dequeue() {		public void dequeue() {
	if (!this.isEmpty()) {		if (!this.isEmpty()) {
	~~head~~ = ~~head~~.getNext();		front = front.getNext();
	if (this.isEmpty()) {		if (this.isEmpty()) {
	~~head~~ = null;		front = null;
	~~tail~~ = null;		last = null;
	}		}
	}		}
Zeile 255:		Zeile 255:
	return null;		return null;
	} else {		} else {
	return ~~head~~.getContent();		return front.getContent();
	}		}
	}		}
	}		}
	</code>		</code>

Akaibel: /* Implementierung */

2019-02-08T17:49:33Z

Implementierung

← Nächstältere Version		Version vom 8. Februar 2019, 17:49 Uhr
Zeile 181:		Zeile 181:

	= Implementierung =		= Implementierung =
	Für die Implementierung wird die Klasse [[Node]] verwendet.		Für die Implementierung wird die Klasse '''[[Node]]''' verwendet, für die das Klassendiagramm rechts gilt.

			[[File:Klassendiagramm-Node.png\|thumb\|Klassendiagramm Node\|322px]]
	<code>		<code>
	public class Queue<ContentType>{		public class Queue<ContentType>{

Akaibel: /* Objektdiagramm einer Queue */

2019-02-08T17:46:51Z

Objektdiagramm einer Queue

← Nächstältere Version		Version vom 8. Februar 2019, 17:46 Uhr
Zeile 44:		Zeile 44:

	= Objektdiagramm einer Queue =		= Objektdiagramm einer Queue =
	~~[[Datei:Klassendiagramm_QueueNode.png\|300px\|thumb\|right\|Klassendiagramm der Klasse QueueNode]]~~

	[[Datei:Queue_ab_Abi2017.png]]		[[Datei:Queue_ab_Abi2017.png]]

	Die Queue selbst hat nur die beiden Attribute <code>'''head'''</code> und <code>'''tail'''</code>, sie kann demnach nur auf den ersten und den letzten Knoten direkt zugreifen. Dies reicht aus, da Queue-Operationen immer nur ganz vorne (Anschauen, Löschen) bzw. ganz hinten (Hinzufügen) möglich sind und die <code>[[~~QueueNode~~\|~~QueueNodes~~]]</code> untereinander verbunden sind (jeder <code>[[~~QueueNode~~]]</code> hat ein Attribut <code>nextNode</code>, in dem eine Referenz auf das darunter liegende <code>[[~~QueueNode~~]]</code>-Objekt gespeichert ist).		Die Queue selbst hat nur die beiden Attribute <code>'''head'''</code> und <code>'''tail'''</code>, sie kann demnach nur auf den ersten und den letzten Knoten direkt zugreifen. Dies reicht aus, da Queue-Operationen immer nur ganz vorne (Anschauen, Löschen) bzw. ganz hinten (Hinzufügen) möglich sind und die <code>[[Node\|Nodes]]</code> untereinander verbunden sind (jeder <code>[[Node]]</code> hat ein Attribut <code>nextNode</code>, in dem eine Referenz auf das darunter liegende <code>[[Node]]</code>-Objekt gespeichert ist).

	= Veranschaulichung: Warteschlange =		= Veranschaulichung: Warteschlange =