Pilas: ¿por qué PUSH y POP?

Question

Me preguntaba por qué usamos los términos " empujar " y "pop" para agregar / quitar elementos de las pilas? ¿Hay alguna metáfora física que haya hecho que esos términos sean comunes?

La única sugerencia que tengo es algo así como una revista de resorte para una pistola , donde las rondas se "empujan" en él y puede ser "aparecido" fuera, pero eso parece un poco improbable.

Una segunda pregunta trivial de la pila: ¿Por qué la mayoría de las CPU implementan la pila de llamadas a medida que crecen hacia abajo en la memoria, en lugar de hacia arriba?

Answer 1

Creo que la pila de placas con resorte es correcta, ya que es la fuente del término PUSH y POP.

En particular, la cafetería East Campus Commons en el MIT tenía pilas de placas cargadas con resorte en el marco de tiempo de 1957-1967. Los términos PUSH y POP habrían sido utilizados por el Tech Model Railroad Club. Creo que este es el origen.

El Tech Model Railroad Club definitivamente influyó en el diseño del PDP-6 de Digital Equipment Corporation (DEC). El 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

Answer 2

Para su segunda pregunta, Wikipedia tiene un artículo sobre la filosofía de CS que controla la pila:

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

Y por primera vez, también en wikipedia:

  

Una metáfora de uso frecuente es la idea.   de una pila de platos en un resorte   Pila de cafetería cargada. En semejante   apilar, solo la placa superior es visible   y accesible para el usuario, todos los demás   Las placas permanecen ocultas. Como nuevos platos   se añaden, cada nueva placa se convierte en el   parte superior de la pila, ocultando cada plato   Abajo, empujando la pila de platos.   abajo. A medida que se retira la placa superior de   la pila, se pueden utilizar, la   las placas vuelven a aparecer, y la segunda   placa se convierte en la parte superior de la pila.   Dos principios importantes son   Ilustrado por esta metáfora: la última.   En principio, el principio es uno; la   segundo es que el contenido de la   la pila está oculta. Solo la placa superior   es visible, así que para ver qué hay en el   tercer plato, el primero y el segundo   Las placas deberán ser retiradas. Esta   También se puede escribir como FILO-First In   Última salida, es decir, el registro insertado   La primera se abrirá al fin.

Answer 3

Para la segunda pregunta: los programadores de 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 ROM / RAM segregada, las asignaciones de datos fijas son más fáciles de construir de abajo hacia arriba y, por lo tanto, reemplazan la parte del código de la explicación anterior.

Aunque estos esquemas de memoria trivial son muy raros, la práctica del hardware continúa según lo establecido.

Answer 4

Piense en ello como un dispensador de gasolina. Puede empujar uno nuevo en la parte superior. Y luego sácalo de la parte superior.

Eso es siempre lo que pienso cuando pienso en empujar y hacer estallar. (Probablemente no muy histórico)

¿Se está preguntando qué diablos son PEZ? Vea los comentarios.

Answer 5

La aliteración siempre es atractiva (¿ves lo que hice allí?), y estas palabras son cortas, aliterativas y sugerentes. Lo mismo ocurre con los antiguos comandos BASIC peek y poke, que tienen la ventaja adicional de las k paralelas.

Una metáfora física común es un dispensador de placas de cafetería, donde una pila de placas con resorte hace que puedas sacar una placa de la parte superior, pero la siguiente placa se levanta para estar en la misma posición.

Answer 6

Re su "segunda pregunta trivial": he visto una considerable inconsistencia en la definición de qué "arriba" y " abajo " ¡media! Desde los primeros días, algunos fabricantes y autores dibujaron diagramas de memoria con direcciones bajas en la parte superior de la página (presumiblemente imitando el orden en que se lee una página), mientras que otros pusieron direcciones altas en la parte superior de la página (presumiblemente imitando coordenadas de papel cuadriculado o los pisos en un edificio).

Por supuesto, el concepto de 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 siguiente truco (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 " pero simplemente crecen desde su base. Una pila individual puede ser implementada en cualquier dirección (o en ninguna , si está utilizando una representación vinculada con recolección de basura, en cuyo caso los elementos pueden estar en cualquier lugar en el espacio de nodos).

Answer 7

Las respuestas en esta página prácticamente responden pregunta de dirección de pila. Si tuviera que resumirlo, diría que se hace hacia abajo para mantener la coherencia con las computadoras antiguas.

Answer 8

Creo que la historia original se produjo porque algunos desarrolladores vieron la pila de platos (como se ve en los restaurantes de buffet). Usted colocó una nueva placa en la parte superior de la pila y también sacó una de la parte superior.

Answer 9

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 una en una página con la base (o tronco) en la parte superior de la página ...

Answer 10

Sé que este hilo es muy antiguo, pero tengo una idea sobre la segunda pregunta:

En mi mente, 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 parte superior izquierda, con 0. Luego aumentaría los números de izquierda a derecha y luego de arriba a abajo. Así que 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 la pila, y los números en negrita representan las direcciones de memoria que la pila no está utilizando. Cada bloque de los mismos números representa una etapa de un programa donde la pila de llamadas ha crecido.

Aunque las direcciones de memoria se mueven hacia abajo, la pila crece hacia arriba.

Del mismo modo, con la pila de placas cargada por 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 es el más alto. Un programador podría incluso llamarlo la placa cero.

Answer 11

Para la pregunta de por qué las pilas disminuyen, me imagino que se usa para ahorrar memoria.

Si comienza desde la parte superior de la memoria de la pila (las direcciones con el valor más alto) y baja a cero, asumo que es más fácil verificar si ha alcanzado la dirección $ 0x00000000 que asignar una variable a darle la altura máxima de la pila y verificar si ha alcanzado o no esa dirección.

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á $ 0x00000000 .