stringtranslate.com

Pila (tipo de datos abstracto)

De manera similar a una pila de platos, agregar o quitar solo es práctico 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:

Además, una operación de peek puede, sin modificar la pila, devolver el valor del último elemento añadido. El nombre pila es una analogía de un conjunto de elementos físicos apilados uno sobre otro, como una pila de platos.

El orden en el que se agrega o elimina un elemento de una pila se describe como último en entrar, primero en salir , al que se hace referencia mediante el acrónimo LIFO . [nb 1] Al igual que con una pila de objetos físicos, esta estructura facilita la extracción de un elemento de la parte superior de la pila, pero acceder a un dato más profundo en la pila puede requerir la eliminación de varios otros elementos primero. [1]

Considerada como una colección secuencial, una pila tiene un extremo que es la única posición en la que pueden ocurrir las operaciones de inserción y extracción, la parte superior de la pila, y está fija en el otro extremo, la parte inferior . Una pila puede implementarse, por ejemplo, como una lista enlazada simple con un puntero al elemento superior.

Se puede implementar una pila para que tenga una capacidad limitada. Si la pila está llena y no contiene suficiente espacio para aceptar otro elemento, la pila se encuentra en un estado de desbordamiento de pila .

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

Historia

Las pilas entraron en la literatura de la ciencia informática en 1946, cuando Alan Turing utilizó los términos "enterrar" y "desenterrar" como un medio para llamar y regresar de subrutinas. [2] [3] Las subrutinas y una pila de dos niveles ya se habían implementado en el Z4 de Konrad Zuse en 1945. [4] [5]

Klaus Samelson y Friedrich L. Bauer de la Universidad Técnica de Múnich propusieron la idea de una pila llamada Operationskeller ("sótano operativo") en 1955 [6] [7] y presentaron una patente en 1957. [8] [9] [10] [11] En marzo de 1988, cuando Samelson ya había fallecido, Bauer recibió el premio IEEE Computer Pioneer Award por la invención del principio de pila. [12] [7] Charles Leonard Hamblin desarrolló conceptos similares de forma independiente en la primera mitad de 1954 [13] [7] y Wilhelm Kämmerer  [de] con su automatisches Gedächtnis ("memoria automática") en 1958. [14] [15] [7]

Las pilas se describen a menudo utilizando la analogía de una pila de platos accionada por resorte en una cafetería. [16] [1] [17] Los platos limpios se colocan en la parte superior de la pila, empujando hacia abajo los platos que ya están allí. Cuando se retira el plato superior de la pila, el que está debajo se eleva 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 quitarlo de la pila. [18] Dado que esto se puede dividir en un "pop" seguido de un "push" para devolver los mismos datos a la pila, no se considera una operación esencial. Si la pila está vacía, se producirá una condición de desbordamiento al ejecutar las operaciones "stack top" o "pop". Además, muchas implementaciones proporcionan una verificación si la pila está vacía y una operación que devuelve su tamaño.

Pilas de software

Implementación

Una pila se puede implementar fácilmente a través de una matriz o una lista enlazada , ya que es simplemente un caso especial de una lista. [19] En cualquier caso, lo que identifica la estructura de datos como una pila no es la implementación sino la interfaz: al usuario solo se le permite insertar o sacar elementos de la matriz o lista enlazada, con algunas otras operaciones auxiliares. A continuación se demostrarán ambas implementaciones utilizando pseudocódigo .

Formación

Se puede utilizar 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]que sea el primer elemento que se inserta en la pila y el último que se extrae. El programa debe realizar un seguimiento del tamaño (longitud) de la pila, utilizando una variable top que registra la cantidad de elementos insertados hasta el momento, por lo tanto, apunta al lugar en la matriz donde se insertará el siguiente elemento (asumiendo una convención de índice basada en cero). Por lo tanto, la pila en sí se puede implementar de manera efectiva como una estructura de tres elementos:

pila de estructura : tamaño máximo: entero arriba: entero artículos: matriz de artículos
procedimiento initialize(stk: pila, tamaño: entero): stk.items ← nueva matriz de elementos de tamaño , inicialmente vacía stk.maxsize ← tamaño punto superior ← 0

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

