Pila (tipo de datos abstracto)

Tipo de datos abstracto

Para el uso del término LIFO en contabilidad, vea LIFO (contabilidad) . Para el uso del término pushdown en el entrenamiento de fuerza, consulte Pushdown (ejercicio) .

Para otros usos, consulte Stack (desambiguación) .

Similar a una pila de platos, agregar o quitar solo es posible en la parte superior.

Representación simple de un tiempo de ejecución de pila con operaciones push y pop .

En informática , una pila es un tipo de datos abstracto que sirve como una colección de elementos, con dos operaciones principales principales:

• Push , que agrega un elemento a la colección, y
• Pop , que elimina el elemento agregado más recientemente que aún no se eliminó.

El orden en el que los elementos salen de una pila da lugar a su nombre alternativo, LIFO ( último en entrar , primero en salir ). Además, una operación de inspección puede dar acceso a la parte superior sin modificar la pila. ^[1] El nombre "pila" para este tipo de estructura proviene de la analogía con un conjunto de elementos físicos apilados uno encima del otro. Esta estructura hace que sea fácil quitar un elemento de la parte superior de la pila, mientras que para llegar a un elemento más profundo en la pila puede ser necesario quitar varios otros elementos primero. ^[2]

Considerada como una estructura de datos lineal , o de manera más abstracta como una colección secuencial, las operaciones push y pop ocurren solo en un extremo de la estructura, conocido como la parte superior de la pila. Esta estructura de datos hace posible implementar una pila como una lista enlazada individualmente y un puntero al elemento superior. Se puede implementar una pila para tener una capacidad limitada. Si la pila está llena y no contiene suficiente espacio para aceptar la inserción de una entidad, se considera que la pila está en un estado de desbordamiento . La operación pop elimina un elemento de la parte superior de la pila.

Se necesita una pila para implementar la búsqueda en profundidad .

Historia

Véase también: Jan Łukasiewicz § Trabajo

Stacks entró en la literatura informática en 1946, cuando Alan M. Turing utilizó los términos "enterrar" y "desenterrar" como un medio para llamar y regresar de subrutinas. ^{[3] [4]} Las subrutinas ya se habían implementado en el Z4 de Konrad Zuse en 1945.

Klaus Samelson y Friedrich L. Bauer de la Universidad Técnica de Munich propusieron la idea de una pila en 1955 ^{[5] [6]} y presentaron una patente en 1957. ^{[7] [8] [9] [10]} En marzo de 1988, por la cual Cuando Samelson falleció, Bauer recibió el premio IEEE Computer Pioneer Award por la invención del principio de pila. ^{[11] [6]} Conceptos similares fueron desarrollados, independientemente, por Charles Leonard Hamblin en la primera mitad de 1954 ^[12] y por Wilhelm Kämmerer  [ de ] en 1958. ^{[13] [14]}

Las pilas se describen a menudo usando la analogía de una pila de platos cargada por resorte en una cafetería. ^{[15] [2] [16]} Los platos limpios se colocan en la parte superior de la pila, empujando hacia abajo los que ya están allí. Cuando se retira un plato de la pila, el que está debajo aparece para convertirse en el nuevo plato superior.

Operaciones no esenciales

En muchas implementaciones, una pila tiene más operaciones que las operaciones esenciales "push" y "pop". Un ejemplo de una operación no esencial es "top of stack", o "peek", que observa el elemento superior sin sacarlo de la pila. ^[17] Esto podría hacerse con un "pop" seguido de un "push" para devolver los mismos datos a la pila, por lo que no se considera una operación esencial. Si la pila está vacía, se producirá una condición de subdesbordamiento al ejecutar las operaciones "stack top" o "pop". Además, las implementaciones a menudo tienen una función que solo devuelve si la pila está vacía.

Pilas de software

Implementación

