Hispanopedia Wiki
Articulo de referencia

Pila (tipo de dato abstracto)

Al igual que con una pila de platos, añadir o quitar platos solo es práctico en la parte superior. Representación simple de un entorno de ejecución de pila con operaciones push ...

Hispanopedia WikiContenido en espanolLectura gratuita

Al igual que con una pila de platos, añadir o quitar platos solo es práctico en la parte superior.
Representación simple de un entorno de ejecución de pila con operaciones push y pop.

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

  • Push , que agrega un elemento a la colección, y
  • Pop , que elimina el elemento añadido más recientemente.

Además, una operación de visualización puede, sin modificar la pila, devolver el valor del último elemento añadido (el elemento que se encuentra en la parte superior de la pila). El nombre " pila" es una analogía de un conjunto de objetos físicos apilados uno encima del otro, como una pila de platos.

El orden en que se agregan o eliminan elementos de una pila se describe como último en entrar, primero en salir , conocido por 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 el acceso a un dato más profundo puede requerir la eliminación previa de varios otros elementos. [ 1 ]

Considerada una colección secuencial, una pila tiene un extremo, la única posición donde pueden ocurrir las operaciones de inserción y extracción (la parte superior ), y un extremo fijo (la parte inferior) . Una pila puede implementarse, por ejemplo, como una lista enlazada simple con un puntero al elemento superior.

Una pila puede implementarse con una capacidad limitada. Si la pila está llena y no contiene suficiente espacio para aceptar otro elemento, se produce un desbordamiento de pila .

Historia

Las pilas entraron en la literatura de la 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 ("bodega operativa") en 1955 [ 6 ] [ 7 ] y presentaron una patente en 1957. [ 8 ] [ 9 ] [ 10 ] [ 11 ] En marzo de 1988, para entonces Samelson ya había fallecido, Bauer recibió el Premio Pionero de la Informática del IEEE por la invención del principio de pila. [ 12 ] [ 7 ] Conceptos similares fueron desarrollados independientemente por Charles Leonard Hamblin en la primera mitad de 1954 [ 13 ] [ 7 ] y por Wilhelm Kämmerer con su automatisches Gedächtnis ("memoria automática") en 1958. [ 14 ] [ 15 ] [ 7 ]

Las pilas se suelen describir mediante la analogía de una pila de platos con resorte en una cafetería. [ 16 ] [ 1 ] [ 17 ] Los platos limpios se colocan encima de la pila, empujando hacia abajo los 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 esenciales "push" y "pop". Un ejemplo de operación no esencial es "top of stack" o "peek", que observa el elemento superior sin eliminarlo de la pila. [ 18 ] Dado que esto se puede descomponer 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 subdesbordamiento al ejecutar cualquiera de las operaciones "peek" o "pop". Además, muchas implementaciones incluyen operaciones de conveniencia que manejan tareas comunes, como verificar si la pila está vacía o devolver su tamaño.

Pilas de software

Diagrama UML para una pila

Implementación

Una pila se puede implementar fácilmente mediante un arreglo o una lista enlazada , ya que es simplemente un caso especial de una lista. [ 19 ] En ambos casos, lo que identifica la estructura de datos como una pila no es la implementación, sino la interfaz: el usuario solo puede extraer o insertar elementos en el arreglo o la lista enlazada, con pocas otras operaciones auxiliares. A continuación se demostrarán ambas implementaciones mediante pseudocódigo .

Formación

Se puede usar un arreglo para implementar una pila (limitada) de la siguiente manera. El primer elemento, generalmente en la posición cero , es la base, lo que resulta en array[0]que sea el primer elemento insertado en la pila y el último extraído. El programa debe llevar un registro del tamaño (longitud) de la pila, usando una variable ` top` que registra la cantidad de elementos insertados hasta el momento, apuntando así a la posición en el arreglo donde se insertará el siguiente elemento (suponiendo una convención de índice basada en cero). Por lo tanto, la pila en sí misma se puede implementar de manera efectiva como una estructura de tres elementos:

pila de estructuras : tamaño máximo: entero superior: entero elementos: matriz de elementos
procedimiento initialize(stk : pila, tamaño : entero): stk.items ← nuevo array de elementos de tamaño , inicialmente vacío stk.maxsize ← tamaño stk.top ← 0

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

Operación de inserción animada en una pila basada en matrices, desde desbordamiento inferior hasta desbordamiento superior.
procedimiento push(stk : pila, x : elemento): si stk.top = stk.maxsize: informe de error de desbordamiento demás : stk.items[stk.top] ← x stk.top ← stk.top + 1

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