procedimiento push(stk : pila, x : elemento): si stk.top = stk.maxsize: Informar de un error de desbordamiento demás : stk.items[stk.top] ← x stk.top ← stk.top + 1

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

procedimiento pop(stk : pila): si stk.top = 0: Informar de un error de desbordamiento demás : punto.arriba ← punto.arriba − 1 r ← stk.items[stk.top] volver r

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

Lista enlazada

Otra opción para implementar pilas es utilizar una lista enlazada simple . Una pila es entonces un puntero a la "cabeza" de la lista, con quizás un contador para llevar un registro 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 initialize(stk : pila): stk.cabeza ← nulo tamaño de pieza ← 0

La inserción y extracción de elementos se realiza al principio de la lista; el desbordamiento no es posible en esta implementación (a menos que se agote la memoria):

procedimiento push(stk : pila, x : elemento): newhead ← nuevo marco nuevo encabezado.datos ← x newhead.next ← stk.cabeza stk.head ← nuevohead tamaño de pieza ← tamaño de pieza + 1
procedimiento pop(stk : pila): si stk.head = nil: Informar de un error de desbordamiento r ← stk.cabeza.datos stk.cabeza ← stk.cabeza.siguiente tamaño de pieza ← tamaño de pieza - 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 de lista/array estándar. 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 de Lisp; las líneas que no comienzan con " > " son las respuestas del intérprete a las expresiones):

