Warum wird etwas auf den Stapel gelegt, das als "Push" bezeichnet wird?

22

Laut http://dictionary.reference.com

drücken

Verb (verwendet mit Objekt)

  1. mit Gewalt auf oder gegen ein Ding drücken, um es wegzubewegen.

  2. (etwas) auf eine bestimmte Art und Weise bewegen, indem man Kraft ausübt; schieben; fahren: etwas beiseite schieben; die Tür aufstoßen .

  3. zu bewirken oder zu vollbringen, indem man Hindernisse beiseite stößt: sich durch die Menge schieben.

  4. verlängern oder projektieren lassen; Schub.

  5. zu einer Aktion oder einem Kurs drängen oder drängen: Seine Mutter drängte ihn, einen Job zu bekommen.

Diese IMO passt zu FIFO- Warteschlangen. Gibt es eine Erklärung dafür?

doc
quelle
2
Naja ... in Israel galt die Analogie für ein Waffenmagazin, da man die Kugeln hineindrücken muss ... aber ich glaube, ich mag den Pez-Dispenser besser.
GY
@GY - LOL - Ich bin hierher gekommen, um genau das zu sagen (das Pez-Ding). BASTARD! Interessante Kultur in Israel ...
Edward Strange
Ich schätze, wenn ich nur für heute FGITW bin!
Scott C Wilson
1
Diese Frage wurde gestellt und beantwortet auf Stackoverflow - stackoverflow.com/questions/420315/stacks-why-push-and-pop . Push und Pop werden diskutiert.
Bratch
Benötigt "history" -Tag.
Bratch

Antworten:

47

Der Legende nach hat der ursprüngliche Stapel seinen Namen in Analogie zu den Geschirrstapeln in der Mensa der Universität erhalten: Man legt ein Geschirr darauf, und der (gefederte) Geschirrstapel sinkt ein wenig, man nimmt ein Geschirr weg und es platzt ein bisschen nach oben. Aus diesem Grund wurde beim „Drücken“ die Konnotation einer Abwärtsbewegung verwendet, auch wenn Sie nicht auf die Platte drücken - Sie legen sie einfach ab und die Schwerkraft erledigt die Arbeit. "Pushdown-Stapel" ist immer noch eine gebräuchliche Phrase, und Stapel neigen dazu, im Speicher nach unten zu wachsen (dh mit abnehmenden Speicheradressen), obwohl es zweifelhaft ist, ob dies etwas mit Schalenstapeln zu tun hat oder nicht.

Kilian Foth
quelle
1
Pushdown kann von Pushdown-Automaten stammen.
Oded
11
@Oded Ich bin mir ziemlich sicher, dass es umgekehrt ist. Ein Pushdown-Automat ist ein endlicher Automat, der durch einen Pushdown-Stapel erweitert wird.
Konrad Rudolph
Und Sie wissen, dass einige arme Idioten lernen, dass niedrigere Speicheradressen ganz unten stehen, weil der PC "hoch" zählt.
Philip
Ich hatte den Eindruck, dass der Ursprung etwas mit diesen Dokumenten-Spikes zu tun hat. Weißt du, ein Nagel, der senkrecht gehalten wird und auf den du ein Stück Papier
Ian
44

Denken Sie an einen Pez-Spender . Das ist dein mentales Modell für einen Stack - last in, first out. Wenn Sie also einen Gegenstand zu einem Stapel hinzufügen, müssen Sie die vorhandenen Gegenstände nach unten drücken, um Platz zu schaffen.

http://i.stack.imgur.com/VJkYi.jpg

Scott C Wilson
quelle
2
mmmmmm ... Pez !!!
Steven A. Lowe
1
Ich wollte das Modell eines Munitionsmagazins vorschlagen, aber der Pez-Spender ist ein viel familienfreundlicheres Bild. +1 und ich wünschte, ich könnte mehr stimmen.
KeithS
Ich bin versucht, -1 für Hallo Kitty, aber es würde die Antwort und die Analogie Gerechtigkeit nicht tun. Also +1 von mir.
0xC0000022L
und so erklärst du einem Kind "Stack" :)
Chani
StackOverflow ist, wenn Sie versuchen, es mit einer ganzen Packung Pez zu füllen, und das Ganze aus Ihren Fingern herausschnellt, bevor Sie es hineinstecken, damit es sich überall ausbreitet.
Ehrfurcht
3

FIFO ist eine Warteschlange - die erste, die der Gruppe hinzugefügt wird, wird zuerst bedient.

LIFO ist ein Stapel - wie ein Haufen Tabletts. Sie nehmen immer die von der Spitze des Stapels.

Der Begriff Push wird verwendet, wenn ein Artikel zum LIFO / Stack hinzugefügt wird, da sich der Tablettstapel in einigen Cafeterias auf einer federbelasteten Oberfläche befindet. Je mehr Gegenstände auf den Stapel geschoben werden, desto tiefer sinkt der gesamte Stapel.

Wenn das oberste / neueste Element vom Stapel entfernt wird, wird das oberste Element vom oberen Ende des Stapels "abgesprungen".

mhoran_psprep
quelle
Der Plattenstapel in einer Cafeteria wird häufig verwendet, um die Funktionsweise einer Stapel-Datenstruktur zu veranschaulichen. Haben Sie jedoch Beweise dafür, dass die Terminologie von dort stammt?
Caleb
@Caleb, TAOCP Volume 1 (S. 237 in der zweiten Ausgabe) impliziert, dass dies der Fall ist, gibt jedoch kein Zitat an. Auf der vorherigen Seite wird erläutert, wie die Begriffe "Stapel" und "Warteschlange" allmählich zur Standardterminologie werden. Dies ist möglicherweise die früheste mögliche Referenz.
mpdonadio
3

Die Illustrationen mit Cafeteria-Tellern oder -Tabletts, Pez-Spendern und Stapel von Büchern kamen alle später. Aus Wikipedia: (mit Referenzen)

"Der Stapel wurde erstmals 1946 im Computerentwurf von Alan M. Turing (der die Begriffe" Begraben "und" Entgraben "verwendete) als Mittel zum Aufrufen und Zurückkehren von Unterprogrammen vorgeschlagen." Zusätzliche Arbeiten und Patente von anderen folgten 1957. Die aktuellen Illustrationen von Stacks, die wir heute verwenden, könnten dazu geführt haben, dass sich Turings ursprüngliche Begriffe von Begraben und Nichtbegraben zu Push und Pop entwickelt haben. Vielleicht klingen diese Begriffe einfach besser.

Die Antwort auf die Frage des OP lautet, wo genau oder wann dies geschah. Vielleicht ist die Antwort in einem der Wikipedia-Verweise wie " Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens " vergraben .

Bratch
quelle