example - Stacks: ¿por qué PUSH y POP?
stack java (11)
Me preguntaba por qué usamos los términos "push" y "pop" para agregar / eliminar elementos de las pilas. ¿Hay alguna metáfora física que haga que esos términos sean comunes?
La única sugerencia que tengo es algo así como una revista con resorte para una pistola , donde las rondas son "empujadas" hacia adentro y pueden ser "reventadas", pero eso parece un poco improbable.
Una segunda pregunta de pila de trivia: ¿Por qué la mayoría de las CPU implementan la pila de llamadas como crecer hacia abajo en la memoria, en lugar de hacia arriba?
Con respecto a su "segunda pregunta trivial": ¡he visto una considerable incoherencia al definir qué significa "subir" y "bajar"! Desde los primeros días, algunos fabricantes y autores dibujaban diagramas de memoria con direcciones bajas en la parte superior de la página (supuestamente imitando el orden en que se lee una página), mientras que otros colocaban direcciones altas en la parte superior de la página (probablemente imitando coordenadas de papel cuadriculado o los pisos en un edificio).
Por supuesto, el concepto de una pila (y el concepto de memoria direccionable también) es independiente de tales metáforas visuales. Uno puede implementar una pila que "crece" en cualquier dirección. De hecho, a menudo he visto el truco a continuación (en implementaciones de nivel básico) utilizado para compartir una región de memoria entre dos pilas:
+---+---+-------- -------+--+--+--+
| | | -> ... <- | | | |
+---+---+-------- -------+--+--+--+
^ ^
Stack 1 both stacks Stack 2
base "grow" toward base
the middle
Entonces mi respuesta es que las pilas conceptualmente nunca crecen "hacia abajo" o "hacia arriba" sino que simplemente crecen desde su base. Se puede implementar una pila individual en cualquier dirección (o en ninguna dirección, si está utilizando una representación vinculada con la recolección de elementos no utilizados, en cuyo caso los elementos pueden estar en cualquier parte del espacio vacío).
Creo que la historia original surgió debido a que algunos desarrolladores vieron la pila de platos (como suele ver en los restaurantes buffet). Empujaste un nuevo plato a la parte superior de la pila, y también sacaste uno de la parte superior.
Creo que la pila de placas con resorte es correcta, como la fuente para el término PUSH y POP.
En particular, la Cafetería East Campus Commons en el MIT tenía pilas de placas cargadas por resorte en el marco temporal de 1957-1967. Los términos PUSH y POP habrían estado en uso por el Tech Model Railroad Club. Creo que este es el origen.
El Tech Model Railroad Club definitivamente influyó en el diseño de Digital Equipment Corporation (DEC) PDP-6. La PDP-6 fue una de las primeras máquinas en tener instrucciones orientadas a la pila en el hardware. Las instrucciones fueron PUSH, POP, PUSHJ, POPJ.
http://ed-thelen.org/comp-hist/pdp-6.html#Special%20Features
En cuanto a las pilas que crecen hacia abajo en la memoria, recuerde que cuando se trata de estructuras de datos jerárquicas (árboles), la mayoría de los programadores están felices de dibujar uno en una página con la base (o tronco) en la parte superior de la página ...
La aliteración siempre es atractiva (¿ves lo que hice allí?), Y estas palabras son cortas, aliterativas y sugestivas. Lo mismo ocurre con los viejos comandos BASIC peek y poke, que tienen la ventaja adicional de los k paralelos.
Una metáfora física común es un dispensador de plato de cafetería, donde una pila de placas con carga de resorte lo hace para que pueda sacar un plato de la parte superior, pero la siguiente placa se levanta para estar en la misma posición.
Las respuestas en esta página responden bastante a la pregunta de la dirección de pila. Si tuviera que resumirlo, diría que se hace a la baja para mantener la coherencia con las computadoras antiguas.
Para la segunda pregunta: los programadores ensambladores en sistemas pequeños tienden a escribir código que comienza en direcciones bajas en la memoria, y crecen a direcciones más altas a medida que se agrega más código.
Debido a esto, hacer que una pila crezca hacia abajo le permite iniciar la pila en la parte superior de la memoria física y permitir que las dos zonas de memoria crezcan una hacia la otra. Esto simplifica la administración de la memoria en este tipo de entorno trivial.
Incluso en un sistema con segregación de ROM / RAM, las asignaciones de datos fijos son más fáciles de construir desde abajo hacia arriba y, por lo tanto, reemplazan la parte del código de la explicación anterior.
Si bien estos esquemas de memoria triviales son muy raros, la práctica del hardware continúa según lo establecido.
Para su segunda pregunta, Wikipedia tiene un artículo sobre la filosofía CS que controla la pila:
http://en.wikipedia.org/wiki/LIFO
Y para el primero, también en wikipedia:
Una metáfora de uso frecuente es la idea de una pila de platos en una pila de cafetería con resorte. En tal apilamiento, solo la placa superior es visible y accesible para el usuario, todas las demás placas permanecen ocultas. A medida que se agregan placas nuevas, cada placa nueva se convierte en la parte superior de la pila, ocultando cada placa debajo, empujando la pila de placas hacia abajo. A medida que la placa superior se retira de la pila, se pueden usar, las placas se abren hacia arriba y la segunda placa se convierte en la parte superior de la pila. La metáfora ilustra dos principios importantes: el principio del Último en entrar es uno; el segundo es que el contenido de la pila está oculto. Solo la placa superior es visible, por lo que para ver qué hay en la tercera placa, la primera y la segunda placa tendrán que ser retiradas. Esto también se puede escribir como FILO-First In Last Out, es decir, el registro insertado primero se abrirá al final.
Piense en ello como un dispensador de pez. Puedes empujar uno nuevo en la parte superior. Y luego sal de la parte superior.
Eso es siempre lo que pienso cuando pienso push and pop. (Probablemente no sea muy histórico)
¿Te estás preguntando qué diablos son PEZ? Ver los comentarios.
Sé que este hilo es muy viejo, pero tengo un pensamiento sobre la segunda pregunta:
En mi opinión, la pila crece, a pesar de que las direcciones de memoria disminuyen. Si tuviera que escribir un montón de números en una hoja de papel, comenzaría en la esquina superior izquierda, con 0. Luego, aumentaría los números de izquierda a derecha y luego de arriba a abajo. Entonces di que la pila es así:
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
donde los números en negrita representan la memoria de pila, y los números sin negrita representan direcciones de memoria que la pila no está usando. Cada bloque de los mismos números representa una etapa de un programa donde la pila de llamadas ha crecido.
A pesar de que las direcciones de memoria se mueven hacia abajo, la pila está creciendo hacia arriba.
Del mismo modo, con la pila de placas con resorte,
si sacaste un plato de la parte superior de la pila, lo llamarías el primer plato (el número más pequeño) ¿verdad? Incluso pensé que era el más alto. Un programador incluso podría llamarlo placa zeroth.
Para la pregunta de por qué crecen las pilas, me imagino que se usa para ahorrar memoria.
Si comienza desde la parte superior de la memoria de pila (las direcciones de mayor valor) y trabaja hasta cero, supongo que es más fácil verificar si ha alcanzado la dirección $0x00000000 que asignar una variable para darle la altura máxima de la pila y verificar ya sea que hayas llegado a esa dirección o no
Supongo que esto hace que sea más fácil verificar si está llegando al final de su espacio direccionable ya que no importa cuánta memoria esté disponible, el límite de la pila siempre será de $0x00000000 .