Colas

SISTEMA DE COLAS
MODELO BASICO

olaSalidas
Sistema de Colas

LLEGADA
S

SALIDAS
Disciplina
COLA
SERVIDOR
De Cola

Colas:
Una cola es un tipo especial de lista
abierta en la que sólo se pueden
insertar nodos en uno de los extremos de
la lista y sólo se pueden eliminar nodos en
el otro. Además, como sucede con las
pilas, las escrituras de datos siempre son
inserciones de nodos, y las lecturassiempre eliminan el nodo leído.

Estructura básica de
un nodo en Lenguaje C
typedef struct _nodo
{ int dato;
struct _nodo *siguiente;
} tipoNodo;

DATO

DATO

DATO

DATO

DATO

Primero
Último

NULL

OPERACIONES BASICAS DE
COLA
De nuevo nos encontramos ante una estructura con
muy pocas operaciones disponibles. Las colas sólo
permiten añadir y leer elementos:
   Añadir: Inserta un elemento al finaldela cola.
  Leer y/o atender: Lee y elimina un elemento del
principio de la cola.

Añadir un elemento a la cola vacía

De nuevo partiremos de un nodo a insertar, con un puntero que apunt
a él, y de una cola, en este caso, al  estar vacía, los punteros primero
y ultimo serán nulos
NODO

DATO

El proceso sigue siendo muy sencillo:
1.Hacemos que nodo->siguiente apunte a NULL.
2.Después queultimo->siguiente apunte a nodo.
3.Y actualizamos ultimo, haciendo que apunte a nodo
NODO

Primero

NULL

DATO
Último

Añadir un elemento a la cola NO
vacía

Añadir elemento en una cola no vacía:
De nuevo partiremos de un nodo a insertar, con un puntero que
apunte a él, y de una cola, en este caso, al no estar vacía, los
punteros primero y ultimo no serán nulos:

DATO
Primero

NULL

DATO

NODO

DATOÚltimo

El proceso es muy simple, bastará con que:
1.Hacemos que nodo->siguiente apunte a NULL.
2.Después que ultimo->siguiente apunte a nodo.
3.Y actualizamos ultimo, haciendo que apunte a nodo

DATO

1

2

DATO

NODO

3

Último

DATO

NULL

Leer un elemento en una cola con más de un
elemento:
Usaremos un puntero a un nodo auxiliar:

DATO
Primero

DATO

DATO

NULL
Último

NODO

1.Hacemos que nodoapunte al primer elemento
de la cola, es decir a primero.
2.Asignamos a primero la dirección del segundo
nodo de la pila: primero->siguiente.

3.Guardamos el contenido del nodo para
devolverlo como retorno, recuerda que la
operación de lectura en colas
implican también borrar.
4. Liberamos la memoria asignada al primer
nodo, el que queremos eliminar.

4

DATO

Primero

2

NODO

1

DATO

DATODATO

3

Leer 1 elemento en 1 cola con un solo
elemento

También necesitamos un puntero a un nodo auxiliar:
DATO

DATO

NULL
Último

Nodo auxiliar

Primero

1.Hacemos que nodo apunte al primer elemento de
la pila, es decir a primero.
2.Asignamos NULL a primero, que es la dirección del
segundo nodo teórico de la cola: primero->siguiente.

3.Guardamos el contenido del nodo para
devolverlo comoretorno, recuerda que la
operación de lectura en colas implican también
borrar.
4.Liberamos la memoria asignada al primer nodo,
el que queremos eliminar.
5.Hacemos que ultimo apunte a NULL, ya que la
lectura ha dejado la cola vacía.

4
Primero

1NODO

DATO

NULL

2

Último

5

3

DATO

Funcion Añadir
void Anadir(pNodo *primero, pNodo *ultimo, int v) {

pNodo nuevo;


/* Crear un nodo nuevo */
nuevo = (pNodo)malloc (sizeof (tipoNodo));
nuevo->valor = v;



/* Este será el último nodo, no debe tener siguiente */



nuevo->siguiente = NULL;
/* Si la cola no estaba vacía, añadimos el nuevo a continuación de
ultimo */

if(*ultimo) (*ultimo)->siguiente = nuevo;


/* Ahora, el último elemento de la cola es el nuevo nodo */
*ultimo = nuevo;





/* Si primero es NULL, la cola estaba vacía,ahora primero
apuntará también al nuevo nodo */
if(!*primero) *primero = nuevo;




}

Funcion leer
int Leer(pNodo *primero, pNodo *ultimo) {
pNodo nodo; /* variable auxiliar para manipular nodo */
int v;
/* variable auxiliar para retorno */
/* Nodo apunta al primer elemento de la pila */
nodo = *primero;
if(!nodo) return 0; /* Si no hay nodos en la pila retornamos 0 */
/* Asignamos a primero...