Sé lo que es una cola y lo que es un arreglo, pero no entiendo la unión de ambos, necesito que me expliquen dicho proceso con ejemplos cotidianos.
2 respuestas
Con una simple imagen se aclara todo:
La relación con un arreglo es simple:
Encolar
Colocar un nuevo elemento al final del arreglo.
Desencolar
Obtener el primer elemento del arreglo.
Dependiendo de la implementación que uses, este último paso puede implicar mover todos los elementos del arreglo 1 posición hacia abajo.
Tamaño de la cola
Número de elementos máximos que caben en el arreglo.
Elementos en la cola
Número de elementos ocupados en el arreglo. El resto serán huecos libres.
Ejemplos de la vida diaria
Los que quieras, cualquier cola o fila de espera te sirve: fila en las cajas, fila para entrar al autobus ... cualquier espera en el que el primero abandona la cola y los demás avanzan una posición. Los nuevos que van llegando se colocan al final.
Página de la Wikipedia sobre colas, de donde obtuve la imagen.
Tanto en C como en C++ los objetos simples se pueden crear en el stack (la pila) o en el heap (memoria dinámica).
En el primer caso los objetos los estaremos usando por valor, que es el caso típico que uno encuentra al aprender a programar:
int main()
{
int var = 1; // Variable declarada en la pila
printf("%d",var);
}
El problema lo encontramos al usar tipos compuestos (listas, vectores, matrices)... Ninguno de los dos lenguajes dispone de un tipo nativo para gestionar este tipo de objetos y en su lugar se recurre a los punteros:
int main()
{
int lista[10]; // Aunque no lo parezca esto es un puntero
int* ptr = lista; // Y la prueba está en que aquí no hay error
for( int i=0; i<10; i++)
*ptr = i;
for( int i=0; i<10; i++)
printf("%d\n", lista[i]);
}
NOTA: No voy a entrar en detalles sobre cómo gestionan C o C++ el uso de arreglos de tamaño fijo... si hay dudas al respecto es preferible abrir una nueva pregunta.
El caso es que una cola suele ser, básicamente, una lista no ordenada de elementos y por lo que acabamos de ver, la única forma de gestionar una lista es mediante arreglos ya que el lenguaje no dispone de un tipo nativo específico para este menester.
Un ejemplo muy sencillo de cola (basada en un buffer circular) podría ser entonces :
int cola[10]; // arreglo de 10 elementos
int push;
int pop;
void Inicializar()
{
push = 0;
pop = -1;
}
void Push(int numero)
{
if( push != pop ) // Cola llena
cola[push] = numero;
if( pop == -1 )
pop = push; // Ya hay elementos a extraer de la cola
push = (push+1)%10;
}
int Pop()
{
int toReturn = -1; // Valor a devolver si la cola está vacía
if( pop != -1 )
{
toReturn = cola[pop];
pop = (pop+1)%10;
if( pop == push )
pop = -1; // Si hemos extraido el último indicamos que está vacía
}
return toReturn;
}
Y una prueba de uso:
int main()
{
Inicializar();
Push(2);
Push(4);
printf("%d\n",Pop()); // 2
printf("%d\n",Pop()); // 4
printf("%d\n",Pop()); // -1
}