> ( setf stack ( list 'a 'b 'c )) ;; establece la variable "stack" ( A B C ) > ( pop stack ) ;; obtiene el elemento superior (más a la izquierda), debe modificar la pila A > stack ;; verifica el valor de stack ( B C ) > ( push 'new stack ) ;; inserta un nuevo elemento superior en la pila ( NEW 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 que utiliza esa clase.StackVector

importar java.util.Stack ; clase  StackDemo { public static void main ( String [] args ) { Stack < String > stack = new Stack < String > (); stack . push ( "A" ); // Insertar "A" en la pila stack . push ( "B" ); // Insertar "B" en la pila stack . push ( "C" ); // Insertar "C" en la pila stack . push ( "D" ); // Insertar "D" en la pila System . out . println ( stack . peek ()); // Imprime la parte superior de la pila ("D") stack . pop (); // Eliminando la parte superior ("D") stack . pop (); // Eliminando la siguiente parte superior ("C") } }

Pila de hardware

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

Arquitectura básica de una pila

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 procesador ) apunta a la ubicación de la pila a la que se hizo referencia más recientemente; cuando la pila tiene un tamaño de cero, el puntero de pila apunta al origen de la pila.

Las dos operaciones aplicables a todas las pilas son:

Existen muchas variaciones del 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 a partir del origen.

Los punteros de pila pueden apuntar al origen de una pila o a un rango limitado de direcciones por encima o por debajo del origen (dependiendo de la dirección en la que crece la pila); sin embargo, el puntero de 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 pila nunca debe incrementarse más allá de 1000 (hasta 1001 o más allá). Si una operación de extracción en la pila hace que el puntero de pila se mueva más allá del origen de la pila, se produce un desbordamiento de pila . Si una operación de inserción hace que el puntero de pila aumente o disminuya más allá de la extensión máxima de la pila, se produce un desbordamiento de pila .

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

Las pilas se visualizan a menudo creciendo de abajo hacia arriba (como las pilas del mundo real). También se pueden visualizar creciendo de izquierda a derecha, donde la parte superior está en el 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 una visualización de crecimiento de arriba hacia abajo: la parte superior (28) es la parte "inferior" de la pila, ya que la parte "superior" de la pila (9) es desde donde se empujan o extraen los elementos.

Una rotación hacia la derecha moverá el primer elemento a la tercera posición, el segundo a la primera y el tercero a la segunda. A continuación se muestran dos visualizaciones equivalentes de este proceso:

manzana plátanoplátano ===rotación derecha==> pepinopepino manzana
pepino manzanaplátano ===rotación a la izquierda==> pepinomanzana plátano

En las computadoras, una pila suele representarse mediante un bloque de celdas de memoria, con la "base" en una ubicación fija y el puntero de pila que contiene la dirección de la celda "superior" actual en la pila. La nomenclatura "superior" e "inferior" se utiliza independientemente de si la pila realmente crece hacia direcciones de memoria superiores.

Al insertar un elemento en la pila, el puntero de la pila se ajusta según el tamaño del elemento (ya sea decrementándolo o incrementándolo, según la dirección en la que crece la pila en la memoria), apuntándolo a la siguiente celda y copiando el nuevo elemento superior en 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 superior en 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 se inserte el nuevo elemento en la pila.

Sacar la pila es simplemente lo inverso de empujarla. Se quita el elemento superior de la pila y se actualiza el puntero de la pila, en el orden opuesto al utilizado en la operación de empujar.

Pila en memoria principal

Muchos diseños de CPU de tipo CISC , incluidos los x86 , Z80 y 6502 , tienen un registro dedicado para su uso como puntero de pila de llamadas con instrucciones dedicadas de llamada, retorno, inserción y extracción que implícitamente actualizan el registro dedicado, aumentando así la densidad del código . 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 los diseños de CPU RISC no tienen instrucciones de pila dedicadas y, por lo tanto, la mayoría de los registros, si no todos, se pueden usar como punteros de pila según sea necesario.

Apilar en registros o memoria dedicada

La calculadora de bolsillo programable HP-42S de 1988 tenía, como casi todas las calculadoras de la compañía de esa época , una pila de 4 niveles y podía mostrar dos de los cuatro valores de los registros de la pila X, Y, Z y T al mismo tiempo debido a su pantalla de dos líneas, aquí X e Y. En modelos posteriores como la HP-48 , el número de niveles se incrementó para estar limitado únicamente por el tamaño de la memoria.

Algunas máquinas utilizan una pila para realizar operaciones aritméticas y lógicas; los operandos se colocan en la pila y las operaciones aritméticas y lógicas actúan sobre uno o más elementos de la parte superior de la pila, sacándolos de la pila y colocando el resultado en la pila. Las máquinas que funcionan de esta manera se denominan máquinas de pila .

Varias computadoras centrales y minicomputadoras eran máquinas apiladas, siendo las más famosas los grandes sistemas de Burroughs . Otros ejemplos incluyen las máquinas CISC HP 3000 y las máquinas CISC de Tandem Computers .

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).

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 de los cachés de código , pero también impide algunos tipos de optimizaciones posibles en procesadores que permiten el acceso aleatorio al archivo de registros para todos (dos o tres) operandos. Una estructura de pila también hace que las implementaciones superescalares con cambio de nombre de registros (para ejecución especulativa ) sean algo más complejas de implementar, aunque aún es factible, como lo ejemplifican las implementaciones x87 modernas .

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 funciones 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 , el Computer Cowboys MuP21, la línea Harris RTX y el Novix NC4016. Al menos una familia de microcontroladores, la COP400 , implementa una pila ya sea directamente en el hardware o en la RAM a través de un puntero de pila, según el dispositivo. Muchos microprocesadores basados ​​en pila se utilizaron para implementar el lenguaje de programación Forth a nivel de microcódigo .

Aplicaciones de las pilas

Evaluación de expresiones y análisis de sintaxis

Las calculadoras que emplean la notación polaca inversa utilizan una estructura de pila para almacenar valores. Las expresiones se pueden representar en notaciones de prefijo, posfijo o infijo y la conversión de una forma a otra se puede lograr utilizando una pila. Muchos compiladores utilizan una pila para analizar la sintaxis antes de traducirla a código de bajo nivel. La mayoría de los lenguajes de programación son lenguajes libres de contexto , lo que permite analizarlos con máquinas basadas en pilas.

Retrocediendo

Otra aplicación importante de las pilas es el retroceso . Un ejemplo de esto es el simple ejemplo de encontrar el camino correcto en un laberinto que contiene una serie de puntos, un punto de partida, varios caminos y un destino. Si se deben elegir caminos aleatorios, luego de seguir un camino incorrecto, debe haber un método para regresar al comienzo de ese camino. Esto se puede lograr mediante el uso de pilas, ya que se puede insertar un último punto correcto en la pila y sacarlo de la pila en caso de un camino incorrecto.

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 soluciones potenciales a un problema de optimización. La técnica de ramificación y acotación es una técnica para realizar este tipo de búsquedas de retroceso sin buscar exhaustivamente todas las soluciones potenciales en dicho espacio.

Gestión de memoria en tiempo de compilación

Una pila de llamadas típica, que almacena datos locales e información de llamadas para múltiples niveles de llamadas a procedimientos. Esta pila crece hacia abajo desde su origen. El puntero de pila apunta al dato superior actual en la pila. Una operación push decrementa el puntero y copia los datos a la pila; una operación pop copia datos de la pila y luego incrementa el puntero. Cada procedimiento llamado en el programa almacena información de retorno del 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).

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) como tomar sus argumentos de la pila y colocar los valores de retorno nuevamente 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 diccionarios. Muchas máquinas virtuales también están orientadas a la pila, 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) utilizan una pila especial (la " pila de llamadas ") para almacenar información sobre la llamada y el anidamiento de procedimientos/funciones con el fin de cambiar al contexto de la función llamada y restaurar a la función que llama cuando finaliza la llamada. Las funciones siguen un protocolo de tiempo de ejecución entre el llamador y el llamado para guardar los argumentos y el valor de retorno en la pila. Las pilas son una forma importante de admitir llamadas a funciones anidadas o recursivas . Este tipo de pila es utilizada implícitamente por el compilador para admitir las declaraciones CALL y RETURN (o sus equivalentes) y no es manipulada directamente por el programador.

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 libera cuando éste sale. El lenguaje de programación C se implementa típicamente de esta manera. El uso de la misma pila para llamadas de datos y de procedimientos tiene importantes implicaciones de seguridad (ver a continuación) de las cuales un programador debe estar consciente 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. Entre ellos se incluyen:

