Ingenieria de software

Colas

Pila

1

UVM

3.1 Objetivos
El estudiante manejará el tad Cola, sobre memoria estática

Pila

3

UVM

3.2 Temas a Cubrir
Definición Operaciones sobre Colas
  


Encolar (enqueue) Desencolar (dequeue) Primero (front) Último (rear) Vacía? (empty)

Implementación de Colas
Pila 4 UVM

3.3 Definición
Una cola (queue en inglés) es una estructura de datosen la que el modo de acceso a sus elementos es de tipo FIFO (del inglés First In First Out, primero en entrar, primero en salir) que permite almacenar y recuperar datos.

Pila

5

UVM

3.4Operaciones sobre Colas
Encolar (enqueue) Desencolar (dequeue) Primero (front) Último (rear) Vacía? (empty)

Pila

6

UVM

3.4.1 Encolar (enqueue)
Esta operación sirve para insertar unelemento e en la cola q enqueue(Q, e)

Pila

7

UVM

3.4.2 Desencolar (dequeue)
Se usa para retirar un elemento de la cola Q y asignarlo a una variable del mismo tipo que el tipo de loselementos de la cola v = dequeue(Q);

Pila

8

UVM

3.4.3 Primero (front)
La operación front(Q) devuelve el valor del primer elemento de la cola Q. v=front(Q)

Pila

9

UVM

3.4.4 Último(rear)
La operación rear(Q) devuelve el valor del último elemento de la cola Q. v=rear(Q)

Pila

10

UVM

3.4.5 Vacía? (empty)
Toma como argumento una estructura del tipo cola (queue) ydevuelve un valor booleano: true si la cola está vacía o false si la cola tiene al menos un elemento

Pila

11

UVM

3.4.5 Ejemplos
Cola de Impresión Cola de Procesos en un S. O. Mensajes devoz en una contestadora telefónica

Pila

12

UVM

3.5 Implementación de Colas

#define MAXQUEUE 100 struct queue { int items[MAXQUEUE]; int front, rear; } ; struct queue Q; Q.front =Q.rear = -1;

Pila

13

UVM

3.5.1 enqueue
void enqueue(struct queue *Q, int e){ Q->items[++Q->rear]=e; }

Pila

14

UVM

3.5.2 dequeue
int dequeue(struct queue *Q){ return...