Стеки - почему PUSH и POP?

Question

Мне было интересно, почему мы используем термины «push» и «pop» для добавления / удаления элементов из стеков? Есть ли какая-то физическая метафора, которая привела к тому, что эти термины стали общими?

Единственное предложение, которое у меня есть, это что-то вроде подпружиненного магазина для пистолета , где патроны "проталкиваются" в него и могут быть "выдвинуты", но это кажется маловероятным.

Второй вопрос о пустяках стека: почему большинство процессоров реализуют стек вызовов как растущий вниз в памяти, а не вверх?

Answer 1

На ваш второй вопрос в Wikipedia есть статья о философии CS, которая контролирует стек:

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

И для первого, тоже в википедии:

Часто используемая метафора - идея стопки тарелок в пружине загружен кафетерий стека. В таком стек, видна только верхняя пластина и доступны для пользователя, все остальные тарелки остаются скрытыми. Как новые тарелки добавляются, каждая новая пластина становится вершина стека, скрывающая каждую тарелку ниже, толкая стопку тарелок вниз. Поскольку верхняя пластина снята с стек, они могут быть использованы, тарелки выскакивают, а вторая пластина становится вершиной стека. Два важных принципа иллюстрируется этой метафорой: последний Принцип First Out один; во-вторых, что содержание Стек спрятан. Только верхняя пластина видно, чтобы увидеть, что на третья пластина, первая и вторая пластины должны быть удалены. это также можно записать как FILO-First In Last Out, т.е. вставленная запись первый будет выдавлен наконец.

Answer 2

По второму вопросу: программисты на ассемблере в небольших системах, как правило, пишут код, который начинается с низких адресов в памяти и увеличивается до более высоких адресов по мере добавления кода.

Из-за этого увеличение стека вниз позволяет запустить стек в верхней части физической памяти и позволить двум зонам памяти расти друг к другу. Это упрощает управление памятью в такой тривиальной среде.

Даже в системе с разделенными ПЗУ / ОЗУ фиксированное распределение данных проще всего построить снизу вверх и, таким образом, заменить часть кода вышеприведенного объяснения.

Хотя такие тривиальные схемы памяти уже встречаются очень редко, аппаратная практика продолжается, как установлено.

Answer 3

Я считаю, что подпружиненная стопка тарелок является правильной, как источник для терминов PUSH и POP.

В частности, в кафетерии East Campus Commons в Массачусетском технологическом институте были загружены пружинные стопки тарелок в период 1957-1967 гг. Термины PUSH и POP использовались бы Техническим модельным железнодорожным клубом. Я думаю, что это происхождение.

Технический железнодорожный клуб модели определенно повлиял на дизайн PDP-6 корпорации Digital Equipment Corporation (DEC). PDP-6 была одной из первых машин, в которой аппаратные инструкции были ориентированы на стек. Инструкции были PUSH, POP, PUSHJ, POPJ.

http://ed -thelen.org / сост-истор / ПРП-6.html # Special% 20Features

Answer 4

Думайте об этом как о дозаторе. Вы можете нажать новый сверху. А потом вытолкни его сверху.

Это всегда то, о чем я думаю, когда я думаю о пуше и поп-музыке. (Вероятно, не очень исторический, хотя)

Вы спрашиваете себя, какого черта PEZ? Смотрите комментарии.

Answer 5

Относительно вашего «второго тривиального вопроса»: я видел существенную непоследовательность в определении того, что означают «вверх» и «вниз»! С самого начала некоторые производители и авторы рисовали диаграммы памяти с низкими адресами в верхней части страницы (предположительно, имитируя порядок чтения страницы), в то время как другие помещали высокие адреса в верхней части страницы (предположительно, имитируя координаты миллиметровки). или полы в здании).

Конечно, концепция стека (и концепция адресуемой памяти) не зависит от таких визуальных метафор. Можно реализовать стек, который «растет» в любом направлении. Фактически, я часто видел уловку ниже (в реализациях на уровне «голого металла»), используемую для разделения области памяти между двумя стеками:

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

Так что мой ответ таков: концептуально стеки никогда не растут ни "вниз", ни "вверх", а просто растут из своей базы. Отдельный стек может быть реализован в любом направлении (или в или направлении, если он использует связанное представление со сборкой мусора, в этом случае элементы могут быть в любом месте в пространстве узлов).

Answer 6

Аллитерация всегда привлекательна (видите, что я там делал?), И эти слова короткие, аллитеративные и наводящие на размышления. То же самое касается старых базовых команд peek и poke, которые имеют дополнительное преимущество по сравнению с параллельными k.

Обычная физическая метафора - это раздаточная тарелка для столовой, в которой подпружиненная стопка тарелок позволяет вынимать тарелку с верха, но следующая тарелка поднимается, чтобы оказаться в том же положении.

Answer 7

Ответы на этой странице в значительной степени отвечают на вопрос о направлении стека. Если бы мне пришлось подвести итог, я бы сказал, что это делается вниз, чтобы соответствовать древним компьютерам.

Answer 8

На вопрос, почему стеки растут, я бы подумал, что это используется для экономии памяти.

Если вы начинаете с вершины стековой памяти (адреса с наибольшим значением) и работаете до нуля, я предполагаю, что проще проверить, достиг ли вы адрес $0x00000000, чем выделять переменную, чтобы получить максимальную высоту стек и проверка, достигли ли вы этого адреса.

Полагаю, это облегчает проверку достижения конца адресного пространства, поскольку независимо от того, сколько памяти доступно, предел стека всегда будет $0x00000000.

Answer 9

Я знаю, что эта ветка действительно старая, но у меня есть мысль о втором вопросе:

На мой взгляд, стек растет, хотя адреса памяти уменьшаются. Если бы вы написали целую кучу цифр на листе бумаги, вы бы начали с левого верхнего угла, с 0. Затем вы увеличивали бы числа слева направо, затем сверху вниз. Скажем, стек выглядит так:

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 <b>006 007 008 009</b>
010 011 012 013 014     010 011 012 013 014     <b>010 011 012 013 014</b>
015 016 017 018 019     015 016 <b>017 018 019     015 016 017 018 019</b>
020 021 022 <b>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</b>

где полужирные числа представляют память стека, а полужирные числа представляют адреса памяти, которые стек не использует. Каждый блок с одинаковыми номерами представляет собой этап программы, где стек вызовов вырос.

Несмотря на то, что адреса памяти перемещаются вниз, стек растет вверх.

Аналогично, с подпружиненным стеком пластин,
если бы вы сняли тарелку с вершины стека, вы бы назвали это первой тарелкой (наименьшим числом), верно? Даже думал, что это наивысший. Программист может даже назвать это нулевой табличкой.

Answer 10

Что касается стеков, растущих вниз в памяти, помните, что, имея дело с иерархическими структурами данных (деревьями), большинство программистов с удовольствием рисуют один на странице с основанием (или стволом) вверху страницы ...