Мне было интересно, почему мы используем термины "push" и "pop" для добавления/удаления элементов из стеков? Есть ли какая-то физическая метафора, которая заставила эти термины быть обычными?
Единственное, что у меня есть, это что-то вроде spring -груженного журнала для пистолета, где раунды "вталкиваются" в него и можно "выскочить", но это кажется маловероятным.
Второй вопрос о стеке: почему большинство процессоров реализуют стек вызовов как растущий вниз в памяти, а не вверх?
Я полагаю, что загруженный стоп-лист spring правильный, как источник для термина PUSH и POP.
В частности, Восточная кампусская палата общин в Массачусетском технологическом институте имела spring загруженные стопки пластин в период с 1957 по 1967 год. Термины PUSH и POP использовались в Tech Rail Rail Club. Я думаю, что это источник.
The Tech Model Railroad Club определенно повлиял на дизайн Digital Equipment Corporation (DEC) PDP-6. PDP-6 был одним из первых машин, на которых были установлены инструкции, ориентированные на стек. Инструкции были PUSH, POP, PUSHJ, POPJ.
http://ed-thelen.org/comp-hist/pdp-6.html#Special%20Features
Для вашего второго вопроса в Википедии есть статья о философии CS, которая управляет стеком:
http://en.wikipedia.org/wiki/LIFO
И для первого, также в википедии:
Часто используемой метафорой является идея стопки пластин в springзагруженный столовый столик. В такой стек, видна только верхняя пластина и доступный пользователю, все остальные пластины остаются скрытыми. В качестве новых пластин добавляются, каждая новая пластина становится сверху стека, скрывая каждую пластину ниже, нажатие стопки пластин вниз. Поскольку верхняя пластина удаляется из стек, они могут использоваться, пластины появляются вверх, а вторая пластина становится вершиной стека. Два важных принципа: иллюстрируется этой метафорой: Последний В принципе "Первый выход" - один; во-вторых, содержание стек скрыты. Только верхняя пластина отображается, поэтому, чтобы увидеть, что находится на третья пластина, первая и вторая пластины должны быть удалены. Эта также может быть записано как FILO-First In Last Out, т.е. Вставленная запись сначала выскочит наконец.
Во втором вопросе: ассемблерные программисты на небольших системах склонны писать код, начинающийся с низких адресов в памяти, и увеличиваются до более высоких адресов по мере добавления большего количества кода.
Из-за этого, если стек стекается вниз, вы можете запустить стек в верхней части физической памяти и позволить двум зонам памяти расти друг к другу. Это упрощает управление памятью в такой тривиальной среде.
Даже в системе с выделенными ROM/RAM фиксированные распределения данных проще всего строить снизу вверх и, таким образом, заменять часть кода приведенного выше объяснения.
В то время как такие тривиальные схемы памяти очень редки, аппаратная практика продолжается, как установлено.
Подумайте об этом, как диспенсер Pez. Вы можете нажать на новый. И затем вытащите его сверху.
Это всегда то, о чем я думаю, когда думаю толчок и поп. (Вероятно, не очень исторический, хотя)
Вы спрашиваете себя, что такое PEZ? См. комментарии.
Аллитерация всегда привлекательна (см., что я там делал?), и эти слова короткие, аллитеративные и наводящие на размышления. То же самое относится к старым командам BASIC, которые выглядят и подталкиваются, что имеет дополнительное преимущество параллельных k.
Общая физическая метафора - это диспенсер для столовых приборов, где spring -груженная стопка пластин делает это так, что вы можете снять пластину сверху, но следующая пластина поднимается, чтобы находиться в том же положении.
Повторите свой "второй тривиальный вопрос": я видел значительную несогласованность в определении того, что означает "вверх" и "вниз"! С ранних дней некоторые производители и авторы рисовали диаграммы памяти с низкими адресами в верхней части страницы (предположительно имитируя порядок чтения страницы), в то время как другие помещали высокие адреса в верхней части страницы (предположительно имитируя координаты графической бумаги или полы в здании).
Конечно, понятие стека (и понятие адресной памяти также) не зависит от таких визуальных метафор. Можно реализовать стек, который "растет" в любом направлении. На самом деле, я часто видел трюк ниже (в реализациях на уровне белого), используемый для обмена областью памяти между двумя стеками:
+---+---+-------- -------+--+--+--+
| | | -> ... <- | | | |
+---+---+-------- -------+--+--+--+
^ ^
Stack 1 both stacks Stack 2
base "grow" toward base
the middle
Итак, мой ответ заключается в том, что стеки концептуально никогда не растут ни "вниз", ни "вверх", а просто растут со своей базы. Отдельный стек может быть реализован в любом направлении (или в любом направлении, если он использует связанное представление с сборкой мусора, и в этом случае элементы могут находиться где угодно в узловом пространстве).
Ответы на на этой странице в значительной степени отвечают на вопрос о направлении стека. Если бы мне пришлось подвести итог, я бы сказал, что это делается вниз, чтобы оставаться в соответствии с древними компьютерами.
Я думаю, что первоначальная история возникла из-за того, что некоторые разработчики увидели стопку пластинок (как вы часто видите в ресторанах буфета). Вы подтолкнули новую пластину к верхней части стека, и вы тоже вытащили ее сверху.
Что касается стеков, растущих вниз в памяти, помните, что при работе с иерархическими структурами данных (деревьями) большинство программистов с удовольствием рисуют один на странице с базой (или стволом) в верхней части страницы...
Я знаю, что эта ветка действительно старая, но я подумал о втором вопросе:
На мой взгляд, стек растет, хотя адреса памяти уменьшаются. Если бы вы написали целую кучу цифр на листе бумаги, вы бы начали в левом верхнем углу, с 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 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
где жирные цифры представляют стекную память, а нераспределенные числа представляют адреса памяти, которые стек не использует. Каждый блок с одинаковыми номерами представляет собой этап программы, в которой стек вызовов вырос.
Несмотря на то, что адреса памяти перемещаются вниз, стек растет вверх.
Аналогично, с загруженной таблицей с таблицей spring,
если вы сняли пластину с верхней части стека, вы бы назвали ее первой пластиной (наименьшим номером)? Даже думал, что это самое высокое. Программист может даже назвать его нулевой табличкой.
Для вопроса о том, почему стеки растут, я бы предположил, что он используется для сохранения памяти.
Если вы начинаете с верхней части памяти стека (адреса наивысшего значения) и работаете до нуля, я предполагаю, что проще проверить, достиг ли вы адрес $0x00000000, чем выделение переменной, чтобы дать вам максимальную высоту стек и проверить, достиг ли вы этого адреса.
Я предполагаю, что это облегчает проверку того, достигли ли вы конца вашего адресуемого пространства, независимо от того, сколько памяти доступно, предел стека всегда будет $0x00000000.