Informatik Warteschlange Programmieren?

3 Antworten

geri3d
Nutzer, der sehr aktiv auf gutefrage ist
im Thema programmieren
30.11.2022, 09:21

Das Video meines Vorantworters finde ich zwar peppig und einfach aber es wird überhaut nicht erwähnt um wie viel mächtiger eine Rekursion ist und wo es gar nicht anders geht.

Zu den dynamischen und statischen Warteschlangen kann ich dir nur sagen stell dir eine Arzpraxis vor, Leute machen Termine und kommen auf eine Warteschlange. Es steht also fest wieviele Termine sind, anders in einem Supermarkt, wo ständig Leute abgefertigt werden und hinten immer neue dazu kommen.

Über Rekusive Funktionen lassen sich zum Beispiel ganze Verzeichnisstrukturen auslesen, was in einer Iteration nur sehr aufwändig wäre.

Das Prinzip wie im Video nur nehmen wir einen Ordner mit vielen Unterordnern und es geht darum, die Gesammtgröße auf der Platte zu ermitteln, dann sieht die Rekursion so aus (Pseudocode):

Funct getSizeOfDir(Dir as Directory)
// „Dir ist das Startverzeichnis"

static fileSize as Double

If Dir has Subdirs{
   For Each subDir in Dir
     getSizeOfDir(subDir) // <-- Rekursion
   Next
}Else{
     For Each file in Dir
        fileSize = filesize + file.size
     Next
}
Woher ich das weiß:Berufserfahrung
daCypher
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
programmieren
30.11.2022, 10:08

Ziemlich viele Fragen auf einmal, aber ich geh mal der Reihe nach durch.

Deinen Fragen nach zu urteilen, gehe ich mal davon aus, dass ihr die Warteschlange einmal mit einem Array und einmal mit einer List (LinkedList oder ArrayList?) aufgebaut habt. Das ist leider typisch für Unterrichtsstunden, aber im "normalen Leben" würde man für sowas eine Queue oder in diesem Fall eher eine PriorityQueue benutzen. Das sind beides Klassen (bzw. ein Interface und eine Klasse), die in Java schon enthalten sind. Wobei, falls ihr bei der dynamischen Version wenigstens eine LinkedList benutzt habt, habt ihr vielleicht die poll() Funktion benutzt, die auch bei einer Queue benutzt wird (LinkedList implementiert das Interface Queue - dazu später mehr)

Was ist die Theorie von statisch und dynamisch?

Die Frage ist etwas ungenau, aber in diesem Zusammenhang wird damit vermutlich der Unterschied zwischen Arrays und Listen gemeint sein.

Arrays haben eine statische Größe. Wenn man ein Array initialisiert, muss man angeben, wie groß das Array sein soll. Man kann einzelnen Indizes (also Speicherpositionen) einen Wert oder ein Objekt zuweisen und auch wieder auslesen.

Bei Listen wird hauptsächlich zwischen ArrayList und LinkedList unterschieden. Eine ArrayList ist im Prinzip ein Array, was automatisch von Java verwaltet wird. Man braucht also keine Größe vorgeben, kann Elemente hinzufügen oder löschen und der Speicherplatz wird automatisch angepasst, wenn er für die bestehenden Elemente nicht ausreicht. Eine ArrayList hat die gleichen Stärken, wie ein Array. Man kann schnell auf seine gewünschten Indizes zugreifen und sie z.B. ändern. Man kann die Liste schnell sortieren. Dafür ist sie aber ziemlich langsam, wenn man viele Elemente hinzufügt ohne zu sagen, wie groß die ArrayList am Ende sein soll, weil jedes Mal wenn die Größe des darunterliegenden Arrays geändert werden soll, das komplette Array kopiert werden muss.

Eine LinkedList besteht dagegen aus einem Haufen einzelnen Elementen, die jeweils einen Zeiger zum vorherigen und zum nächsten Element gespeichert haben. Die LinkedList hat ihre Stärken, wenn man am Anfang/Ende neue Elemente hinzufügt oder entfernt, dafür ist sie aber ziemlich langsam, wenn man Elemente per Index lesen/schreiben will, weil sie sich jedes Mal bis zum gewünschten Element "durchhangeln" muss, um es auszulesen. Allerdings ist sie schneller als eine ArrayList, wenn man z.B. in der Mitte neue Elemente hinzufügt oder entfernt, weil die ArrayList alle Elemente eine Stelle weiterkopieren muss, während die LinkedList nur die Zeiger der benachbarten Elemente ändern muss.

