3.3 ColasLic. En C.C. Ann Margareth Meza Rodríguez

Una estructura lineal cuya característica principal es que el acceso a los elementos se realiza en el mismo orden en que fueron almacenados

a1

a2

…

an

También se les denomina

Estructuras FILO (First In Last Out).

Su uso mas común se lleva a cabo en materia de simulación

Operaciones básicas con colas.Los accesos a los elementos de la cola se realizan por un extremo denominado FRENTE, mientras que las inserciones se realizan por el extremo posterior.

a1 a2 a3 … an-2 an-1 an

Frente. Devuelve el elemento del frente. Solo se puede llamar si la cola NO está vacía.

Colocar. Añade un elemento al final de la cola.

Quitar. Elimina el elemento del frente. Solo se puede llamar si la cola NO está vacía.

Vacía. Indica si la cola está vacía.

Frente Colocar

Quitar

a1 a2 a3 … an-2 an-1 anFrente Colocar

SIMPLE

Quitar

a1 a2 a3 … an-2 an-1 anFrente

Colocar

QuitarDOBL

EColocar

Quitar

Frente

Una cola doble es una estructura de datos en la cual las operaciones de agregar y retirar se practican por ambos lados.

Por la forma en que se realizan las operaciones las colas pueden comportarse como pila o como cola.

a5

a4

a3a2

a1

Para crear una cola circular se debe tener el control de tres puntos dentro de la cola que son:

- La posición del primer elemento en la cola (inicio),

- La posición del último elemento en la cola (final) y

- El tamaño de la cola (máximo)

MAX = 5

CIRC

ULA

R

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor.

a5

a4

a3a2

a1

MAX = 5

Los elementos pueden consultarse, añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida.

a5

a4

a3a2

a1

Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

a5

a4

a3a2

a1

a1

a2

a3a4

a5

Para solucionar el problema de desperdicio de memoria se implementaron las colas circulares, en las cuales existe un apuntador desde el último elemento al primero de la cola.

a5

a4

a3a2

a1

Tarea: Verificar si una palabra es un palíndromo.

Una frase o palabra es un palíndromo si “se lee igual” de izquierda a derecha que de derecha a izquierda.

Para resolver esta tarea se debe hacer uso de las funciones desarrolladas en clase para la estructura lineal pila y la estructura lineal cola

TIP. En la pila se extraen los caracteres en orden inverso a la de la inserción, mientras queen la cola se extraen el mismo orden.