Estructuras Lineales Colas

Estructuras Lineales
Colas, mediante arreglos

Definicion
• En una aplicación informática, una cola es una
lista en la que todas las inserciones a la lista se
realizan por un extremo, y todaslas
eliminaciones o supresiones de la lista se
realizan por el otro extremo.
• Las colas se llaman también estructuras FIFO
(jirst-in, first-ont; primero en entrar, primero
en salir).

TDA:Cola
• Una cola es una lista ordenada de elementos,
en la cual las eliminaciones se realizan en un
solo extremo, llamado frente o principio de la
cola, y los nuevos elementos son aña- didos
por elotro extremo, llamado fondo o jinal de
la cola

Cola: Las operaciones básicas
• Las operaciones básicas que definen la especificación
del TAD cola son:
• Qcrear(Q): Crea la cola Q como colavacía.
• Qvacia(Q): Nos devuelve cierto si la cola está vacía.
• Frente(Q): Devuelve el elemento frente de la cola.
• Qborrar(Q): Elimina el elemento frente de la cola.
• Qanula(Q): Convierte lacola en vacía.
• Quitar(X,Q): Elimina y devuelve el frente de la cola.
• Qponer(X,Q): Añade un nuevo elemento a la cola.

Implementación de las Colas
• la implementación de colas puede hacerseutilizando como «depósito» de los elementos:
• Un array, o
• Una lista enlazada y dos punteros a los
extremos.

IMPLEMENTACiÓN DEL TAD COLA CON
ARRAYS LINEALES
• Estructuras estàticas:
– Un arrayunidimensional cuyo tipo es el mismo
que el tipo de los elementos de la cola

• Son necesarios dos Índices para refe- renciar al
elemento frente y al elemento final.
• El array y las dosvariables Índice se agru- pan
en el tipo registro de nombre cola.

• Añadir elemento

• Eliminar elemento:

• Una alternativa a esta situación es mantener fijo el frente de la cola al
comienzo delarray; este hecho supone mover todos los elementos de la
cola una posición cada vez que se quiera retirar un elemento de la cola.
• Solución: Arrays circulares

• Solución: Arrays circulares...