[C con Clase] Pilas y Colas

[Steven Davidson]

Hola César,

Cesar Cortes Baron wrote:
> Hola amigos
> 
> me estoy introduciendo en le tema de estructuras de datos, me
> gustaria saber si me podrian ayudar con algunos ejemplos basicos
> sobre el manejo de Pilas y Colas, ya que aun no logro entender muy
> bien el concepto, no se en que tipo de programas pueda apliar este
> tipo de herramientas.
> 

Sugiero que consultes el curso de "Estructuras Dinámicas de Datos" (EDD) 
en nuestra página. El enlace es: http://c.conclase.net/edd/index.php 
Los tres primeros capítulos te ayudarán y al final de cada uno verás 
ejemplos en C, C++, y C++ usando plantillas.

Las pilas y las colas se usan bastante en los programas. Por ejemplo, 
para poder retroceder en un historial de acciones o elementos, 
implementamos una pila. Un ejemplo puede ser el historial de muchos 
editores y procesadores de texto. Al pulsar CTRL+Z retrocedemos en el 
historial.

Al invocar funciones, se usan pilas para recordar el orden inverso al 
regresar de una función. Por ejemplo,

func()
{
   f1();
   ...
   return;
}

f1()
{
   g6();
   ...
   return;
}

g6()
{
   r3();
   ...
   return;
}

r3()
{
   ...
   return;
}

int main()
{
   func();
   ...
}

Se guardan las invocaciones y su contexto en el orden de aparición para 
poder retroceder a cada una en el orden correcto. Esto es,

Pila:
   r3()
   g6()
   f1()
   func()
   main()

Cuando hayamos terminado con la primera función, entonces se eliminará 
su elemento en esta pila y estaremos en 'g6()'; o sea,

Pila:
   g6()
   f1()
   func()
   main()

Y así sucesivamente.

Este sistema es indispensable para implementar la recursividad.

Otro ejemplo puede ser el algoritmo para buscar la salida de un 
laberinto. Si nos topamos con una bifurcación, recordamos su posición en 
un historial de bifurcaciones recientes. Ahora escogemos otro camino. Si 
este camino no conduce a una salida, entonces volvemos a la bifurcación 
más reciente. Puede darse el caso de que al escoger un camino a partir 
de una bifurcación, nos encontremos con otra bifurcación, y por tanto 
necesitamos volver a la bifurcación más reciente. Por ejemplo,

Pila de Bifurcaciones:
   (3,4)
   (3,7)
   (1,3)

Si hemos probado todos los caminos a partir de la última bifurcación: 
(3,4), entonces es hora de volver a la anterior: (3,7). La pila entonces 
contendría:

Pila de Bifurcaciones:
   (3,7)
   (1,3)

Y probaríamos otra vez.

Para las colas, los sistemas operativos hacen uso de ellas para 
organizar los datos por varios motivos. Por ejemplo, para los SS.OO. 
orientados a eventos o basados en mensajes suelen implementar una pila 
de mensajes o de eventos para cada proceso, para ir recogiendo y 
procesando cada mensaje o evento. Un claro ejemplo de esto es 
MS-Windows. Cada ventana tiene una cola de mensajes a procesar que 
indican varias acciones o eventos, como pueden ser: dibujar el área del 
cliente, la pulsación de un botón en una ventana, la pulsación doble del 
botón izquierdo del ratón, el ensanchamiento de la ventana, el 
movimiento del ratón, la destrucción de una ventana, etc.. En el API de 
MS-Windows, vamos sacando cada mensaje de esta cola y podemos agregar 
otros al final, claro está.

El uso de colas tiene que ver con una ordenación de los datos primerizos 
para ser tratados primeros. Estos datos pueden representar los pedidos 
en una tienda, los clientes de una empresa, banco, o supermercado, etc.. 
En general, se usa una pila para implementar cualquier sistema de 
procesamiento póstumo de datos, como puede ser la recogida de datos en 
redes de telecomunicaciones como la comunicación en tiempo "real" de 
vídeo, sonido, y posiblemente texto. La información que llega al 
dispositivo (PC, teléfono, etc.) es guardada hasta que la aplicación de 
tal dispositivo haga uso de ella.

El mismo sistema de lectura desde el teclado en los PC's implementa una 
cola circular cada vez que se nos pida introducir caracteres.


Espero que todo esto te ayude.

Steven