Operación de extracción animada en una pila basada en matrices desde el estado de pila completa hasta el subdesbordamiento.
procedimiento pop(stk : pila): si stk.top = 0: informe de error de desbordamiento demás : stk.top ← stk.top − 1 r ← stk.items[stk.top] devolver r

Mediante un arreglo dinámico , es posible implementar una pila que puede crecer o encogerse según sea necesario. El tamaño de la pila es simplemente el tamaño del arreglo dinámico, lo que constituye una implementación muy eficiente, ya que agregar o eliminar elementos del final de un arreglo dinámico requiere un tiempo amortizado de O(1).

Lista enlazada

Otra opción para implementar pilas es usar una lista enlazada simple . Una pila es entonces un puntero al "inicio" de la lista, con un contador para controlar el tamaño de la misma:

marco de la estructura : datos: artículo siguiente: marco o nulo
pila de estructuras : cabeza: marco o nulo tamaño: entero
procedimiento inicializar(stk : pila): stk.head ← nil stk.size ← 0

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

Operación de inserción animada en una pila basada en listas enlazadas.
procedimiento push(stk : pila, x : elemento): nuevo encabezado ← nuevo marco newhead.data ← x nuevocabezado.siguiente ← stk.cabezado stk.head ← newhead stk.size ← stk.size + 1
Operación pop animada en una pila basada en lista enlazada.
procedimiento pop(stk : pila): si stk.head = nil: informe de error de desbordamiento demás : r ← stk.head.data stk.head ← stk.head.next stk.size ← stk.size - 1 devolver r

Pilas de tecnologías y lenguajes de programación

Algunos lenguajes, como Perl , LISP , JavaScript y Python , permiten realizar operaciones de pila (push y pop) en sus tipos de lista/matriz estándar. Otros lenguajes, en particular los de la familia Forth (incluido PostScript ), están diseñados en torno a pilas definidas por el propio lenguaje, que el programador puede visualizar y manipular directamente.

