PILAS Y COLAS

 INVESTIGACION DE PILAS Y COLAS
PILAS
Una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de los extremos de la lista. Estas operaciones se conocen como "push" y "pop", respectivamente "empujar" y "tirar". Además, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan elnodo leído.
Estas características implican un comportamiento de lista LIFO (Last In First Out), el último en entrar es el primero en salir.
El símil del que deriva el nombre de la estructura es una pila de platos. Sólo es posible añadir platos en la parte superior de la pila, y sólo pueden tomarse del mismo extremo.
El nodo típico para construir pilas es el mismo que vimos en el capítulo anteriorpara la construcción de listas:
struct nodo \
{
int dato;
struct nodo *siguiente;
};

Operaciones básicas con pilas
Las pilas tienen un conjunto de operaciones muy limitado, sólo permiten las operaciones de "push" y "pop":
Push: Añadir un elemento al final de la pila.
Pop: Leer y eliminar un elemento del final de la pila.
Push
Las operaciones con pilas son muy simples, no hay casosespeciales, salvo que la pila esté vacía.
Push en una pila vacía
Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero a la pila valdrá NULL:

El proceso es muy simple, bastará con que:
1. nodo->siguiente apunte a NULL.
2. Pila apunte a nodo.
Push en una pila no vacía

Push en pila no vacía
Podemos considerar el caso anterior como un caso particularde éste, la única diferencia es que podemos y debemos trabajar con una pila vacía como con una pila normal.
De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una pila, en este caso no vacía:

Resultado
El proceso sigue siendo muy sencillo:
1. Hacemos que nodo->siguiente apunte a Pila.
2. Hacemos que Pila apunte a nodo.
Pop, leer y eliminar un elemento


Pop
Ahora sóloexiste un caso posible, ya que sólo podemos leer desde un extremo de la pila.
Partiremos de una pila con uno o más nodos, y usaremos un puntero auxiliar, nodo:

Resultado
1. Hacemos que nodo apunte al primer elemento de la pila, es decir a Pila.
2. Asignamos a Pila la dirección del segundo nodo de la pila: Pila->siguiente.
3. Guardamos el contenido del nodo para devolverlo como retorno, recuerdaque la operación pop equivale a leer y borrar.
4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.
Si la pila sólo tiene un nodo, el proceso sigue siendo válido, ya que el valor de Pila->siguiente es NULL, y después de eliminar el último nodo la pila quedará vacía, y el valor de Pila será NULL.
Declaraciones de tipos de para manejar pilas en C

Los tipos que definiremosnormalmente para manejar pilas serán casi los mismos que para manejar listas, tan sólo cambiaremos algunos nombres:
typedef struct _nodo \
{
int dato;
struct _nodo *siguiente;
} tipoNodo;

typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;
tipoNodo es el tipo para declarar nodos, evidentemente.
pNodo es el tipo para declarar punteros a un nodo.
Pila es el tipo para declarar pilas.

Es evidente,a la vista del gráfico, que una pila es una lista abierta. Así que sigue siendo muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas.
Teniendo en cuenta que las inserciones y borrados en una pila se hacen siempre en un extremo, lo que consideramos como el primer elemento de la lista es en realidad el último elemento de lapila.

COLAS
Una cola (también llamada fila) es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.
Una cola es un...