Stack und Queue in Aktion (Bitte Hilfe für die Klausur)

[chemical20]

Hallo zusammen, ich studiere Informatik und übernächste Woche habe ich ne Klausur.
Die unten stehende Fragen sind aus der Probeklausur. Ich verstehe den Sinn einfach nicht. Könnte jemand mir bitte erklären? Vielen lieben dank im voraus.



1. Auf einem Stack werden in gemischter Reihenfolge 10 Push und 10 PopOperationen ausgeführt. Es ist bekannt, dass die PushOperationen die Zahlen 0, 1, 2, …, 9 in dieser Reihenfolge einspeichern und dass bei jedem Pop der ausgespeicherte Wert ausgegeben wird. Welche Ausgabelisten sind möglich? Wählen Sie aus den beiden Blöcken jeweils die zutreffende Antwort aus (jeweils 2P für die richtige Kombination/0P für jede andere).
(A) 1 2 3 4 5 6 9 8 7 0
(B) 0 4 6 5 3 8 1 7 2 9
(C) 1 4 7 9 8 6 5 3 0 2
(D) 2 1 4 3 6 5 8 7 9 0 2.

Auf einer Queue werden in gemischter Reihenfolge 10 Enqueue und 10 DequeueOperationen ausgeführt. Es ist bekannt, dass die EnqueueOperationen die Zahlen 0, 1, 2, …, 9 in dieser Reihenfolge einspeichern und dass bei jedem Dequeue der ausgespeicherte Wert ausgegeben wird. Welche Ausgabelisten sind möglich? Wählen Sie aus den beiden Blöcken jeweils die zutreffende Antwort aus (jeweils 1P für die richtige Kombination/0P für jede andere).
(E) 4 6 8 7 5 3 2 9 0 1
(F) 2 5 6 7 4 8 9 3 1 0
(G) 0 1 2 3 4 5 6 7 8 9
(H) 4 3 2 1 0 5 6 7 8 9 9.

 

[YOES1805]

Ich weiß noch das Stacks in Java First in Last out sind. Wenn die zahlen 0,1,2,3...9 in dieser reihenfolge eingespeichert werden sollten sie auch anders herum wieder ausgegeben werden, also 9,8,7...0.

Noch dazu musst du wissen das ein stack bei einer pop operation die zahl aus dem Stack komplett entfernt.

 

[Meniskusschaden]

Die zehn push-Operationen sollen in der Reihenfolge push 0, push 1, push 2, ... , push 9 ausgeführt werden, aber nicht zwangsläufig unmittelbar nacheinander, sondern einige der zehn pop-Operationen können eingeschoben werden. Z.B. wäre push 0, push 1, pop, push 2, ... bis dahin erlaubt. push 1, push 0, ... und push 0, pop, pop, ... sind Beispiele, die nicht erlaubt sind. Du musst prüfen, ob sich die Ausgaben A-D durch solche push-/pop-Folgen erzeugen lassen. Bei der zweiten Aufgabe eben entsprechend für die Queue-Operationen.

 

[MoxxiManagarm]

Ich erkläre es dir am Beispiel von a), welches möglich ist. Erst finden 2 Push Aktionen statt, wodurch 0 und 1 auf dem Stack liegen. Dann pop(1) und jeweils abwechselnd push(n) und pop(n) bis pop(6). Dann befindet sich nur noch die 0 auf dem Stack. Dann erfolgt push(7..9), der Stack enthält 0,7,8,9. Dann werden diese alle nacheinander mit pop entfernt. d) ist nicht möglich, da die 2 nicht 2x entfernt werden kann. Überlege dir das gleiche nun mit b und c.

 

[mrBrown]

d) ist nicht möglich, da die 2 nicht 2x entfernt werden kann.

Die zweite 2. dürfte die Nummer der nächsten Aufgabe sein, zumindest hab ich das so interpretiert

 

[MoxxiManagarm]

Die zweite 2. dürfte die Nummer der nächsten Aufgabe sein, zumindest hab ich das so interpretiert

Achso ja macht Sinn dann revidiere ich meine Aussage.

 

[chemical20]

Ich erkläre es dir am Beispiel von a), welches möglich ist. Erst finden 2 Push Aktionen statt, wodurch 0 und 1 auf dem Stack liegen. Dann pop(1) und jeweils abwechselnd push(n) und pop(n) bis pop(6). Dann befindet sich nur noch die 0 auf dem Stack. Dann erfolgt push(7..9), der Stack enthält 0,7,8,9. Dann werden diese alle nacheinander mit pop entfernt. d) ist nicht möglich, da die 2 nicht 2x entfernt werden kann. Überlege dir das gleiche nun mit b und c.

Vielen dank 🙂
Ich habe es endlich verstanden.
Bei D hätte eigentlich keine 2 am Ende stehen sollen, ich habe es falsch abgeschrieben.
Also D ist =2 1 4 3 6 5 8 7 9 0

 

[MoxxiManagarm]

Und was würdest du bei der ersten Aufgabe sagen für b-d welche möglich sind? Nur der Interesse halber für mich zum Verifizieren ob es wirklich klick gemacht hat bei dir. Selbst anwenden ist meist schwieriger als ein Beispiel zu verstehen.