PDF de programación - Pilas LIFO y Colas FIFO - Algoritmos y Estructuras de Datos

Algoritmos y Estructuras de Datos

Pilas LIFO y Colas FIFO

Guillermo Román Díez

groman@fi.upm.es

Universidad Politécnica de Madrid

Curso 2015-2016

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

1/12

Motivación

Pregunta

¿qué es una pila? ¿qué es una cola?

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

2/12

Motivación

Pregunta

¿qué es una pila? ¿qué es una cola?

Pregunta

¿qué significa LIFO? ¿y FIFO?

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

2/12

Motivación

Pregunta

¿qué es una pila? ¿qué es una cola?

Pregunta

¿qué significa LIFO? ¿y FIFO?

Las pilas y las colas son TADs fundamentales con
innumerables aplicaciones
Se usan en multitud de aplicaciones

Pila de llamadas a métodos
Gestión del historial de acciones / navegación
Sistemas Operativos (round robin)
. . .

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

2/12

¿Qué es un LIFO?

LIFO ⇒ Last In First Out
Una Pila, LIFO o Stack es un TAD contenedor que consiste
en una secuencia lineal de elementos donde:

El último elemento apilado (push) es el primer elemento en
ser desapilado(pop)
No existe operación de búsqueda

No tiene límite de tamaño (teórico. . . )

Os suena Stack Overflow?

Veremos dos implementaciones usando

Listas de posiciones
Arrays

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

3/12

Interfaz LIFO<E>

Interrogadores: size, isEmpty
Inserción: push
Borrado: pop
Acceso: top
Conversión: toArray, toPositionList

Siguiendo LIFO, el primer elemento del array será el primer
elemento desapilado

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

4/12

Interfaz LIFO<E>

Interrogadores: size, isEmpty
Inserción: push
Borrado: pop
Acceso: top
Conversión: toArray, toPositionList

Siguiendo LIFO, el primer elemento del array será el primer
elemento desapilado

Ejercicio

Implementar el método boolean balance(String s)

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

4/12

Clase LIFOList<E>

Implementa una pila usando lista de posiciones
Sólo tiene la lista como atributo:

El tamaño de la pila es el de la lista
Apilar (push) consiste en insertar al principio
Desapilar (pop) consiste en borrar el primer elemento
La consulta se realiza mediante la operación top

Tiene 4 constructores:

(1) Vacío, (2) un array, (3) una lista posiciones o (4) una pila

pop y top lanzan EmptyStackException si la pila está vacía
push no lanza excepción
toString y toArray usan los método de la lista
toPositionList devuelve una copia de la lista atributo

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

5/12

Clase LIFOArray<E>

Implementa una pila usando un array

Establece un tamaño inicial para el array. Cuando se llena crea
uno mayor copiando los elementos (shallow copy )

Tiene 3 atributos: arr, size, defaultCapacity

El tamaño de la pila es el número de elementos apilados (size)
Apilar (push) consiste en añadir después del último elemento
Desapilar (pop) consiste en borrar el último

Tiene 4 constructores:

(1) Vacío, (2) un valor para la capacidad, (3) un array, (4) una
lista de posiciones, (5) una pila

pop y top lanzan EmptyStackException si la pila está vacía
push comprueba si estamos al máximo de la capacidad y
amplia si es necesario
toString escribe el array en orden inverso
toArray y toPositionList devuelven los elementos uno a uno
insertándolos en el array o en la lista

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

6/12

¿Qué es un FIFO?

FIFO ⇒ First In First Out
Es un TAD contenedor que consiste en una secuencia lineal de
elementos donde el primer elemento encolado (enqueue) es
el primer elemento en ser desencolado (dequeue)
No existe una operación de búsqueda
No tiene límite de tamaño (teórico)

Presenta las mismas limitaciones que la lista

Veremos dos implementaciones usando

Listas de posiciones
Arrays

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

7/12

Interfaz FIFO<E>

Interrogadores: size, isEmpty
Inserción: enqueue
Borrado: dequeue
Acceso: first
Conversión: toArray, toPositionList

El primer elemento será el primer elemento desencolado

Un ejemplo típico es la gestión de CPU mediante
RoundRobin

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

8/12

Interfaz FIFO<E>

Interrogadores: size, isEmpty
Inserción: enqueue
Borrado: dequeue
Acceso: first
Conversión: toArray, toPositionList

El primer elemento será el primer elemento desencolado

Un ejemplo típico es la gestión de CPU mediante
RoundRobin

while (! fifo . isEmpy () ) {

Process p = fifo . first () ;
fifo . dequeue () ;
int status = p . run (20) ;
if ( status < 0) {

p . suspend () ;
fifo . enqueue ( p ) ;

}

}
Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

8/12

Clase FIFOList<E>

Implementa una cola usando lista de posiciones
Sólo tiene la lista como atributo:

El tamaño de la pila es el de la lista
Encolar (enqueue) consiste en insertar al final
Desencolar (dequeue) consiste en borrar el primer elemento

Tiene 4 constructores:

(1) Vacío, (2) un array, (3) una lista posiciones o (4) una cola

first y dequeue lanzan EmptyFIFOException si la pila está
vacía
enqueue no lanza excepción
toString y toArray usan los método de la lista
toPositionList devuelve una copia de la lista atributo

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

9/12

Clase FIFOArray<E>

Implementa una cola usando un array de forma circular

Establece un tamaño inicial para el array. Cuando se llena crea
uno mayor copiando los elementos (shallow copy )

Tiene 5 atributos: arr, size, first, last y defaultCapacity

El tamaño de la cola es el número de elementos apilados
Encolar (push) consiste en insertar al principio
Desapilar (pop) consiste en borrar el primer elemento

Tiene 5 constructores:

(1) Vacío, (2) un valor para la capacidad, (3) un array, (4) una
lista de posiciones, (5) una cola

pop y top lanzan EmptyFIFOException si la pila está vacía
push comprueba si estamos al máximo de la capacidad y
amplia si es necesario
toString escribe el array en orden inverso
toArray y toPositionList devuelven los elementos uno a uno
insertándolos en el vector o en la lista

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

10/12

Implementación Array Circular

Pregunta

¿por qué usamos un array de forma circular para las colas y no lo hemos
hecho así con las pilas?

La cola está vacía cuando first y last son iguales
Se van insertando elementos mediante last
El incremento de first y last se realiza de forma circular

last = ( last + 1) % arr . length ;

La cola se llena cuando first y last vuelven a ser iguales

En este caso tenemos que ampliar el tamaño del array

Pregunta

¿puede last ser menor que first?

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

11/12

Ampliación del tamaño del array

Se puede producir cuando se ejecuta enqueue
La ampliación el tamaño de la pila es igual que el tamaño del
array
Por decisión de diseño doblamos el tamaño del array
Se crea un array, se copian los elementos del antiguo en la
parte inicial del array

La copia hay que hacerla en el orden de encolado

first pasa a ser el primer elemento del array
last pasa a ser el primero de los huecos
Se inserta el elemento nuevo en el primer hueco

Guillermo Román, UPM

AED: Pilas LIFO y Colas FIFO

12/12