Pila (tipo de datos abstracto)
En informática , una pila es un tipo de datos abstracto que sirve como una colección de elementos, con dos operaciones principales principales:
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 más abstractamente como una colección secuencial, las operaciones de empujar y hacer estallar 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 emergente elimina un elemento de la parte superior de la pila.
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, de forma independiente, por Charles Leonard Hamblin en la primera mitad de 1954 [12] y por Wilhelm Kämmerer 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 quita un plato de la pila, el que está debajo aparece para convertirse en el nuevo plato superior.