El siguiente es un ejemplo de cómo manipular 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), debería modificar la pila A > stack ;; comprueba el valor de stack ( B C ) > ( push 'new stack ) ;; inserta un nuevo elemento superior en la pila ( NEW B C )

Varios tipos de contenedores de la biblioteca estándar de C++push_back() tienen operaciones pop_back()con semántica LIFO; además, la std::stackclase plantilla adapta los contenedores existentes para proporcionar una API restringida con solo operaciones push/pop. PHP tiene una SplStackclase. La biblioteca de Java contiene una Stackclase que es una especialización de Vector. A continuación se muestra un programa de ejemplo en lenguaje Java , que utiliza esa clase.

paquete org.wikipedia.examples ;import java.util.Stack ;public class Example { public static void main ( String [] args ) { Stack < Character > stack = new Stack <> (); stack . push ( 'a' ); // Inserta 'a' en la pila stack . push ( 'b' ); // Inserta 'b' en la pila stack . push ( 'c' ); // Inserta 'c' en la pila stack . push ( 'd' ); // Inserta 'd' en la pila System . out . println ( stack . peek ()); // Imprime la cima de la pila ('d') stack . pop (); // Elimina la cima ('d') stack . pop (); // Elimina la siguiente cima ('c') } }

Algunos procesadores, como los de las series PDP-11 , VAX y Motorola 68000, cuentan con modos de direccionamiento útiles para la manipulación de pilas. El siguiente código fuente en lenguaje ensamblador para PDP-11, de carácter trivial , inserta dos números en una pila y los suma, dejando el resultado en la misma.

; Se supone que R0 apunta a un área de la pila ; -(R0) predecrementa el puntero de pila asignando un elemento en la pila ; (R0)+ Postincrementa el puntero de pila eliminando un elemento de la pila ; MOV #12,-(R0) ; Inserta 12 en la pila MOV #34,-(R0) ; Inserta 34 en la pila ADD ( R0 ) + ,( R0 ) ; Extrae 34 de la pila y lo suma a 12 ; dejando el resultado en la pila

Conjunto 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 memoria de 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 del procesador ) apunta a la ubicación de la pila a la que se accedió 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:

  • Operación de inserción : la dirección en el puntero de pila se ajusta según el tamaño del elemento de datos y se escribe un elemento de datos en la ubicación a la que apunta el puntero de pila.
  • Operación de extracción o adquisición : se lee un elemento de datos en la ubicación actual a la que apunta el puntero de pila, y el puntero de pila se mueve una distancia que corresponde al tamaño de ese elemento de datos.

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

Los punteros de pila pueden apuntar al origen de la pila o a un rango limitado de direcciones por encima o por debajo del origen (según la dirección de crecimiento de la pila); sin embargo, el puntero de pila no puede sobrepasar el origen. En otras palabras, si el origen de la pila se encuentra 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). Si una operación de extracción (pop) en la pila provoca que el puntero de pila se mueva más allá del origen, se produce un subdesbordamiento de pila . Si una operación de inserción (push) provoca que el puntero de pila se incremente o decremente más allá de la extensión máxima de la pila, se produce un sobredesbordamiento de pila .

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

  • Duplicar : el elemento superior se extrae y luego se vuelve a insertar dos veces, de manera que ahora hay dos copias del antiguo elemento superior en la parte superior.
  • Peek : se inspecciona (o se devuelve) el elemento superior, pero el puntero de pila y el tamaño de la pila no cambian (es decir, el elemento permanece en la pila). Esto también se conoce como operación top .
  • Intercambiar o cambiar : los dos elementos superiores de la pila intercambian posiciones.
  • Rotación (o desplazamiento) : los n elementos superiores de la pila se mueven 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, respectivamente. Existen muchas variantes de esta operación, siendo las más comunes la rotación a la izquierda y la rotación a la derecha.

Las pilas suelen visualizarse creciendo de abajo hacia arriba (como las pilas del mundo real). También pueden visualizarse creciendo de izquierda a derecha, con la parte superior en el extremo derecho, o incluso creciendo de arriba hacia abajo. Lo importante es que la base de la pila permanezca 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 base de la pila, ya que la parte superior (9) es desde donde se insertan o extraen los elementos.

Una rotación a la derecha moverá el primer elemento a la tercera posición, el segundo a la primera y el tercero a la segunda. Aquí hay dos visualizaciones equivalentes de este proceso:

manzana plátano plátano ===rotación a la derecha==> pepino pepino manzana
pepino manzana plátano ===girar a la izquierda==> pepino manzana plátano

En informática, una pila se representa generalmente mediante un bloque de celdas de memoria, donde la celda inferior (o "inferior") se encuentra en una ubicación fija y el puntero de pila almacena la dirección de la celda superior (o "superior") actual. La nomenclatura "superior" e "inferior" se utiliza independientemente de si la pila crece hacia direcciones de memoria superiores.

Al insertar un elemento en la pila, el puntero de pila se ajusta según el tamaño del elemento (ya sea decrementándolo o incrementándolo, dependiendo de la dirección en que la pila crece en la memoria), apuntando a la siguiente celda, y se copia el nuevo elemento superior al área de la pila. Dependiendo de la implementación específica, al finalizar una operación de inserción, el puntero de pila puede apuntar a la siguiente ubicación no utilizada en la pila o al elemento superior actual. Si la pila apunta al elemento superior actual, el puntero de pila se actualizará antes de insertar un nuevo elemento; si apunta a la siguiente ubicación disponible, se actualizará después de insertar el nuevo elemento.

Extraer un elemento de la pila es simplemente lo contrario de insertarlo. Se elimina el elemento superior de la pila y se actualiza el puntero de pila, en el orden opuesto al utilizado en la operación de inserción.

Pila en la memoria principal

Muchos diseños de CPU de tipo CISC , incluidos el x86 , el Z80 y el 6502 , tienen un registro dedicado para usarse como puntero de pila de la pila de llamadas con instrucciones dedicadas de llamada, retorno, inserción y extracción que actualizan implícitamente dicho registro, 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 , generalmente con un puntero de pila semidedicado (como el 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, si no todos, los registros pueden usarse como punteros de pila según sea necesario.

Pila en registros o memoria dedicada

La calculadora programable de bolsillo HP-42S de 1988, al igual que casi todas las calculadoras de la compañía de aquella época , tenía 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) simultáneamente gracias a su pantalla de dos líneas (en este caso, X e Y). En modelos posteriores, como la HP-48 , el número de niveles se incrementó hasta estar limitado únicamente por el tamaño de la memoria.

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

Varias computadoras centrales y minicomputadoras eran máquinas de pila, siendo la más famosa la Burroughs Large Systems . 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 un tamaño de código máquina reducido con un buen uso del ancho de banda del bus y las cachés de código , pero también impide ciertos tipos de optimizaciones posibles en procesadores que permiten el acceso aleatorio al banco 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 sigue siendo factible, como lo demuestran 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 la memoria principal, que es lenta, para los argumentos de las funciones y los valores de retorno.

También existen varios microprocesadores pequeños que implementan una pila directamente en hardware, y algunos microcontroladores tienen una pila de profundidad fija que no es directamente accesible. Ejemplos de ello 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 directamente en hardware o en la RAM mediante 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 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 almacenar valores. Las expresiones pueden representarse en notación prefija, postfija o infija, y la conversión entre ellas se realiza mediante 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 libres de contexto , lo que permite analizarlos con máquinas basadas en pilas.

Retroceder

Otra aplicación importante de las pilas es el retroceso . Un ejemplo sencillo es 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, entonces, después de seguir un camino incorrecto, debe existir un método para regresar al inicio 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 extraerlo en caso de que el camino sea incorrecto.

El ejemplo prototípico de un algoritmo de retroceso es la búsqueda en profundidad , que encuentra todos los vértices de un grafo que se pueden alcanzar desde un vértice inicial específico. Otras aplicaciones del retroceso implican la búsqueda en espacios que representan posibles soluciones a un problema de optimización. La ramificación y acotación es una técnica para realizar dichas búsquedas de retroceso sin explorar exhaustivamente todas las posibles soluciones en dicho espacio.

Gestión de memoria en tiempo de compilación

Una pila de llamadas típica 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 más alto actual en la pila. Una operación de inserción decrementa el puntero y copia los datos a la pila; una operación de extracción copia los 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) insertándolos en la pila. Este tipo de implementación de pila es extremadamente común, pero es vulnerable a ataques de desbordamiento de búfer (ver el texto).

