Pilas Y Colas

Pilas y Colas

Las pilas y colas son estructuras de datos que se utilizan generalmente para simplificar ciertas operaciones de programación. Estas estructuras pueden implementarse mediante arrays o mediante listas enlazadas.

Pilas: Las pilas son estructuras de datos que tienes dos operaciones básicas:

Push (para insertar un elemento) y pop (para extraer un elemento). Su característica fundamental es que al extraer se obtiene siempre el último elemento que acaba de insertarse. Por esta razón también se conocen como estructuras de datos LIFO (del inglés Last In First Out). Una posible implementación mediante listas enlazadas sería insertando y extrayendo siempre por el principio de la lista. Gracias a las pilas es posible el uso de la recursividad (lo veremos en detalle en el tema siguiente). La variable que llama al mismo procedimiento en el q está, habrá que guardarla así como el resto de variables de la nueva llamada, para a la vuelta de la recursividad ir sacándolas, esto es posible a la implementación de pilas.

Las pilas se utilizan en muchas aplicaciones que utilizamos con frecuencia. Por ejemplo, la gestión de ventanas en Windows (cuando cerramos una ventana siempre recuperamos la que teníamos detrás). Otro ejemplo es la evaluación general de cualquier expresión matemática para evitar tener que calcular el número de variables temporales que hacen falta. Por ejemplo:

3 + 4 * (8 – 2 * 5)

5

-2

8

4

3

-10

8

4

3

-2

4

3

-8

3 -5

Colas: Las colas también son llamadas FIFO (First In First Out), que quiere decir “el primero que entra es el primero que sale”.

Colas simples: Se inserta por un sitio y se saca por otro, en el caso de la cola simple se inserta por el final y se saca por el principio. Para gestionar este tipo de cola hay que recordar siempre cual es el siguiente elemento que se va a leer y cuál es el último elemento que se ha introducido

910

973

175

137

.

Colas circulares: En las colas circulares se considera que después del último elemento se accede de nuevo al primero. De esta forma se reutilizan las posiciones extraídas, el final de la cola es a su vez el principio, creándose un circuito cerrado.

5

4

3

2

5

4

3

2

8

4

3

2

1

5

4

3

2

1

Lo que se ha hecho es insertar (5), sacar (1), e insertar (8).

Se sabrá que una tabla está llena cuando “rear” y “front” estén en una posición de diferencia.

El teclado de ordenador se comporta exactamente como una cola circular.

Para implementar las colas circulares mediante listas enlazadas se pone en el tipo T_Lista los punteros front y rear.

Colas con prioridad: Las colas con prioridad se implementan mediante listas o arrays ordenados. No nos interesa en este caso que salgan en el orden de entrada sino con una prioridad que le asignemos. Puede darse el caso que existan varios elementos con la misma prioridad, en este caso saldrá primero aquel que primero llego (FIFO).

Pilas: Una pila representa una estructura lineal de datos en que se puede agregar o quitar elementos únicamente por uno de los dos extremos. En consecuencia, los elementos de una pila se eliminan en el orden inverso al que se insertaron. Debido a esta característica, se le conoce como estructura LIFO (Last input, First output).

• Existen muchos casos prácticos en los que se utiliza la idea de pila:

• Ejemplo; pila de platos, en el supermercado latas.

• Las pilas con estructuras lineales como los arreglos, ya que sus componentes ocupan lugares sucesivos en la ED y c/u tienen un único sucesor/predecesor, con excepción del primero/último.

Definición de Pila

• Una colección de datos a los cuales se les puede acceder mediante un extremo, que se conoce generalmente como tope.

Representación de Pilas

• Las pilas no son estructuras fundamentales de datos; es decir no están definidas como tales en los lenguajes de programación.

...