Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Sequenz von Zahlen bei einem Stack möglich oder nicht möglich?
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?
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?
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.
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.
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.
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.