Stacks - warum PUSH und POP?

Question

Ich frage mich, warum wir die Begriffe „Push“ und „Pop“ für das Hinzufügen / Entfernen von Elementen aus Stapeln verwenden? Gibt es eine physikalische Metapher, die diese Begriffe verursacht werden gemeinsam?

Der einzige Vorschlag, den ich habe, ist so etwas wie ein gefedertes Magazin für eine Handfeuerwaffe , wo Runden „geschoben“ hinein und kann „knallte“, aber das scheint ein wenig unwahrscheinlich.

Eine zweite Stapel Trivia Frage: Warum hat die meisten CPUs den Call-Stack als wachsende nach unten im Speicher, anstatt nach oben implementieren?

Answer 1

Ich glaube, die gefederten Plattenstapel korrekt ist, als Quelle für den Begriff PUSH und POP.

Insbesondere hatte die Ostcampus Commons Cafeteria am MIT gefederten Stapel von Platten in dem 1957-1967 Zeitrahmen. Die Begriffe PUSH und POP würde im Gebrauch von dem Tech Model Railroad Clubs gewesen. Ich denke, dass dies der Ursprung ist.

Das Tech Model Railroad Club beeinflusste definitiv das Design der Digital Equipment Corporation (DEC) PDP-6. Die PDP-6 war eine der ersten Maschinen Stapel orientierten Anweisungen in der Hardware zu haben. Die Anweisungen waren PUSH, POP, PUSHJ, POPJ.

http://ed-thelen.org/comp- hist / pdp-6.html # Spezial% 20Features

Answer 2

Für Ihre zweite Frage betrifft, hat Wikipedia einen Artikel über die CS-Philosophie, die den Stapel steuert:

http://en.wikipedia.org/wiki/LIFO

Und zum ersten, auch auf wikipedia:

  

Eine häufig verwendete Metapher ist die Idee,   aus einem Stapel von Platten in einer Feder   geladen Cafeteria-Stack. In einem solchen   Stapel, nur die obere Platte sichtbar ist   und für den Benutzer zugänglich, alle anderen   Platten bleiben verborgen. Als neue Platten   hinzugefügt werden, wird jede neue Platte die   oben auf dem Stapel, wobei jede Platte versteckt   unten, Schieben des Stapels von Platten   Nieder. Da die obere Platte entfernt ist von   der Stapel, können sie verwendet werden, die   Platten pop wieder nach oben, und den zweiten   Platte wird die Oberseite des Stapels.   Zwei wichtige Grundsätze sind   durch diese Metapher veranschaulicht: die Last   In First Out ist grundsätzlich ein; das   zweite ist, dass der Inhalt der   Stapel werden ausgeblendet. Nur die obere Platte   sichtbar ist, so zu sehen, was die ist   dritte Platte, die erste und zweite   Platten werden entfernt müssen. Diese   kann auch als FILO-First In geschrieben werden   Last Out, das heißt der Datensatz eingefügt   zuerst wird schließlich tauchte aus.

Answer 3

Für die zweite Frage: Assembler-Programmierer auf kleine Systemen neigen dazu, Code zu schreiben, die bei niedrigeren Adressen im Speicher beginnt, und zu höheren Adressen wachsen, da mehr Code hinzugefügt wird

.

Aus diesem Grund, so dass ein Stapel wachsen nach unten können Sie den Stapel an der Spitze des physikalischen Speichers starten und lassen Sie die zwei Speicherzonen aufeinander wachsen. Dies vereinfacht die Speicherverwaltung in dieser Art von trivialer Umgebung.

selbst in einem System mit getrennten ROM / RAM-Datenzuordnungen fixiert sind am leichtesten von unten aufbauen und damit den Codeabschnitt von der obigen Erläuterung ersetzen.

Während solche trivialen Speichersysteme mehr sehr selten sind, setzt die Hardware-Praxis etabliert.

Answer 4

Denken Sie daran, wie ein PEZ-Spender. Sie können einen neuen über schieben. Und dann knallen sie weg von der Spitze.

Das ist immer das, was ich denke, wenn ich denke, Push und Pop. (Wahrscheinlich nicht sehr historische though)

Sie fragen sich, was zum Teufel sind PEZ? Sehen Sie die Kommentare.

Answer 5

Alliteration ist immer attraktiv (siehe, was ich tat es?), Und diese Worte sind kurz, alliterative und suggestiv. Das gleiche gilt für die alten BASIC-Befehle Peek und Poke, was den zusätzlichen Vorteil der parallelen ks haben.

Eine gemeinsame physikalische Metapher ist eine Cafeteria Platte Spender, in dem ein federbelasteter Stapel von Platten macht es so, dass man eine Platte aus der Spitze erfolgen kann, aber die nächste Platte steigt in der gleichen Position sein.

Answer 6

