Programacion

Estructuras Fundamentales de
Datos
Colas Circulares
Universidad Politécnica de Tlaxcala
Ingeniería en Tecnologías de la Información
M. C. Augusto Meléndez Teodoroaugustu.melendez@uptlax.edu.mx

M. C. Augusto Meléndez Teodoro - TI's - UPTx

1

Febrero de 2013

Introducción (I)
 En muchas ocasiones el uso de una cola simple es ineficiente ya
que se desperdiciaespacio en memoria.
 Cuando insertamos vamos moviendo Final y cuando eliminando
datos movemos a Frente.
 En algún momento, tendremos posiciones inaccesibles debido
a las posiciones deFrente y Final.
R

T

A

0
Frente

1

2

M. C. Augusto Meléndez Teodoro - TI's - UPTx

N
3
Final

Max
2

R

T

0

Eliminar R, T

1

A

N

2
3 Max
Frente FinalIntroducción (II)
 Una cola circular es una estructura en la que el sucesor de la
última posición del arreglo es la primera, de tal forma que
optimiza el uso del espacio del arregloimplementado en la
cola.
 Insertamos el nuevo dato en la primer posición del arreglo y
desplazamos a Final a esa posición.
 Al hacer este recorrido, nuestro nuevo inicio es la posición deFrente, y al llegar al límite de la cola, se reinicia en la celda 0
(cero) hasta encontrar el Final.
M. C. Augusto Meléndez Teodoro - TI's - UPTx

3

Introducción (III)
 Porejemplo, insertemos el dato B.
R

T

0

1

A

N

Insertar B

M. C. Augusto Meléndez Teodoro - TI's - UPTx

4

T

0
Final

2
3 Max
Frente Final

B

1

A

N

2
3Frente

Max

Introducción (IV)

M. C. Augusto Meléndez Teodoro - TI's - UPTx

5

Diagrama de Clase
ClaseColaCircular
Tam: int
Frente: int
Final: int
Arreglo: []intClaseColaCircular(Tam: int)
estaVacia(): bool
estaLlena(): bool
Insertar(dato: int): void
Eliminar(): int
Mostrar(): void
Vaciar(): void
M. C. Augusto Meléndez Teodoro - TI's - UPTx

6