Cesar java

Colas

Carlos Delgado Kloos Dep. Ingeniería Telemática Univ. Carlos III de Madrid
cdk@it.uc3m.es Java: Colas / 1

Ejemplo
La cola del autobús La cola de la impresora

cdk@it.uc3m.es

Java: Colas /

2

1

Características
Estructura lineal Acceso de inserción por un extremo y de eliminación por el otro extremo

cdk@it.uc3m.es

Java: Colas /

3

Interfaz para colas
ppublic interface Queue { public int size(); public boolean isEmpty(); public void enqueue(Object o); public Object dequeue() throws QueueEmptyException; public Object front() throws QueueEmptyException; }
cdk@it.uc3m.es Java: Colas / 4

2

Un interfaz y varias implementaciones
Queue

ArrayQueue

LinkedQueue

cdk@it.uc3m.es

Java: Colas /

5

Implementación basada en arrays
top p 10

tail 2 3
1 2

4
3

5
4 5 N-1

tail 8
0

top 5 6 7
N-1

9
1 2 3 4 5

cdk@it.uc3m.es

Java: Colas /

6

3

Implementación basada en listas encadenadas

top

tail

Madrid

Miami

Múnich

cdk@it.uc3m.es

Java: Pilas /

7

Inserción (enqueue)

top

tail n

Madrid

Miami

Múnich

Moscú

cdk@it.uc3m.es

Java: Colas /

8

4Implementación basada en listas
public void enqueue(Object e) { Node n=new Node(e, null); if (isEmpty()) top=n; else tail.setNext(n); tail n; tail=n; size++; }

cdk@it.uc3m.es

Java: Colas /

9

Borrado (dequeue)

top

tail

Madrid

Miami

Múnich

Moscú

cdk@it.uc3m.es

Java: Colas /

10

5

Implementación basada en listas
public Object dequeue() throwsQueueEmptyException { Object temp; if (isEmpty()) throw new QueueEmptyException("vacia"); temp=top.getElem(); top=top.getNext(); size--; if (size==0) tail=null; return temp; }
cdk@it.uc3m.es Java: Colas / 11

Actividad
Ver animaciones de colas:
http://courses.cs.vt.edu/ csonline/DataStructures/ Lessons/ QueuesImplementationView/ applet.html http://www.cs.usask.ca/ http://www cs usask ca/resources/tutorials/ csconcepts/1998_2/queues/java/

cdk@it.uc3m.es

Java: Colas /

12

6

Actividad
Probar el applet DepthBreadth.java que se encuentra en
http://www.faqs.org/docs/javap/c11/s3.html

cdk@it.uc3m.es

Java: Colas /

13

Otros tipos de colas (que ya no son colas)
Colas dobles Colas con prioridad

cdk@it.uc3m.es

Java: Colas /

14

7

Deques (colas dobles)

firstinsertFirst removeFirst

last removeLast

insertLast

cdk@it.uc3m.es

Java: Colas /

15

Interfaz para colas dobles
p public interface Deque { q public int size(); public boolean isEmpty(); public void insertFirst(Object o); public void insertLast(Object o);

cdk@it.uc3m.es

Java: Colas /

16

8

Interfaz para colas dobles
p public Object removeFirst() j throwsDequeEmptyException; public Object removeLast() throws DequeEmptyException; public Object first() throws D th DequeEmptyException; E t E ti public Object last() throws DequeEmptyException; }
cdk@it.uc3m.es Java: Colas / 17

Pilas y colas como deques
Stack
size()

Deque
size()

Queue
size() isEmpty() front() enqueue(e) dequeue()

Deque
size() isEmpty() first() insertLast(e) removeFirst()isEmpty() isEmpty() top() push(e) pop() last() insertLast(e) removeLast()

cdk@it.uc3m.es

Java: Colas /

18

9

Definición de pilas a partir de deques
public class DequeStack implements Stack { private Deque D; public DequeStack() {D=new Deque();} public int size() {return D.size();} public boolean isEmpty() {return D.isEmpty();}
cdk@it.uc3m.es Java: Colas / 19

Definición de pilas apartir de deques
p public void push(Object o){ p j D.insertLast(o);} public Object pop() throws StackEmptyException { try {return D.removeLast();} catch (DequeEmptyException ece) {throw new StackEmptyException("vacia");} }
cdk@it.uc3m.es Java: Colas / 20

10

Definición de pilas a partir de deques
p public Object top() j p() throws StackEmptyException { try {return D.last();} catch...