Saltearse al contenido

Colas

  • Operaciones básicas: insertar, quitarPrimero y primero.
  • Cada rutina debería ejecutarse en tiempo constante.

Tipo Colas

tipo Cola = registro
Cabeza_de_cola, Final_de_cola : 1..Tamaño_máximo_de_cola
Tamaño_de_cola : 0..Tamaño_máximo_de_cola
Vector_de_cola : vector [1..Tamaño_de_máximo_de_cola] de Tipo_de_elemento
fin registro
colas.h
#define TAMANO_MAXIMO_COLA 5
typedef int tipo_elemento;
typedef struct {
int cabeza, final, tamano;
tipo_elemento vector[TAMANO_MAXIMO_COLA];
} cola;

Crear Cola ( C ) — O(1)

procedimiento Crear Cola ( C ) // O(1)
C.Tamaño_de_cola := 0;
C.Cabeza_de_cola := 1;
C.Final_de_cola := Tamaño_de_máximo_de_cola
fin procedimiento
cola.c
void crear_cola(cola *c) {
c->tamano = 0;
c->cabeza = 0;
c->final = -1;
}

Cola Vacía ( C ) — O(1)

función Cola_Vacía ( C ) : test // O(1)
devolver C.Tamaño_de_cola = 0
fin función
cola.c
int cola_vacia(cola c) {
return (c.tamano == 0);
}

incrementar ( x ) (privado) — O(1)

procedimiento Incrementar ( x ) (* privado *) // O(1)
si C.Tamaño_de_cola = Tamaño_de_máximo_de_cola entonces
error Cola llena
sino
C.Tamaño_de_cola := C.Tamaño_de_cola + 1;
incrementar(C.Final_de_cola);
C.Vector_de_cola[C.Final_de_cola] := x;
fin procedimiento
cola.c
void incrementar(int *x) {
/* privado */
if (++(*x) == TAMANO_MAXIMO_COLA)
*x = 0;
}

Insertar en Cola ( x, C ) — O (1)

procedimiento Insertar_en_Cola ( x, C ) // O(1)
si C.Tamaño_de_cola = Tamaño_de_máximo_de_cola entonces
error Cola llena
sino
C.Tamaño_de_cola := C.Tamaño_de_cola + 1;
incrementar(C.Final_de_cola);
C.Vector_de_cola[C.Final_de_cola];
fin procedimiento
cola.c
void insertar(tipo_elemento x, cola *c) {
if (c->tamano == TAMANO_MAXIMO_COLA) {
printf("error: cola llena: %d\n", c->tamano);
exit(EXIT_FAILURE);
}
c->tamano++;
incrementar(&(c->final));
c->vector[c->final] = x;
}

Quitar Primero ( C ) — O(1)

función Quitar_Primero ( C ) : Tipo_de_elemento // O(1)
si Cola_Vacía ( C ) entonces
error Cola vacía
sino
C.Tamaño_de_cola := C.Tamaño_de_cola - 1;
x := C.Vector_de_cola[C.Cabeza_de_cola];
incrementar(C.Cabeza_de_cola);
devolver x
fin función
cola.c
tipo_elemento quitar_primero(cola *c) {
tipo_elemento x;
if (cola_vacia(*c)) {
printf("error: cola vacia\n");
exit(EXIT_FAILURE);
}
c->tamano--;
x = c->vector[c->cabeza];
incrementar(&(c->cabeza));
return x;
}

Primero ( C ) — O(1)

función Primero ( C ) : Tipo_de_elemento // O(1)
si Cola_Vacía ( C ) entonces
error Cola vacía
sino
devolver C.Vector_de_cola[C.Cabeza_de_cola]
fin función
cola.c
tipo_elemento primero(cola c) {
if (cola_vacia(c)) {
printf("error: cola vacia\n");
exit(EXIT_FAILURE);
}
return (c.vector[c.cabeza]);
}
Pablo Portas López © 2025 licensed under CC BY 4.0