Sequenz von Zahlen bei einem Stack möglich oder nicht möglich?

[Steiner2023]

Hi,
nachdem ich nun schon 2h lang nachgedacht habe und auf stackoverflow nach Erklärungen gesucht habe, aber dennoch nicht schlauer geworden bin, will ich es hier versuchen.
Die Aufgabenstellung lautet:

Suppose that a client performs an intermixed sequence of stack push and pop operations. The push operations push the integers 0 through 9 in order on to the stack; the pop operations print out the return value. Which of the following sequences could not occur?

(a) 4 3 2 1 0 9 8 7 6 5
(b) 2 1 4 3 6 5 8 7 9 0
(c) 0 4 6 5 3 8 1 7 2 9
(d) 4 6 8 7 5 3 2 9 1 0
(e) All of these sequences are possible

Die Antwort ist C. Ich kann aber überhaupt nicht nachvollziehen warum. Bitte erklärt mir das einer für ganz doofe Menschen.

 

[Meniskusschaden]

Hier ist mal als Beispiel die Befehlsfolge, die Ausgabe (a) erzeugt. Ich glaube, so wird das Prinzip relativ einfach deutlich:

push 0
push 1
push 2
push 3
push 4
pop
pop
pop
pop
pop
push 5
push 6
push 7
push 8
push 9
pop
pop
pop
pop
pop

 

[Steiner2023]

Danke für die Antwort, aber warum hörst du bei der 4 mit dem push auf? Weil es die Hälfte ist?

Wäre folglich C so:
push 3
push 5
push 6
push 4
push 0
pop
pop
pop
pop
pop
push 9
push 2
push 7
push 1
push 8
pop
pop
pop
pop
pop

Aber warum ist das jetzt falsch?
Wäre es bei einer Queue das selbe Prinzip, nur das man beim pop(dequeue) die selbe Reihenfolge (also nicht wie beim Stack die umgekehrte) bekommt?

 

[Meniskusschaden]

Danke für die Antwort, aber warum hörst du bei der 4 mit dem push auf? Weil es die Hälfte ist?

Nein, sondern weil die 4 bei (a) als erste Ziffer ausgegeben werden soll. Wenn ich weitere push-Operationen vornehmen würde, müsste ich ja Ziffern entfernen, um wieder an die 4 zu kommen. Und dann würden diese Ziffern vor der 4 ausgegeben werden.

Aber warum ist das jetzt falsch?

Weil das zwar die korrekt Ausgabe für (c) erzeugt, aber die Bedingung verletzt, dass die Ziffern 0 bis 9 in dieser Reihenfolge auf den Stack gelegt werden sollen.

Wäre es bei einer Queue das selbe Prinzip, nur das man beim pop(dequeue) die selbe Reihenfolge (also nicht wie beim Stack die umgekehrte) bekommt?

Ja, aber bei einer Queue ist das nicht interessant, weil man die Objekte ohnehin immer nur genau in der Reihenfolge heraus bekommt, in der man sie hinein getan hat. Beim Stack ist es aber nicht unbedingt die umgekehrte Reihenfolge, wie man oben sieht.

 

[FourOhFour]

Okay, ich versuche es mal mit meinen Worten zu erklären:

In der Aufgabe sollst du die Zahlen 0-9 (von 0 anfangen, bei 9 aufhören) auf einen Stack legen und runternehmen. Das mit dem Runternehmen kannst du an jeder beliebigen Stelle machen, aber wenn du 0 "gepushed" hast, dann musst du mit 1 weiter machen, dann mit 2, 3, etc..
(Heißt: Wenn du z.B.

0 push
1 push
pop

dann musst du nach dem pop der 1 dennoch als nächstes die 2 pushen, auch wenn du z.B. noch einen pop für die 0 gemacht hast.

pop
2 push
...)

Mit dieser Erklärung schau dir nochmal das Beispiel von Meniskusschaden an - ich denke jetzt wirst du es verstehen.

 

[Steiner2023]

Okay, danke ich glaub ich habs jetzt verstanden