Colas

📖 Teoría

📖

Una Cola es un TAD lineal de tipo FIFO, lo que quiere decir es que es una lista cuyas operaciones han sido restringidas a solo unas pocas que permitan añadir (encolar) y sacar (desencolar) elementos desde extremos opuestos de la lista

En una cola, la inserción (encolar) se hace desde un extremo de la lista y la extracción (desencolar) desde el extremo opuesto de manera eficiente: $O(1)$

Es una estructura de tipo FIFO (First In First Out), por lo que el primer elemento en ser insertado (encolado) en la estructura será en primero en ser extraido (desencolado). Osea, los elementos se extraen en el mismo orden en el que fueron introducidos

Especificación Algebraica de una Cola

Parámetros Genéricos
TElemento

Tipos
TCola

Operaciones
Constructoras generadoras
crearColaVacia → TCola
encolar: TCola X TElemento → TCola
Observadoras selectoras
(PARCIAL) primero: TCola → TElemento
(PARCIAL) desencolar: TCola → TCola
Observadoras no selectoras
esColaVacia: TCola → boolean
Constructoras Generadoras
copiar: TCola → TCola
destruir: TCola → TCola

Variables
c , c<N> , cola → TCola
e , e<N> → TElemento

Ecuaciones de definitud
DEF ( primero( encolar(c, e) ) )
DEF ( desencolar( encolar(c, e) ) )

Ecuaciones
Observadoras selectoras
primero( encolar(c, e) ) = SI esColaVacia(c) → ( e ) || ( primero(c) )
desencolar( encolar(c, e) ) = SI esColaVacia(c) → ( c ) || ( encolar( desencolar(c), e ) )
Observadoras no selectoras
esColaVacia
esColaVacia( crearColaVacia ) = True
esColaVacia( encolar(c, e) ) = False
esColaIgual
esColaIgual(crearColaVacia, c2) = esColaVacia(c2)
esColaIgual(encolar(c, e), crearColaVacia) = False
esColaIgual(encolar(c1, e1), encolar(c2, e2)) = esElemIgual(e1, e2)
Constructoras no generadoras
copiarCola
copiarCola(crearColaVacia) = crearColaVacia
copiarCola(encolar(c, e)) = encolar(copiarCola(c), e)

📖

Una cola de prioridad es cola en la cual la inserción de nuevos elementos se realiza mediante una busqueda en la lista para encontrar la posición adecuada. La extracción de elementos se realiza desde el principio de la lista

Una cola de prioridad puede insertar elementos en cualquier parte de la cola

Una cola de prioridad solo puede extraer elementos desde el principio de la cola

La prioridad de los elementos de la cola la determinará la unidad correspondiente al elemento, la cual determinará si un elemento tiene mayor prioridad que otro, normalmente a través la el subprograma esMejor(e1, e2)

Si dos elementos tienen la misma prioridad, se respetará el orden de llegada

💡

La cola de prioridad, se comporta como una lista para la inserción, y como una cola para la extracción

Especificación Algebraica de una Cola de Prioridad

Tipos
TColaOrd
TPrioridad

Operaciones
prioridad: TElemento → TPrioridad
esMejor: TElemento X TElemento → boolean

Ecuaciones
Ecuaciones entre generadoras
SI esMejor(e1, e2) → ( encolar(encolar(c, e1), e2) ) || ( encolar(encolar(c, e2), e1) )
Observadoras selectoras
primero(encolar(c, e)) = SI esColaVacia(c) or esMejor(e, primero(c))→ ( e ) || ( primero(c) )
desencolar(insertarOrd(c, e)) = SI esColaVacia(c) or esMejor(e, primero(c))→ ( c ) || ( encolar(desencolar(c), e) )
Observadoras no selectoras
esColaVacia
esColaVacia(crearColaVacia) = True
esColaVacia(insertarOrd(c, e)) = False

⚙️ Implementation

💡

Implementaciones de listas válidas para colas

Desde el principio
Circular estática

Desde el final
Puntero cabecera-final
Ciscular estática
Circular con puntero al final

Interface de la cola

unit uColas;


interface

uses uElementoInt;

type 
   TCola =  record
        primero: ^TNodo;  // Salida de la cola
        ultimo: ^TNodo;   // Entrada a la cola
    end;
   TNodo =  Record
      info:  TElemento;
      sig:  ^TNodo; 
   End;

// Cola normal
procedure CrearColaVacia (var c: tCola);
function EsVacia (c: tCola):boolean; //comprueba si la cola es vacia
procedure Primero (c:tCola; e:tElemento);
procedure Encolar (var c:tCola; e:tElemento);
procedure Desencolar (var c:tCola; e:tElemento);

// Cola de prioridad
procedure InsertarOrdenado (var c: tCola; e: tElemento); 

//===========================IMPLEMENTATION============================
implementation

	// ...

end.

Implementación de una cola

CrearColaVacia

Ajusta los punteros de una cola a NIL

procedure crearVacia (var c: tCola); //crea una cola vacia
begin
  c.primero:= nil; // Estableces el inicio de la cola a nil
  c.ultimo:=nil;   // Estableces el final de la cola a nil
end;

EsColaVacia
Comprueba si la entrada y salida de la cola apuntan a NIL
function esColaVacia(c: TCola):boolean; begin
  esColaVacia:= (c.primero=nil) and (c.ultimo= nil);
end;

Primero
Consulta el primer elemento de la cola (próximo en salir)
procedure primero (c:TCola; e:TElemento); begin
   If not esColaVacia(c) then copiarElemento(e, c.primero^.info);
end;

Encolar

Añadir nuevo elemento a la cola, el nuevo elemento será el último de la cola

procedure Encolar (var c:tCola; e:tElemento);
var aux: ^TNodo;
begin
	// Crea el nodo del nuevo ultimo elemento
  new(aux); 
  copiarElemento(aux^.info, e); 
	aux^.sig := NIL; 

	if not esColaVacia(c) then begin
		// Decir al ultimo elemento de la cola que hay un nuevo nodo detras suya
		c^.ultimo^.sig := aux;
		// Ajustar nuevo ultimo elemento de la lista
		c^.ultimo : = aux;
	end else begin	// Si no había otros elementos antes
      c.primero := aux;
			c.ultimo := aux;
	end;
end;

Desencolar

Saca el primer elemento de la cola y pone al segundo como el nuevo primer elemento de la cola

procedure desencolar (var c:tCola);
var aux: ^TNodo;
begin
	if not esColaVacia(c) then begin
		aux := c.primero;
		c.primero := c.primero^.sig;  // Asignar al segundo como el nuevo primer elemento
		dispose(aux);

		// Si el elemento desencolado era el unico en la cola, apuntar

Implementación de una cola de prioridad

InsertarOrdenado

Este subprograma va a recorrer la lista (cola) para insertar en una el elemento en la posición adecuada

procedure InsertarOrdenado (var c: tCola; e: tElemento); //cola de prioridad
var
    aux, aux2, auxn: ^tNodo;
begin
    aux:= c;

    if (EsVacia(aux)) or (EsMejor(e, aux^.info)) then
        Construir(e,aux) // (e: tElemento; c: tCola)
    else
    begin
      new(auxn);
      Asignar(auxn^.info, e);
      aux2:= aux;
      aux:= aux^.sig;

      while (not EsVacia(aux)) and (not EsMejor(e, aux^.info)) do
        begin
          aux2:= aux;
          aux:= aux^.sig;
        end;
      
      aux2^.sig:= auxn;
      auxn^.sig := aux;
    
    end;
end;