Una pila se puede implementar fácilmente a través de una matriz o una lista vinculada . Lo que identifica la estructura de datos como una pila, en cualquier caso, no es la implementación sino la interfaz: al usuario solo se le permite hacer estallar o insertar elementos en la matriz o lista vinculada, con algunas otras operaciones auxiliares. A continuación, se demostrarán ambas implementaciones, utilizando pseudocódigo .

Matriz

Se puede usar una matriz para implementar una pila (limitada), de la siguiente manera. El primer elemento, generalmente en el desplazamiento cero , es la parte inferior, lo que resulta en array[0]ser el primer elemento empujado hacia la pila y el último elemento salido. El programa debe realizar un seguimiento del tamaño (longitud) de la pila, utilizando una parte superior variable que registra el número de elementos empujados hasta el momento, por lo tanto, apunta al lugar en la matriz donde se insertará el siguiente elemento (asumiendo un cero- convención de índice basada). Por lo tanto, la pila en sí se puede implementar de manera efectiva como una estructura de tres elementos:

pila de estructura : maxsize: entero arriba: entero elementos: matriz de elementos

procedimiento inicializar (stk: pila, tamaño: entero): stk.items ← nuevo conjunto de elementos de tamaño , inicialmente vacío stk.maxsize ← tamaño stk.top ← 0

La operación de inserción agrega un elemento e incrementa el índice superior , después de verificar el desbordamiento:

procedimiento push (stk: stack, x: item): si stk.top = stk.maxsize: reportar error de desbordamiento otra cosa : stk.items [stk.top] ← x stk.top ← stk.top + 1

De manera similar, pop disminuye el índice superior después de verificar el subdesbordamiento y devuelve el elemento que anteriormente era el superior:

procedimiento pop (stk: stack): si stk.top = 0: reportar error de subdesbordamiento otra cosa : stk.top ← stk.top - 1 r ← stk.items [stk.top] volver r

Usando una matriz dinámica , es posible implementar una pila que puede crecer o reducirse tanto como sea necesario. El tamaño de la pila es simplemente el tamaño de la matriz dinámica, que es una implementación muy eficiente de una pila, ya que agregar elementos o eliminar elementos del final de una matriz dinámica requiere un tiempo O (1) amortizado.

Lista vinculada

Otra opción para implementar pilas es usar una lista enlazada individualmente . Una pila es entonces un puntero al "encabezado" de la lista, con quizás un contador para realizar un seguimiento del tamaño de la lista:

marco de estructura : datos: artículo siguiente: marco o nulo

pila de estructura : cabeza: marco o nulo tamaño: entero

procedimiento inicializar (stk: stack): stk.head ← nil stk.size ← 0

Empujar y hacer estallar elementos ocurre al principio de la lista; el desbordamiento no es posible en esta implementación (a menos que se agote la memoria):

procedimiento push (stk: stack, x: item): newhead ← nuevo marco newhead.data ← x newhead.next ← stk.head stk.head ← cabeza nueva stk.size ← stk.size + 1

procedimiento pop (stk: stack): si stk.head = nil: reportar error de subdesbordamiento r ← stk.head.data stk.head ← stk.head.next stk.size ← stk.size - 1 volver r

Pilas y lenguajes de programación

Algunos lenguajes, como Perl , LISP , JavaScript y Python , hacen que las operaciones de pila push y pop estén disponibles en sus tipos estándar de lista / matriz. Algunos lenguajes, en particular los de la familia Forth (incluido PostScript ), están diseñados en torno a pilas definidas por el lenguaje que son directamente visibles y manipuladas por el programador.

El siguiente es un ejemplo de manipulación de una pila en Common Lisp (" > " es el indicador del intérprete Lisp; las líneas que no comienzan con " > " son las respuestas del intérprete a las expresiones):