Seguridad

Algunos entornos informáticos utilizan pilas de forma que pueden hacerlos vulnerables a ataques y violaciones de seguridad . Los programadores que trabajan en dichos entornos deben tener especial cuidado para evitar este tipo de problemas en 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 de procedimiento. Si los datos se mueven a la ubicación incorrecta en la pila, o un elemento de datos de gran tamaño se mueve a una ubicación de pila que no es lo suficientemente grande para contenerlo, la información de retorno para las llamadas de procedimiento puede estar dañada, lo que provoca que el programa falle.

Los grupos malintencionados pueden intentar un ataque de destrucción de pila que se aproveche de 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. Un programa de este tipo 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 un programa de este tipo 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 de búfer y es una fuente extremadamente frecuente de brechas de seguridad en el software, principalmente porque algunos de los compiladores más populares utilizan una pila compartida tanto para llamadas de datos como de procedimientos, y no verifican la longitud de los elementos de datos. Con frecuencia, los programadores tampoco escriben código para verificar el tamaño de los elementos de datos, y cuando un elemento de datos de tamaño demasiado grande o demasiado pequeño se copia a la pila, puede ocurrir una brecha de seguridad.

Véase también

Notas

  1. ^ Por el contrario, una cola opera según el principio primero en entrar, primero en salir, conocido con el acrónimo FIFO .