Varios lenguajes de programación están orientados a pilas , 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 de nuevo en ella. Por ejemplo, PostScript tiene una pila de retorno y una pila de operandos, además de una pila de estado gráfico y una pila de diccionario. Muchas máquinas virtuales también están orientadas a pilas, como la máquina de código P y la máquina virtual de Java .

Casi todas las convenciones de llamada —lasformas en que las subrutinas reciben sus parámetros y devuelven resultados— utilizanuna pila especial (la " pila de llamadas ") para almacenar información sobre la llamada a procedimientos/funciones y su anidamiento, con el fin de cambiar al contexto de la función llamada y regresar a la función que la llamó cuando finaliza la llamada. Las funciones siguen un protocolo de tiempo de ejecución entre la función que llama y la función llamada 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 instrucciones 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 a un procedimiento. El espacio para estos datos se asigna desde la pila al entrar en el procedimiento y se libera al finalizar. El lenguaje de programación C se implementa típicamente de esta manera. El uso de la misma pila para datos y llamadas a procedimientos tiene importantes implicaciones de seguridad ( véase más abajo ) que el programador debe conocer para evitar introducir vulnerabilidades graves en el programa.

Algoritmos eficientes

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

Seguridad

Algunos entornos informáticos utilizan pilas de forma que pueden hacerlos vulnerables a fallos de seguridad y ataques. Los programadores que trabajan en dichos entornos deben extremar las precauciones para evitar estos riesgos en sus 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 quien lo llamó. Esto significa que el programa mueve los datos dentro y fuera de la misma pila que contiene las direcciones de retorno críticas para las llamadas a procedimientos. Si los datos se mueven a una ubicación incorrecta en la pila, o si un elemento de datos demasiado grande se mueve a una ubicación de la pila que no tiene capacidad suficiente para contenerlo, la información de retorno para las llamadas a procedimientos puede corromperse, lo que provoca que el programa falle.

Los atacantes pueden intentar un ataque de saturación de pila aprovechando este tipo de implementación al proporcionar datos de entrada sobredimensionados a un programa que no verifica la longitud de la entrada. Dicho programa puede copiar los datos completos a una ubicación en la pila y, al hacerlo, puede modificar las direcciones de retorno de los procedimientos que lo hayan llamado. Un atacante puede experimentar para encontrar un tipo específico de datos que se pueda proporcionar a dicho programa de manera 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 para realizar operaciones no autorizadas.

Este tipo de ataque es una variante del ataque de desbordamiento de búfer y es una fuente muy frecuente de brechas de seguridad en el software, principalmente porque algunos de los compiladores más populares utilizan una pila compartida tanto para datos como para llamadas a 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 excesivo o insuficiente se copia a la pila, puede producirse una brecha de seguridad.