Re Ihre „zweite triviale Frage“: Ich habe erhebliche Inkonsistenz gesehen bei der Definition, was „oben“ und „unten“ bedeuten! Von frühen Tagen, zogen einige Hersteller und Autoren Speicher Diagramme mit niedrigeren Adressen am oberen Rande der Seite (vermutlich imitiert die Reihenfolge, in dem eine Seite gelesen wird), während andere hohe Adressen an der Spitze der Seite legen (vermutlich Millimeterpapier Koordinaten nachahmen oder die Böden in einem Gebäude).

Natürlich ist das Konzept eines Stapels (und das Konzept des Speichers als auch) ist unabhängig von solchen visuellen Metaphern. Man kann einen Stapel implementieren, die in jeder Richtung „wächst“. In der Tat habe ich oft den Trick unten (in Bare-Metal-Level-Implementierungen) gesehen verwendet, um einen Bereich des Speichers zwischen zwei Stapeln zu teilen:

+---+---+--------   -------+--+--+--+
|   |   |   ->   ...   <-  |  |  |  |
+---+---+--------   -------+--+--+--+
^                                   ^
Stack 1      both stacks      Stack 2
base        "grow" toward        base
              the middle

Also meine Antwort ist, dass konzeptionell stapelt nie wachsen entweder „nach unten“ oder „nach oben“, sondern einfach von ihrer Basis wachsen. Ein einzelner Stapel sein kann implementiert in jede Richtung (oder in weder Richtung, wenn es eine verknüpfte Darstellung mit Garbage Collection verwenden, wobei in diesem Fall die Elemente sein können überall in nodespace).

Answer 7

Die Antworten auf dieser Seite ziemlich die Antwort Stapelrichtung Frage. Wenn ich es zusammenfassen müsste, würde ich sagen, dass es nach unten getan bleibt im Einklang mit alten Computern.

Answer 8

Ich denke, die ursprüngliche Geschichte, weil einige Entwickler über kam den Plattenstapel zu sehen (wie Sie oft in Buffet-Restaurants sehen). Sie schob eine neue Platte auf die Oberseite des Stapels, und man tauchte eine von der Spitze als auch.

Answer 9

In Bezug auf Stapel nach unten im Speicher wachsen, denken Sie daran, dass, wenn mit hierarchischen Datenstrukturen (Bäume) zu tun, die meisten Programmierer sind glücklich auf einer Seite mit der Basis zu ziehen (oder Stamm) am oberen Rande der Seite ...

Answer 10

Ich weiß, dass dieser Thread wirklich alt ist, aber ich habe einen Gedanken über die zweite Frage:

In meinem Kopf wächst der Stapel nach oben, obwohl die Speicheradressen zu verringern. Wenn Sie eine ganze Reihe von Zahlen auf einem Stück Papier zu schreiben, würden Sie in der oberen linken beginnen mit 0. Dann würden Sie die Zahlen steigen nach rechts nach links gehen, dann von oben nach unten. So sagt der Stapel ist wie folgt:

000 001 002 003 004     000 001 002 003 004     000 001 002 003 004
005 006 007 008 009     005 006 007 008 009     005 006 007 008 009
010 011 012 013 014     010 011 012 013 014     010 011 012 013 014
015 016 017 018 019     015 016 017 018 019     015 016 017 018 019
020 021 022 023 024     020 021 022 023 024     020 021 022 023 024
025 026 027 028 029     025 026 027 028 029     025 026 027 028 029

, wo die fetten Zahlen Stapelspeicher darstellen, und nicht fett Zahlen stellen Speicheradressen, die der Stack nicht. Jeder Block der gleichen Zahl steht für eine Phase eines Programms, wo der Call-Stack ist gewachsen.

Auch wenn die Speicheradressen nach unten bewegen, wobei der Stapel wächst nach oben.

In ähnlicher Weise mit den federbelasteten Plattenstapeln,
wenn Sie eine Platte aus der Spitze des Stapels nahm, nennen würde, dass die erste Platte (kleinste Zahl) nicht wahr? Auch dachte er die höchste nach oben. Ein Programmierer könnte es auch nennt die nulltee Platte.

Answer 11

Für die Frage, warum Stapel nach unten wachsen, ich kann es sich vorstellen würde, wird verwendet, um Speicherplatz zu sparen.

Wenn Sie von der Spitze des Stapelspeichers starten (der höchste Wert Adressen) und arbeiten bis auf Null, gehe ich davon aus ist es einfacher zu überprüfen, ob Sie Adresse $0x00000000 erreicht haben, als eine Variable Zuweisung Sie die maximale Höhe des Stapels geben und Prüfen, ob Sie diese Adresse erreicht haben.

Ich nehme an, dies macht es einfacher, zu überprüfen, ob Sie das Ende Ihrer adressierbaren Raum als egal sind erreicht, wie viel Speicher die Grenze des Stapels vorhanden ist immer $0x00000000 werden wird.