Referencias

  1. ^ ab 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. págs. 232-233. ISBN 0-262-03384-4.
  2. ^ 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).)
  3. ^ Carpenter, Brian Edward ; Doran, Robert William (1977-01-01) [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)
  4. ^ Blaauw, Gerrit Anne ; Brooks, Jr., Frederick Phillips (1997). Arquitectura informática: conceptos y evolución . Boston, Massachusetts, EE. UU.: Addison-Wesley Longman Publishing Co., Inc.
  5. ^ LaForest, Charles Eric (abril de 2007). "2.1 Lukasiewicz y la primera generación: 2.1.2 Alemania: Konrad Zuse (1910–1995); 2.2 La primera generación de computadoras de pila: 2.2.1 Zuse Z4". Arquitectura de computadoras de pila de segunda generación (PDF) (tesis). Waterloo, Canadá: Universidad de Waterloo . pp. 8, 11. Archivado (PDF) desde el original el 20 de enero de 2022. Consultado el 2 de julio de 2022 .(178 páginas)
  6. ^ 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 llama memoria auxiliar lineal ( linearer Hilfsspeicher ).)
  7. ^ abcd Fothe, Michael; Wilke, Thomas, eds. (2015) [2014-11-14]. Escrito en Jena, Alemania. Keller, Stack und automatisches Gedächtnis – eine Struktur mit Potenzial [ Bodega, pila y memoria automática: una estructura con potencial ] (PDF) (Tagungsband zum Kolloquium, 14 de noviembre de 2014 en Jena). Serie GI: Apuntes de conferencias sobre informática (LNI) - Temáticas (en alemán). vol. T-7. Bonn, Alemania: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag GmbH. ISBN 978-3-88579-426-4. ISSN  1614-3213. Archivado (PDF) desde el original el 12 de abril de 2020. Consultado el 12 de abril de 2020 .[1] (77 páginas)
  8. ^ 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). Múnich, Alemania: Deutsches Patentamt. DE-PS 1094019 . Consultado el 1 de octubre de 2010 .
  9. ^ Bauer, Friedrich Ludwig ; Goos, Gerhard [en alemán] (1982). Informatik - Eine einführende Übersicht (en alemán). vol. 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.
  10. ^ Samelson, Klaus ; Bauer, Friedrich Ludwig (1959). "Sequentielle Formelübersetzung" [Traducción secuencial de fórmulas]. Elektronische Rechenanlagen (en alemán). 1 (4): 176–182.
  11. ^ Samelson, Klaus ; Bauer, Friedrich Ludwig (1960). "Traducción de fórmulas secuenciales". Comunicaciones de la ACM . 3 (2): 76–83. doi : 10.1145/366959.366968 . S2CID  16646147.
  12. ^ "IEEE-Computer-Pioneer-Preis – Bauer, Friedrich L." Universidad Técnica de Múnich , Facultad de Informática. 1 de enero de 1989. Archivado desde el original el 7 de noviembre de 2017.
  13. ^ 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 2020-04-12 . Consultado el 2020-04-12 .(12 páginas)
  14. ^ Kämmerer, Wilhelm [en alemán] (11 de diciembre de 1958). Ziffern-Rechenautomat mit Programmierung nach mathematischem Formelbild (tesis de habilitación) (en alemán). Jena, Alemania: Mathematisch-naturwissenschaftliche Fakultät, Friedrich-Schiller-Universität . urna:nbn:de:gbv:27-20130731-133019-7. PPN:756275237. Archivado desde el original el 14 de octubre de 2023 . Consultado el 14 de octubre de 2023 .[2] (2+69 páginas)
  15. ^ Kämmerer, Wilhelm [en alemán] (1960). Ziffernrechenautomaten . Elektronisches Rechnen und Regeln (en alemán). vol. 1. Berlín, Alemania: Akademie-Verlag .
  16. ^ 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. Número de serie  77-14977.
  17. ^ Godse, Atul P.; Godse, Deepali A. (1 de enero de 2010). Arquitectura informática. Publicaciones técnicas. pp. 1–56. ISBN 978-8-18431534-9. Recuperado el 30 de enero de 2015 .
  18. ^ Horowitz, Ellis (1984). Fundamentos de estructuras de datos en Pascal . Computer Science Press . pág. 67.
  19. ^ Pandey, Shreesham (2020). "Estructuras de datos en pocas palabras". Dev Genius . 2020 . SSRN  4145204.
  20. ^ Graham, Ronald "Ron" Lewis (1972). Un algoritmo eficiente para determinar la envoltura convexa de un conjunto plano finito (PDF) . Information Processing Letters 1. Vol. 1. págs. 132-133. Archivado (PDF) desde el original el 22 de octubre de 2022.
  21. ^ 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..
  22. ^ Berkman, Omer; Schieber, Baruch ; Vishkin, Uzi (1993). "Algoritmos paralelos doblemente logarítmicos óptimos basados ​​en la búsqueda de 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. .
  23. ^ 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 ..

Lectura adicional

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