Was sind Arrays?

Das hab ich im Prinzip schon beantwortet. Arrays sind im Prinzip ganze Blöcke von Daten, und man kann mit einem Index auf einzelne Elemente dieses Blocks zugreifen.

Was ist der Vorteil eine Liste gegenüber eines Arrays?

Das hab ich auch schon weitestgehend beantwortet. Man braucht sich nicht um die Größe kümmern, sondern kann einfach Elemente hinzufügen/entfernen. Im Falle der LinkedList kann man sogar einfach an beiden Enden Elemente hinzufügen entfernen, daher wäre sie für die Warteschlange am sinnvollsten. Mit list.add(patient) fügt man einen Patienten am Ende hinzu und mit patient=list.poll() holt man sich einen Patienten vom Anfang der Liste. (Ich hab am Anfang ja schon erwähnt, dass eine PriorityQueue noch sinnvoller wäre. Damit kann man auch Patienten am Ende hinzufügen, aber man kann noch eine Priorität vorgeben, z.B. dass schwerverletzte Patienten ganz an den Anfang der Warteliste rücken sollen)

Was bedeutet "Liste implementieren"?

Implementieren heißt einfach, dass du eine Aufgabe in einen Programmcode umsetzt. Wenn du also eine Liste implementieren sollst, sollst du einfach dein Programm so ändern, dass du eine Liste anstatt eines Arrays verwendest.

Was ist eine Schnittstelle?

Eine Schnittstelle ist quasi eine Vorgabe, mit der man definieren kann, was eine bestimmte Klasse können muss. Z.B. Queue ist ein Interface. Man kann eine Variable nicht einfach so als Queue initialisieren (also z.B. Queue patienten = new Queue() geht nicht), weil ein Interface nur vorgibt, welche Methoden die implementierende Klasse haben muss (im Falle einer Queue z.B. die Methoden add, addAll, peek, poll, remove, removeAll etc.) aber kein Programmcode für die Methoden hinterlegt ist. Man muss also eine Klasse nehmen, die das Interface Queue implementiert (z.B. LinkedList oder PriorityQueue), damit man die Queue benutzen kann.

Der Sinn dahinter ist, dass völlig verschiedene Klassen ein gemeinsames Interface implementieren und dadurch bestimmte Funktionen bereitstellen, die das Interface fordert. Z.B. implementieren viele Klassen das Comparable-Interface, was vorgibt, dass sie eine Methode namens compareTo anbieten müssen, mit der sie sich mit anderen Objekten vergleichen können, um z.B. in einer Liste sortiert werden zu können.

Dazu hatten wir was aufgeschrieben mit Listenelement als Container in Liste

Hmm, dazu kann ich dir nicht viel sagen. Container ist kein Interface in Java und bei LinkedLists kriegt man keinen direkten Zugriff auf die einzelnen Einträge (also die Kombination aus dem eigentlichen Element und den Zeigern zum vorherigen/nächsten Eintrag). Und selbst wenn, hat das nicht unbedingt was mit Interfaces zu tun.

Ein Interface im Zusammenhang mit Listen ist das Interface namens List. Du kannst eine Variable also als List deklarieren und kannst dir dann aussuchen, ob du für die Implementierung jetzt z.B. eine ArrayList oder eine LinkedList nimmst.

List<Patient> patienten = new LinkedList<>();

Dadurch ist es z.B. bei der Übergabe an andere Funktionen egal, ob es eine LinkedList oder eine ArrayList ist.

Was bedeutet es, eine Methode rekursiv zu implementieren?

Rekursiv bedeutet, dass eine Methode sich selbst aufruft. Beim Mergesort-Algorithmus wird z.B. ein Array in zwei Hälften geteilt, die beiden Hälften werden wieder an zwei neue Mergesort-Funktionen übergeben und dort wieder geteilt etc. bis die Arrays nur noch 1-2 Elemente haben, die ganz einfach sortiert werden können. Jede Instanz von Mergesort kriegt dadurch zwei sortierte Arrays zurück, die nur noch ineinander sortiert werden müssen, was deutlich schneller geht, als z.B. jedes Mal das komplette Array nach dem größten Element zu durchsuchen und es an eine neue Stelle zu schieben. Erfahrungsgemäß gibt es aber nur sehr selten mal Situationen, in denen es Sinn macht, etwas rekursiv zu lösen.