Queues (colas)
El ADT Queue
• El ADT Queue almacena
objetos arbitrarios dequeue()
• Las inserciones y
eliminaciones siguen el
esquema first-in first-out
(FIFO)
• Operaciones principales:
■ enqueue(object): encolar
el elemento al final de la
cola
■ dequeue(): desencolar el
elemento en el principio
enqueue()
de la cola
El ADT Queue
• Operaciones auxiliares:
• object front(): retorna el elemento del
frente sin removerlo
• integer size(): retorna la cantidad de
elementos encolados
• boolean isEmpty(): indica si la cola está
vacía
• Excepciones
• Intentar ejecutar dequeue() cuando la fila
está vacía lanza (throw) una excepción
Especificación algebraica
Structure Queue (Element)
declare
new() → Queue
enqueue(Queue, Element) 🡪 Queue
dequeue(Queue) → Queue
front(Queue) → Element
isEmpty (Queue) → boolean
size(Queue) → integer
for all Queue q and Element e let
isEmpty (new()) ::= true
isEmpty (enqueue(q, e)) ::= false
size(new()) ::= 0
size(enqueue(q,e)) ::= size(q)+1
size(dequeue(q,e)) ::= size(q)-1
front(new()) ::= error
front(enqueue(q,e)) ::= if isEmpty(q) then e
else front(q)
dequeue(new()) ::= new()
dequeue(enqueue(q, e)) ::= if isEmpty(q) then new()
else enqueue(dequeue(q),e)
Queue de la STL (Standard Template Library) de C++
queue<int> myQueue;
[Link](5); // myQueue: 5
[Link](6); // myQueue: 5 6
[Link](7); // myQueue: 5 6 7
while(![Link]()) {
cout << [Link]();
[Link]();
}
// Imprime: 5 6 7
Interfaz Stack en C++
class queue {
public:
virtual int enqueue(int val) = 0;
virtual int dequeue() = 0;
virtual void front() = 0;
virtual bool isEmpty() = 0;
virtual void size(int val) = 0;
};
Aplicaciones de colas
• Aplicaciones directas
• Listas de espera, burocracia
• Acceso a recursos compartidos (como una
impresora)
• Programación paralela
• Aplicaciones indirectas
• Estructuras auxiliares para algoritmos
• Componente de otras estructuras de datos
Ejemplo 1:
• Consideremos este ADT sin método size():
class queue {
public:
virtual int enqueue(int val) = 0;
virtual int dequeue() = 0;
virtual void front() = 0;
virtual bool isEmpty() = 0;
};
• Escribir un método que reciba una cola y retorne el
número de elementos. La cola debe quedar igual a como
se recibió después de retornar.
Ejemplo 1:
• Consideremos este ADT sin método size():
class queue {
public:
virtual int enqueue(int val) = 0;
virtual int dequeue() = 0;
virtual void front() = 0;
virtual bool isEmpty() = 0;
};
• Escribir un método que reciba una cola y retorne el
número de elementos. La cola debe quedar igual a como
se recibió después de retornar.
Algoritmo size(Q)
Entrada Una cola Q con objetos no repetidos
Salida el número de objetos de Q
if([Link]()) {return 0;}
first ← [Link]();
[Link]([Link]());
size ← 1
while([Link]() != first) {
[Link]([Link]());
size++;
}
return size;
Ejemplo 2: Reconocer palíndromos
• Palíndromo
• Una cadena de caracteres que se lee igual al
derecho que al revés
• Para reconocerlos, podemos usar una cola en conjunto
con una pila
• Una pila nos permite invertir el orden de los
elementos
• Una cola nos permite preservar el orden original
• ¿Es abcbd un palíndromo?
Queue: Stack: top
d
a b c b d b
c
b
front back
a
Ejemplo 2: Reconocer palíndromos
• Un algoritmo no recursivo para palíndromos
• Al recorrer el string de izquierda a derecha, insertar
cada carácter en una cola y en una pila.
• Comparar los caracteres al tope de la pila y el frente
de la cola.
Ejemplo 2: Reconocer palíndromos
• Un algoritmo no recursivo para palíndromos
• Al recorrer el string de izquierda a derecha, insertar
cada carácter en una cola y en una pila.
• Comparar los caracteres al tope de la pila y el frente
de la cola.
Algoritmo esPalindromo(t)
Entrada Un string t
Salida True si t es palíndromo
Q ← una fila vacía
S ← un pila vacía
for (i ← 0 to [Link]()) {
[Link](t[i]);
[Link](t[i]);
}
while(![Link]()) {
if([Link]() != [Link]())
return False;
}
return True;
Cola con lista ligada
• Podemos implementar colas con listas ligadas
• El elemento al frente se almacena en la cabeza
• El elemento al final se almacena en el último nodo
• Se usa espacio O(n) y cada operación del ADT toma
tiempo O(1)
r
nodes
f ∅
elements
Implementación basada en arreglos
• Para hacer que las operaciones sean O(1) tenemos que
usar el arreglo de manera circular
• La idea de un arreglo circular es que su final se
“curva” hacia el principio del arreglo
• Dos variables siguen el frente y final de la cola
f: índice del elemento al frente
r: índice justo después del último elemento
• El valor en el índice r se mantiene vacío
15 0
14 1 configuración normal
13 2 Q
12 3 012 f r
11 4
configuración envuelta
10 5
Q
9 6
8 7 012 r f
Operaciones
• Usamos el Algorithm size()
operador módulo return (N − f + r) mod N
(resto de la Algorithm isEmpty()
división entera) return (f = r)
Q
01 2 f r
Q
01 2 r f
Operaciones
• La operación enqueue
Algorithm enqueue(o)
lanza una excepción
if size() == N then
si el arreglo está
throw "Queue is full!"
lleno
else
• Esta excepción es Q[r] ← o
dependiente de la r ← (r + 1) mod N
implementación
Q
01 2 f r
Q
01 2 r f
Operaciones
• La operación dequeue Algorithm dequeue()
lanza una excepción if isEmpty() then
si la cola está throw "Queue is empty!"
vacía else
• Esta excepción es o ← Q[f]
especificada en el f ← (f + 1) mod N
ADT return o
Q
0 1 2 f r
Q
0 1 2 r f
Ejemplo
front = 0 queue q;
[Link](6); //push
rear = 1
6
0 1 2 3 4 5
Ejemplo
front = 0 queue q;
[Link](6);
rear = 5 [Link](4);
[Link](7);
6 4 7 3 8 [Link](3);
[Link](8);
0 1 2 3 4 5
Ejemplo
front = 2 queue q;
[Link](6);
rear = 0 [Link](4);
[Link](7);
6 4 7 3 8 9 [Link](3);
[Link](8);
0 1 2 3 4 5
[Link](); // front=1
[Link](); // front=2
front = (0+1) % 6 = 1
[Link](9);
front = (1+1) % 6 = 2
rear = (5+1) % 6 = 0
Ejemplo
front = 2 queue q;
[Link](6);
rear = 1 [Link](4);
[Link](7);
5 4 7 3 8 9 [Link](3);
[Link](8);
0 1 2 3 4 5
[Link](); // front=1
[Link](); // front=2
[Link](9);
[Link](5);
rear = (0+1) % 6 = 1
Implementación usando stacks
Algorithm enqueue(o) Algorithm dequeue()
[Link](o) if isEmpty() then
Algorithm size() throw “Queue is empty!”
return [Link]()+ [Link]() if [Link]() then
while ![Link]() do
Algorithm isEmpty() [Link]([Link]())
return (size() == 0) return [Link]()
Nota: En la práctica esta solución no se utiliza. Sin embargo, es un buen
ejercicio para practicar conceptos
En resumen
Lista ligada Lista ligada Arreglo Arreglo Circular 2 stacks
Métodos Node front
int size
Node front
Node tail
Object Q[N]
int size
Object Q[N]
int f
Stack S1
Stack S2
int size int r
enqueue O(n) O(1) O(1)* O(1)* O(1)
dequeue O(1) O(1) O(n) O(1) O(n)
isEmpty O(1) O(1) O(1) O(1) O(1)
size O(1) O(1) O(1) O(1) O(1)
Espacio O(n) O(n) O(N) O(N) O(N)
*
Error si el arreglo está lleno
Ejemplo 2: Round Robin Schedulers
• Podemos implementar un scheduler round
robin usando una queue Q, repitiendo
los siguientes pasos:
1. e = [Link]()
2. Ejecutar elemento e
3. [Link](e)
Deques
Deques
• Una deque es double-ended queue
(pronunciado deck para distinguir del
método dequeue)
• Inserciones y eliminaciones pueden ser
por cualquier extremo
• La implementación es similar a Queue
• No son muy usadas
Double-Ended Queues
• Una double-ended queue, o deque, soporta
insertar y eliminar por el frente o detrás
• El ADT Deque
• insertFirst(e): Insertar por el frente.
• insertLast(e): Insertar por detrás
• removeFirst(): Remover y retornar por el frente
• removeLast(): Remover y retornar por detrás
• Adicionalmente soporta:
• first()
• last()
• size()
• isEmpty()
27
Implementar Deques con Listas Enlazadas Dobles
• No se puede eliminar al final de una lista enlazada simple en
tiempo constante.
• Para implementar Deque, usamos una lista enlazada doble con
nodos especiales apuntando al inicio y final
• Un nodo de una lista enlazada doble tiene punteros next y
prev. Soporta los siguientes métodos:
○ setElement(Object e)
○ setNext(Object newNext)
○ setPrev(Object newPrev)
○ getElement()
○ getNext()
○ getPrev()
• Todos los métodos se ejecutan en tiempo O(1).
header nodes trailer
∅ ∅
elements
Resumen
Lista ligada Lista ligada Arreglo Arreglo Circular
simple doble
Object Q[N] Object Q[N]
Métodos Node front Node front int size int f
int size Node tail int r
int size
insertFirst() O(1) O(1) O(n)* O(1)*
insertLast() O(n) O(1) O(1)* O(1)*
removeFirst() O(1) O(1) O(n) O(1)
removeLast() O(n) O(1) O(1) O(1)
isEmpty() O(1) O(1) O(1) O(1)
size() O(1) O(1) O(1) O(1)
Espacio O(n) O(n) O(N) O(N)
*
Error si el arreglo está lleno
El patrón adaptador
• El patrón adaptador implementa una clase
utilizando los métodos de otra
• Por lo general, las clases adaptadoras
especializan clases generales
• Dos ejemplos de aplicaciones:
• Especializar una clase general modificando métodos.
• Ej: implementar una pila con una deque.
• Especializar el tipo de objetos usados por una
clase general.
• Ej: Definir una clase IntegerArrayStack que adapta
ArrayStack para almacenar solamente enteros.
Implementar pilas y colas
Pilas con Deques
Método de Stack Método de Deque
size() size()
isEmpty() isEmpty()
top() last()
push(e) insertLast(e)
pop() removeLast()
Colas con Deques
Método de Queue Método de Deque
size() size()
isEmpty() isEmpty()
front() first()
enqueue(e) insertFirst(e)
dequeue() removeFirst()
Arreglos dinámicos
N
2N
Implementaciones con arreglos: Arreglo dinámico
• Los arreglos tienen tamaño limitado,
lo que genera excepción por falta de
espacio
• Solución: Reemplacemos el arreglo por
uno más grande cuando agotemos el
espacio
• Consideramos el caso de Stacks:
• En la operación push, si se llena el
arreglo, en lugar de lanzar una Algorithm push(o)
excepción, reemplazamos el arreglo por if t = [Link] − 1 then
uno más grande. A ← new array of size ?
• ¿Qué tan grande debe ser el arreglo? for i ← 0 to t do
A[i] ← S[i]
• Estrategia incremental: Aumentamos el S ← A
tamaño en una constante t ← t + 1
• Estrategia de doblamiento: Doblar el S[t] ← o
tamaño
• El espacio usado por un arreglo
dinámico es O(n)
Estrategia incremental vs doblamiento
• Para comparar, analizaremos el tiempo total
T(n) usado para realizar n inserciones
• Asumimos que comenzaremos con un stack vacío,
con un arreglo de tamaño 1
• Llamaremos tiempo amortizado de una inserción
al tiempo promedio tomado por inserción en la
serie de operaciones, es decir T(n)/n
Análisis de la estrategia incremental
• El arreglo se reemplaza veces
• El tiempo total T(n) se una serie de n
inserciones es proporcional a
• Como c es una constante, T(n) es O(n + k + k2),
i.e., O(n2)
• El tiempo amortizado de una operación es O(n)
Estrategia de doblado
• Reemplazamos el arreglo veces
• El tiempo total T(n) de una serie geometric series
de n inserciones es proporcional a
n + 1 + 2 + 4 + 8 + …+ 2k-1 =
2
n + 2k −1 = 2n −1 4
• T(n) es O(n) 1 1
• El tiempo amortizado de una
inserción es O(1)
8
Tiempo amortizado de insertar
• Estrategia incremental
• n★=n+c
• Tiempo amortizado: O(n)
• Estrategia de doblado
• n★=2n
• Tiempo amortizado: O(1)
• Multiplicar el tamaño por c
• n★=cn
• Tiempo amortizado: O(1)
• ¡Usado en la práctica! ArrayList de Java usa c = 3/y
la lista de Python usa c = 9/8
• ¿Existe otra opción?
• Elevar al cuadrado: n★=n*n
• ¿Tiempo amortizado?
Elevar al cuadrado
N
N2
• Reemplazamos el arreglo k = log2(log2(n)) veces
• El tiempo total T(n) de una serie de n inserciones es
proporcional a
• Log tiene la siguiente propiedad:
• Entonces:
• T(n) es O(n) y por lo tanto el tiempo amortizado es
O(1)