Pilas (estructura de datos)

PILAS

DEFINICIÓN DE PILA

Una pila es una lista de elementos en la que se pueden insertar y eliminar datos sólo por uno de los extremos. Como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron.
Debido al orden en que se insertan y eliminan los elementos en una pila, también se le conoce como estructura LIFO (Last In, First Out: último enentrar, primero en salir).
En la vida cotidiana existen muchos ejemplos de pilas, una pila de platos en una alacena, una pila de monedas, una pila de papeles sobre un escritorio, etc.
Las pilas no son estructuras de datos fundamentales, es decir, no están definidas como tales en los lenguajes de programación.

IMPLEMENTACION DE PILAS CON ARREGLOS

Las pilas se pueden representar de variasmaneras, generalmente por medio de una lista unidireccional o de un arreglo lineal. A menos que se especifique o este implícito otro tipo de representación, cada una de nuestras pilas se mantendrá en un arreglo lineal PILA; una variable puntero CIMA que contendrá la posición del elemento cima de la pila y una variable MAX PILA que proporcionara el máximo número de elementos que puede contener la pila, lacondición CIMA = 0 o CIMA = NULL indicará que la pila estará vacía. En la siguiente figura se muestra una representación de una pila por medio de un arreglo: Como CIMA = 3 y como MAX PILA = 8, hay espacio para 5 elementos más en la pila.


XXX
YYY
ZZZ







1
2
3
4
5
6
7
8













CIMA = 3


MAX PILA = 8


Los cambios que se pueden hacer en una pilareciben nombres especiales. Cuando se añade a una pila un elemento, decimos que se agrego (push) en la pila y cuando se suprime, decimos que se quito (pop) en la pila. Para una pila “S” y un elemento i ejecutar la operación push(S,i) añade el elemento i al tope de la pila “S”. De manera parecida la operación pop (S) elimina el elemento en el tope de “S”.
Ejemplo si “S” es la pila de la siguientefigura:



Representación de Pilas en “C”.
Como sé vera hay varias maneras de representar a una pila en lenguaje “C”. Una pila es una colección ordenada de elementos; el lenguaje “C” ya incluye un tipo de datos que es una colección ordenada de elementos; por ello es tentador comenzar un programa con la declaración de una variable pila como arreglo, siempre que la solución de un problemarequiera el uso de una pila, por otra parte, una pila que es dinámica cuyo tamaño cambia constantemente en tanto que se le agregan o quitan elementos, sin embargo, aunque un arreglo no puede ser una pila, puede usarse como tal.
Y en consecuencia puede declararse una pila en “C” como una estructura que contiene dos formas: un arreglo para guardar los elementos de la pila y un puntero para indicar laposición del elemento tope dentro del arreglo lo cual puede hacerse para una pila de enteros por medio de las declaraciones.

#define STACKSIZE 100
struct stack
{
int pop;
int items [STACKSIZE];
};

Una vez hecho puede declararse una pila “S”, por medio de struct stack s;.
Aquí se supone que son enteros los elementos de la pila “S” contenidos en el arreglo “S”. items y que lapila nunca contiene más STACKSIZE enteros.
En este ejemplo STACKSIZE se fija en 100 para indicar que la pila puede contener 100 elementos (desde items[0] hasta items [99] ).
Por supuesto, no hay razón para restringir una pila que solo contenga enteros, los elementos items podrían declararse fácilmente como: float items[STACKSIZE] o char items[STACKSIZE].

En la siguiente figura se ilustrauna pila con varios nodos. Note que las pilas y las listas enlazadas se representan a n forma idéntica. La diferencia entre las pilas y las listas enlazadas es que en una la lista enlazada las inserciones y borrados puede ocurrir en cualquier parte, pero en una pila únicamente en su parte superior.

stackPtr
. . .

Las funciones primarias utilizadas para manipular una...