>  ( setf  stack  ( lista  'a  ' b  'c ))  ;; establezca la variable "pila" ( A  B  C ) >  ( pila emergente  ) ;; obtener el elemento superior (más a la izquierda), debería modificar la pila A > pila ;; comprobar el valor de la pila ( B C ) > ( empujar 'nueva pila ) ;; Empuje una nueva tapa en la pila ( NUEVO B C )          

Varios de los tipos de contenedores de la biblioteca estándar de C ++ tienen operaciones push_back y pop_back con semántica LIFO; Además, la clase de plantilla de pila adapta los contenedores existentes para proporcionar una API restringida con solo operaciones push / pop. PHP tiene una clase SplStack . La biblioteca de Java contiene una clase que es una especialización de . A continuación se muestra un programa de ejemplo en lenguaje Java , usando esa clase.StackVector

import  java.util.Stack ;class  StackDemo  {  public  static  void  main ( String [] args )  {  Stack < String >  stack  =  new  Stack < String > ();  apilar . empujar ( "A" );  // Inserta "A" en la pila de  pilas . empujar ( "B" );  // Insertar "B" en la pila de  pilas . empujar ( "C" );  // Insertar "C" en la  pila .empujar ( "D" );  // Insertar "D" en la pila  System . fuera . println ( pila . peek ());  // imprime la parte superior de la pila ( "D")  pila . pop ();  // quitando la  pila superior ("D") . pop ();  // eliminando la siguiente parte superior ("C")  } }

Pila de hardware

Artículo principal: asignación de memoria basada en pilas

Un uso común de las pilas a nivel de arquitectura es como un medio para asignar y acceder a la memoria.

Arquitectura básica de una pila

Una pila típica, que almacena datos locales e información de llamadas para llamadas a procedimientos anidados (no necesariamente procedimientos anidados ). Esta pila crece hacia abajo desde su origen. El puntero de la pila apunta al dato superior actual de la pila. Una operación de inserción reduce el puntero y copia los datos en la pila; una operación emergente copia datos de la pila y luego incrementa el puntero. Cada procedimiento llamado en el programa almacena información de retorno de procedimiento (en amarillo) y datos locales (en otros colores) empujándolos a la pila. Este tipo de implementación de pila es extremadamente común, pero es vulnerable a ataques de desbordamiento de búfer (consulte el texto).

Una pila típica es un área de la memoria de la computadora con un origen fijo y un tamaño variable. Inicialmente, el tamaño de la pila es cero. Un puntero de pila, generalmente en forma de registro de hardware, apunta a la ubicación referenciada más recientemente en la pila; cuando la pila tiene un tamaño de cero, el puntero de la pila apunta al origen de la pila.

Las dos operaciones aplicables a todas las pilas son:

• una operación de empuje , en la que un elemento de datos se coloca en la ubicación apuntada por el puntero de la pila, y la dirección en el puntero de la pila se ajusta por el tamaño del elemento de datos;
• un estallido o tirón operación: un elemento de datos en la ubicación actual a la que apunta el puntero de pila se elimina, y el puntero de pila se ajusta por el tamaño del elemento de datos.

Existen muchas variaciones sobre el principio básico de las operaciones de pila. Cada pila tiene una ubicación fija, en la memoria, en la que comienza. A medida que se agregan elementos de datos a la pila, el puntero de la pila se desplaza para indicar la extensión actual de la pila, que se expande desde el origen.

Los punteros de pila pueden apuntar al origen de una pila oa un rango limitado de direcciones, ya sea por encima o por debajo del origen (dependiendo de la dirección en la que crece la pila); sin embargo, el puntero de la pila no puede cruzar el origen de la pila. En otras palabras, si el origen de la pila está en la dirección 1000 y la pila crece hacia abajo (hacia las direcciones 999, 998, etc.), el puntero de la pila nunca debe incrementarse más allá de 1000 (a 1001, 1002, etc.). Si una operación emergente en la pila hace que el puntero de la pila se mueva más allá del origen de la pila, se produce un subdesbordamiento de la pila . Si una operación de inserción hace que el puntero de la pila aumente o disminuya más allá de la extensión máxima de la pila, se produce un desbordamiento de la pila .

Algunos entornos que dependen en gran medida de las pilas pueden proporcionar operaciones adicionales, por ejemplo:

• Duplicar : se abre el elemento superior y luego se vuelve a presionar (dos veces), de modo que ahora hay una copia adicional del elemento superior anterior en la parte superior, con el original debajo.
• Vistazo : el elemento superior se inspecciona (o se devuelve), pero el puntero de la pila y el tamaño de la pila no cambian (lo que significa que el elemento permanece en la pila). Esto también se denomina operación superior en muchos artículos.
• Intercambiar o intercambiar : los dos elementos superiores en la pila intercambian lugares.
• Rotar (o Rodar) : los n elementos superiores se mueven en la pila de forma rotatoria. Por ejemplo, si n = 3, los elementos 1, 2 y 3 de la pila se mueven a las posiciones 2, 3 y 1 de la pila, respectivamente. Son posibles muchas variantes de esta operación, siendo la más común la denominada rotación a la izquierda y rotación a la derecha.

Las pilas a menudo se visualizan creciendo de abajo hacia arriba (como las pilas del mundo real). También pueden visualizarse creciendo de izquierda a derecha, de modo que "superior" se convierte en "extremo derecho", o incluso creciendo de arriba hacia abajo. La característica importante es que la parte inferior de la pila está en una posición fija. La ilustración de esta sección es un ejemplo de visualización de crecimiento de arriba hacia abajo: la parte superior (28) es la pila "inferior", ya que la pila "superior" (9) es donde se empujan o sacan los elementos.

Un giro a la derecha moverá el primer elemento a la tercera posición, el segundo al primero y el tercero al segundo. Aquí hay dos visualizaciones equivalentes de este proceso:

manzana platanoplátano === girar a la derecha ==> pepinomanzana pepino

manzana pepinoplátano === girar a la izquierda ==> pepinomanzana platano

Una pila generalmente se representa en las computadoras por un bloque de celdas de memoria, con la "parte inferior" en una ubicación fija, y el puntero de la pila contiene la dirección de la celda "superior" actual en la pila. La terminología superior e inferior se utiliza independientemente de si la pila realmente crece hacia direcciones de memoria más bajas o hacia direcciones de memoria más altas.

Empujar un elemento en la pila ajusta el puntero de la pila por el tamaño del elemento (ya sea disminuyendo o incrementándose, dependiendo de la dirección en la que la pila crece en la memoria), apuntándolo a la siguiente celda y copia el nuevo elemento superior a el área de la pila. Dependiendo nuevamente de la implementación exacta, al final de una operación de inserción, el puntero de la pila puede apuntar a la siguiente ubicación no utilizada en la pila, o puede apuntar al elemento más alto de la pila. Si la pila apunta al elemento superior actual, el puntero de la pila se actualizará antes de que se inserte un nuevo elemento en la pila; si apunta a la siguiente ubicación disponible en la pila, se actualizará después de que el nuevo elemento se inserte en la pila.

Hacer estallar la pila es simplemente lo contrario de empujar. El elemento superior de la pila se elimina y el puntero de la pila se actualiza, en el orden opuesto al utilizado en la operación de inserción.

Apilar en la memoria principal

Muchos CISC de tipo CPU diseños, incluyendo el 86 , Z80 y 6502 , tienen un registro dedicado para su uso como la pila de llamadas puntero de pila con la convocatoria específica, a cambio, empuje, y el pop instrucciones que se actualizan de forma implícita el registro dedicado, lo que aumenta código de densidad. Algunos procesadores CISC, como el PDP-11 y el 68000 , también tienen modos de direccionamiento especiales para la implementación de pilas , normalmente también con un puntero de pila semidedicado (como A7 en el 68000). Por el contrario, la mayoría de RISC Los diseños de CPU no tienen instrucciones de pila dedicadas y, por lo tanto, la mayoría, si no todos, los registros se pueden usar como punteros de pila según sea necesario.

Apilar en registros o memoria dedicada

Artículo principal: máquina de apilar

La arquitectura de punto flotante x87 es un ejemplo de un conjunto de registros organizados como una pila donde también es posible el acceso directo a registros individuales (en relación con la parte superior actual). Al igual que con las máquinas basadas en pilas en general, tener la parte superior de la pila como argumento implícito permite una pequeña huella de código de máquina con un buen uso del ancho de banda del bus y las cachés de código , pero también evita algunos tipos de optimizaciones posibles en los procesadores que lo permitan. acceso aleatorio al archivo de registro para todos (dos o tres) operandos. Una estructura de pila también hace implementaciones superescalares con cambio de nombre de registro (para ejecución especulativa ) algo más complejo de implementar, aunque todavía es factible, como lo ejemplifican las implementaciones modernas de x87 .

Sun SPARC , AMD Am29000 e Intel i960 son ejemplos de arquitecturas que utilizan ventanas de registro dentro de una pila de registros como otra estrategia para evitar el uso de memoria principal lenta para argumentos de función y valores de retorno.

También hay una serie de pequeños microprocesadores que implementan una pila directamente en el hardware y algunos microcontroladores tienen una pila de profundidad fija a la que no se puede acceder directamente. Algunos ejemplos son los microcontroladores PIC , Computer Cowboys MuP21 , la línea Harris RTX y Novix NC4016 . Se utilizaron muchos microprocesadores basados ​​en pilas para implementar el lenguaje de programación Forth a nivel de microcódigo . Las pilas también se utilizaron como base de una serie de ordenadores centrales y miniordenadores . Estas máquinas se llamaban máquinas apiladoras , siendo la más famosa laBurroughs B5000 .

Aplicaciones de pilas

Evaluación de expresiones y análisis sintáctico

Las calculadoras que emplean la notación polaca inversa utilizan una estructura de pila para mantener los valores. Las expresiones se pueden representar en notaciones de prefijo, sufijo o infijo y la conversión de una forma a otra se puede realizar utilizando una pila. Muchos compiladores usan una pila para analizar la sintaxis de expresiones, bloques de programa, etc. antes de traducir a código de bajo nivel. La mayoría de los lenguajes de programación son lenguajes libres de contexto , lo que les permite ser analizados con máquinas basadas en pilas.

Retroceso

Artículo principal: Retroceso

Otra aplicación importante de las pilas es retroceder. Considere un ejemplo simple de cómo encontrar el camino correcto en un laberinto. Hay una serie de puntos, desde el punto de partida hasta el destino. Partimos de un punto. Para llegar al destino final, existen varios caminos. Supongamos que elegimos un camino aleatorio. Después de seguir un cierto camino, nos damos cuenta de que el camino que hemos elegido está equivocado. Por tanto, necesitamos encontrar una forma de volver al principio de ese camino. Esto se puede hacer con el uso de pilas. Con la ayuda de pilas, recordamos el punto al que hemos llegado. Esto se hace empujando ese punto en la pila. En caso de que terminemos en el camino equivocado, podemos sacar el último punto de la pila y así regresar al último punto y continuar nuestra búsqueda para encontrar el camino correcto. A esto se le llama retroceder.

El ejemplo prototípico de un algoritmo de retroceso es la búsqueda en profundidad , que encuentra todos los vértices de un gráfico a los que se puede llegar desde un vértice inicial especificado. Otras aplicaciones del retroceso implican la búsqueda en espacios que representan posibles soluciones a un problema de optimización. Branch and bound es una técnica para realizar tales búsquedas de retroceso sin buscar exhaustivamente todas las posibles soluciones en ese espacio.

Gestión de memoria de tiempo de compilación

Artículos principales: Asignación de memoria basada en pila y máquina de pila

Varios lenguajes de programación están orientados a la pila , lo que significa que definen la mayoría de las operaciones básicas (sumar dos números, imprimir un carácter) tomando sus argumentos de la pila y colocando los valores de retorno en la pila. Por ejemplo, PostScript tiene una pila de retorno y una pila de operandos, y también tiene una pila de estado de gráficos y una pila de diccionario. Muchas máquinas virtuales también están orientadas a pilas, incluida la máquina de código p y la máquina virtual Java .

Casi todas las convenciones de llamada ‍ — ‌ las formas en que las subrutinas reciben sus parámetros y devuelven resultados‍ — ‌usan una pila especial (la " pila de llamadas ") para contener información sobre la llamada y anidación de procedimientos / funciones con el fin de cambiar al contexto de la función llamada y restablecer la función de llamada cuando finalice la llamada. Las funciones siguen un protocolo de tiempo de ejecución entre la persona que llama y la persona que llama para guardar argumentos y devolver valor en la pila. Las pilas son una forma importante de admitir llamadas de función anidadas o recursivas . El compilador utiliza implícitamente este tipo de pila para admitir sentencias CALL y RETURN (o sus equivalentes) y el programador no la manipula directamente.

Algunos lenguajes de programación utilizan la pila para almacenar datos locales de un procedimiento. El espacio para los elementos de datos locales se asigna desde la pila cuando se ingresa al procedimiento y se desasigna cuando el procedimiento sale. El lenguaje de programación C generalmente se implementa de esta manera. El uso de la misma pila para llamadas de datos y procedimientos tiene importantes implicaciones de seguridad (ver más abajo) que un programador debe tener en cuenta para evitar introducir errores de seguridad graves en un programa.

Algoritmos eficientes

Varios algoritmos utilizan una pila (separada de la pila de llamadas de función habitual de la mayoría de los lenguajes de programación) como la estructura de datos principal con la que organizan su información. Éstos incluyen:

• Escaneo de Graham , un algoritmo para el casco convexo de un sistema bidimensional de puntos. Un casco convexo de un subconjunto de la entrada se mantiene en una pila, que se utiliza para encontrar y eliminar concavidades en el límite cuando se agrega un nuevo punto al casco. ^[18]
• Parte del algoritmo SMAWK para encontrar los mínimos de fila de una matriz monótona utiliza pilas de manera similar al escaneo de Graham. ^[19]
• Todos los valores más pequeños más cercanos , el problema de encontrar, para cada número en una matriz, el número anterior más cercano que sea más pequeño que él. Un algoritmo para este problema usa una pila para mantener una colección de candidatos para el valor más pequeño más cercano. Para cada posición en la matriz, la pila se abre hasta que se encuentra un valor más pequeño en su parte superior, y luego el valor en la nueva posición se empuja a la pila. ^[20]
• El algoritmo de la cadena del vecino más cercano , un método de agrupamiento jerárquico aglomerativo basado en el mantenimiento de una pila de grupos, cada uno de los cuales es el vecino más cercano de su predecesor en la pila. Cuando este método encuentra un par de clústeres que son vecinos más cercanos mutuos, se abren y se fusionan. ^[21]

Seguridad

Algunos entornos informáticos utilizan pilas de formas que pueden hacerlas vulnerables a ataques y brechas de seguridad . Los programadores que trabajan en estos entornos deben tener especial cuidado para evitar los errores de estas implementaciones.

Por ejemplo, algunos lenguajes de programación utilizan una pila común para almacenar tanto los datos locales de un procedimiento llamado como la información de enlace que permite que el procedimiento regrese a su llamador. Esto significa que el programa mueve datos dentro y fuera de la misma pila que contiene direcciones de retorno críticas para las llamadas a procedimientos. Si los datos se mueven a la ubicación incorrecta en la pila, o si un elemento de datos de gran tamaño se mueve a una ubicación de la pila que no es lo suficientemente grande para contenerlo, la información de retorno para las llamadas a procedimientos puede estar dañada, provocando que el programa falle.

Las partes malintencionadas pueden intentar un ataque de aplastamiento de la pila que aproveche este tipo de implementación al proporcionar una entrada de datos de gran tamaño a un programa que no verifica la longitud de la entrada. Dicho programa puede copiar los datos en su totalidad a una ubicación en la pila y, al hacerlo, puede cambiar las direcciones de retorno de los procedimientos que lo han llamado. Un atacante puede experimentar para encontrar un tipo específico de datos que se puedan proporcionar a dicho programa, de modo que la dirección de retorno del procedimiento actual se restablezca para apuntar a un área dentro de la propia pila (y dentro de los datos proporcionados por el atacante), que a su vez contiene instrucciones que llevan a cabo operaciones no autorizadas.

Este tipo de ataque es una variación del ataque de desbordamiento del búfer y es una fuente extremadamente frecuente de violaciones de seguridad en el software, principalmente porque algunos de los compiladores más populares usan una pila compartida para llamadas de datos y procedimientos, y no verifican la longitud de elementos de datos. Con frecuencia, los programadores tampoco escriben código para verificar el tamaño de los elementos de datos, y cuando se copia en la pila un elemento de datos de tamaño demasiado grande o insuficiente, puede producirse una infracción de seguridad.

Ver también

• Lista de estructuras de datos
• Cola
• Cola de dos extremos
• FIFO (informática y electrónica)
• Asignación de memoria basada en pilas
• Desbordamiento de pila
• Lenguaje de programación orientado a pilas

Referencias

1. Por el contrario, una COLA simple opera FIFO ( primero en entrar , primero en salir ).
2. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03384-4.
3. Turing, Alan Mathison (1946-03-19) [1945], Propuestas para el desarrollo en la división de matemáticas de un motor de cálculo automático (ACE) (NB. Presentado el 19 de marzo de 1946 ante el Comité Ejecutivo del Laboratorio Nacional de Física (Gran Bretaña).)
4. Carpintero, Brian Edward ; Doran, Robert William (1 de enero de 1977) [octubre de 1975]. "La otra máquina de Turing" . The Computer Journal . 20 (3): 269-279. doi : 10.1093 / comjnl / 20.3.269 . (11 páginas)
5. Samelson, Klaus (1957) [1955]. Escrito en Internationales Kolloquium über Probleme der Rechentechnik, Dresden, Alemania. Probleme der Programmierungstechnik (en alemán). Berlín, Alemania: VEB Deutscher Verlag der Wissenschaften . págs. 61–68.(NB. Este artículo se presentó por primera vez en 1955. Describe una pila de números ( Zahlenkeller ), pero la denomina memoria auxiliar lineal ( linearer Hilfsspeicher ).)
6. Fothe, Michael; Wilke, Thomas, eds. (2015). Keller, Stack und automatisches Gedächtnis - eine Struktur mit Potenzial (PDF) (Tagungsband zum Kolloquium 14 de noviembre de 2014 en Jena). Serie GI: Lecture Notes in Informática (LNI) - Temática (en alemán). T-7 . Bonn, Alemania: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag GmbH. ISBN  978-3-88579-426-4. Archivado (PDF) desde el original el 12 de abril de 2020 . Consultado el 12 de abril de 2020 . (77 páginas)
7. Bauer, Friedrich Ludwig ; Samelson, Klaus (30 de marzo de 1957). "Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens" (en alemán). Munich, Alemania: Deutsches Patentamt. DE-PS 1094019 . Consultado el 1 de octubre de 2010 .
8. Bauer, Friedrich Ludwig ; Goos, Gerhard (1982). Informatik - Eine einführende Übersicht (en alemán). Parte 1 (3 ed.). Berlín: Springer-Verlag . pag. 222. ISBN 3-540-11722-9. Die Bezeichnung 'Keller' hierfür wurde von Bauer und Samelson in einer deutschen Patentanmeldung vom 30. März 1957 eingeführt.
9. Samelson, Klaus ; Bauer, Friedrich Ludwig (1959). "Sequentielle Formelübersetzung" [Traducción secuencial de fórmulas]. Elektronische Rechenanlagen (en alemán). 1 (4): 176–182.
10. Samelson, Klaus ; Bauer, Friedrich Ludwig (1960). "Traducción secuencial de fórmulas". Comunicaciones de la ACM . 3 (2): 76–83. doi : 10.1145 / 366959.366968 . S2CID 16646147 . 
11. "IEEE-Computer-Pioneer-Preis - Bauer, Friedrich L." Universidad Técnica de Munich , Facultad de Ciencias de la Computación. 1989-01-01. Archivado desde el original el 7 de noviembre de 2017.
12. Hamblin, Charles Leonard (mayo de 1957). Un esquema de codificación sin direcciones basado en notación matemática (PDF) (mecanografiado). Universidad Tecnológica de Nueva Gales del Sur . págs. 121-1–121-12. Archivado (PDF) desde el original el 12 de abril de 2020 . Consultado el 12 de abril de 2020 . (12 páginas)
13. Kämmerer, Wilhelm (1958). Ziffern-Rechenautomat mit Programmierung nach Mathischem Formelbild (Tesis de habilitación) (en alemán). Friedrich-Schiller-Universität , Jena, Alemania.
14. Kämmerer, Wilhelm (1960). Ziffernrechenautomaten . Elektronisches Rechnen und Regeln (en alemán). 1 . Berlín, Alemania: Akademie-Verlag .
15. Ball, John A. (1978). Algoritmos para calculadoras RPN (1 ed.). Cambridge, Massachusetts, EE. UU .: Wiley-Interscience , John Wiley & Sons, Inc. ISBN  978-0-471-03070-6.
16. Dioses, Atul P .; Godse, Deepali A. (1 de enero de 2010). Arquitectura informática . Publicaciones técnicas. págs. 1-56. ISBN 978-8-18431534-9. Consultado el 30 de enero de 2015 .
17. Horowitz, Ellis: "Fundamentos de estructuras de datos en Pascal", página 67. Computer Science Press, 1984
18. Graham, RL (1972). Un algoritmo eficiente para determinar el casco convexo de un conjunto plano finito . Cartas de procesamiento de información 1, 132-133
19. Aggarwal, Alok; Klawe, Maria M .; Moran, Shlomo ; Shor, Peter ; Wilber, Robert (1987), "Aplicaciones geométricas de un algoritmo de búsqueda de matrices", Algorithmica , 2 (1-4): 195-208, doi : 10.1007 / BF01840359 , MR 0895444 , S2CID 7932878  .
20. Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993), "Algoritmos paralelos doblemente logarítmicos óptimos basados ​​en encontrar todos los valores más pequeños más cercanos", Journal of Algorithms , 14 (3): 344–370, CiteSeerX 10.1.1.55.5669 , doi : 10.1006 / jagm.1993.1018 .
21. Murtagh, Fionn (1983), "Un estudio de los avances recientes en algoritmos de agrupamiento jerárquico" (PDF) , The Computer Journal , 26 (4): 354–359, doi : 10.1093 / comjnl / 26.4.354 .

•  Este artículo incorpora material de dominio público  del  documento NIST :  Black, Paul E. "Bounded stack" . Diccionario de algoritmos y estructuras de datos .

Lectura adicional

• Donald Knuth . El arte de la programación informática , volumen 1: algoritmos fundamentales , tercera edición. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Sección 2.2.1: Pilas, Colas y Deques, págs. 238–243. 

Enlaces externos

Wikimedia Commons tiene medios relacionados con estructuras de datos de pila .

Wikilibros tiene un libro sobre el tema: Estructuras de datos / Pilas y colas

• Stack Machines: la nueva ola
• Profundidad de la pila delimitadora
• Análisis del tamaño de la pila para programas controlados por interrupciones (322 KB)