Véase también

Notas

  1. ↑ Por el contrario, una cola funciona según el principio primero en entrar, primero en salir, conocido por el acrónimo FIFO .

Referencias

  1. ^ 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 una máquina de cálculo automática (ACE) .(Nota: 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 de computadoras: 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 . págs. 8, 11. Archivado (PDF) del original el 20 de enero de 2022. Recuperado 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 a 68. (Nota: Este documento se presentó por primera vez en 1955. Describe una pila numérica ( Zahlenkeller ), pero la denomina memoria auxiliar lineal ( linearer Hilfsspeicher ).)
  7. 1 2 3 4 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-4ISSN 1614-3213 . Archivado (PDF) del original el 12 de abril de 2020. Consultado el 12 de abril de 2020 . (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 de fórmulas secuenciales ] . Elektronische Rechenanlagen (en alemán). 1 (4): 176-182 .
  11. ↑ Samelson, Klaus ; Bauer, Friedrich Ludwig (1960). "Traducción de fórmulas secuenciales" . Communications of the ACM . 3 (2): 76– 83. doi : 10.1145/366959.366968 . S2CID 16646147 . 
  12. ↑ "Premio IEEE a los pioneros de la informática – Bauer, Friedrich L." Universidad Técnica de Múnich , Facultad de Informática. 1 de enero de 1989. Archivado del 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) del original el 12 de abril de 2020. Recuperado el 12 de abril de 2020 . (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+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. LCCN 77-14977 . 
  17. ↑ Godse, Atul P.; Godse, Deepali A. (1 de enero de 2010). Arquitectura de computadoras . Publicaciones técnicas. págs. 1–56 . ISBN  978-8-18431534-9. Consultado 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) del 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 matricial". 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 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 ..

Lecturas adicionales

  • Knuth, Donald (1997). «§2.2.1: Pilas, colas y deques». El arte de la programación informática . Vol.  1: Algoritmos fundamentales (3.ª  ed.). Addison-Wesley. pp. 238–243 . ISBN  0-201-89683-4.
  • Langmaack, Hans [en alemán] (2015) [14 de noviembre de 2014]. Escrito en Kiel, Alemania. Friedrich L. Bauers und Klaus Samelsons Arbeiten in den 1950er-Jahren zur Einführung der Begriffe Kellerprinzip und Kellerautomat [ Trabajos de Friedrich L. Bauer y Klaus Samelson en la década de 1950 sobre la introducción de los términos principio de bodega y autómata de bodega ] (PDF) (en alemán). Jena, Alemania: Institut für Informatik, Christian-Albrechts-Universität zu Kiel. págs. 19 a 29. Archivado (PDF) desde el original el 14 de noviembre de 2022 . Consultado el 14 de noviembre de 2022 . (11 páginas) (Nota: Publicado en Fothe & Wilke .)
  • Goos, Gerhard [en alemán] (7 de agosto de 2017). Geschichte der deutschsprachigen Informatik - Programmiersprachen und Übersetzerbau [ Historia de la informática en los países de habla alemana - Lenguajes de programación y diseño de compiladores ] (PDF) (en alemán). Karlsruhe, Alemania: Fakultät für Informatik, Instituto Tecnológico de Karlsruhe (KIT). Archivado (PDF) desde el original el 19 de mayo de 2022 . Consultado el 14 de noviembre de 2022 .(11 páginas)
  • Máquinas apilables: la nueva ola
  • Profundidad de pila límite
  • Análisis del tamaño de la pila para programas controlados por interrupciones
Lecturas relacionadas
6 articulos
Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...Tipo de datos abstractoTipo de datos abstractoEn informática , un tipo abstracto de datos ( ADT ) es un modelo matemático para los tipos de datos , definido por su comportamiento ( semántica ) ...Colección (tipo de datos abstractos)Colección (tipo de datos abstractos)En programación informática , una colección es un tipo de datos abstracto que es una agrupación de elementos que pueden usarse de manera polimórfica .AnalogíaAnalogíaLa analogía es una comparación o correspondencia entre dos cosas (o dos grupos de cosas) debido a un tercer elemento que se considera que comparten...DatosEstos son algunos de los diferentes tipos de datos: Geográficos, Culturales, Científicos, Financieros, Estadísticos, Meteorológicos, Naturales, Tra...Lista enlazadaUna lista enlazada es una secuencia de nodos que contienen dos campos: datos (un valor entero como ejemplo) y un enlace al siguiente nodo. El últim...