Stacks und Queues

Question 1

Stack

Answer 1

° Datenstruktur die eine Folge von Elementen vom gleichen Datentypen enthält
° Eingeschränkte Einfüge- und Ausfügeoperationen
° einfügeoperation push
- Fügt ein Element an das Ende der Folge ein
° Ausfügeoperation pop
- Entfernt das letzte Element der Folge und liefert es als Ergebnis
° LIFO-Prinzip (Last In First Out): immer das zuletzt eingefügte Element muss als erstes wieder entfernt werden

Question 2

Stack- Interface

Answer 2

interface Stack
{
   void push(E element);
   E pop();
   boolean isEmpty();
}

s.push(“X”); // “X” wird am Anfang eingefügt
s.push(“Z”); // “Z” wird auch am Anfang eingefügt, ist nun das Erste Element der Liste
String t = s.pop(); // t == “Z”, “Z” wird entfernt

Question 3

Queue

Answer 3

° Eine Folge von Elementen eines gegebenen Datentyps
° Ein Element wird an das Ende der Folge eingefügt
° Das erste Element der Folge wird entfernt und als Ergebnis geliefert
° FIFO-Prinzip(First In First Out): Das zuerst eingefügte Element wird als erste wieder entfernt
° Breitensuche:
- Initialisierung: füge das Wurzelelement in eine Queue ein
- Schleife - solange die Queue noch Elemente enthält: Entnimmt das erste Element und füge seine Nachfolge in die Queue ein

Question 4

Queue-Interface

Answer 4

interface Queue
{
   void enqueue(E element);
   E dequeque();
   boolean isEmpty();
}

q.enqueue(“X”); // fügt “X” am ende ein
q.enqueue(“Z”); // fügt “Z” am ende ein, also nach “X”
String s = q.dequeue(); // s == “A”, das erste aus der Liste wird entfernt