Estructuras de Datos: Queues

Queue

Los queues son una estructura de datos fisica que trabaja bajo la disciplina FIFO (First In, First Out.)

Los queues tienen dos extremos: front y rear. La insercion se hace en el extremo rear, y la elliminacion en front.

Para definir el queue como una estructura de datos abstracta vamos a necesitar:

1. Espacio para almacenar los elementos.
2. Un pointer front - para hacer la eliminacion.
3. Un pointer rear - para hacer la insercion.

Y las operaciones que se definen son:

1. enqueue (x): insertar un elemento (en el rear).
2. dequeue (): eliminar un elemento (en el front).
3. is_empty ()
4. is_full ()
5. first ()
6. last ()

Los queues se pueden implemenar utilizando ya sean arrays, o linked lists.

Implementacion con Arrays

Queues usando un unico pointer

Para impllementar un queue usando un solo pointer, vamos a tener un array de tamano x y un pointer rear que va a apuntar al ultimo elemento del queue.

Cada vez que se inserta un elemento, se incrementa la posicion de rear y se inserta el elemento. Para eliminar un elemento, se elimina array[0] (porque los queues son FIFO) y los elementos desde 1 a rear se shiftearan para que no haya espacios en blanco, y disminuir la posicion de rear por 1.

En base a eso, insertar un elemento tiene una complejidad de tiempo \(O(1)\), mientras que eliminarlo tiene una complejidad de tiempo \(O(n)\).

Queues usando dos pointers (front y rear)

Para la implementacion de queues usando dos pointers, y reducir la complejidad de tiempo al momento de eliminar lo haremos de la siguiente manera:

De nuevo, tendremos un array de un tamano especificado, y dos pointers front y rear. Al inicializar la estructura ambos seran igual a -1 y cada vez que se agregue un elemento se incrementara por 1 la posicion de rear. Cuando se vaya a eliminar un elemento, simplmenete se incrementa la posicion de front y se devuelve ese valor.

Ahora la insercion y eliminacion de elementos tienen una complejidad de tiempo \(O(1)\).

Demas Operaciones

Para revisar si un queue esta vacio o no, checaremos si tanto front como rear tienen el mismo valor, de asi serlo, el queue estara vacio (para esto, front siempre debera estar antes de la posicion del primer elemento.)

Para revisar si un queue esta lleno, vamos a comparar rear con size - 1, dado el caso que sean iguales, el queue estara lleno.

Implementacion

struct queue
{
  int size;
  int front;
  int rear;
  int *q;
};

struct queue
queue_create (int size)
{
  struct queue q = { 0 };
  q.front = q.rear = -1;
  q.size = size;
  q.q = calloc (size, sizeof (int));
  return q;
}

void
enqueue (int x, struct queue *q)
{
  if (!q || q->rear == q->size - 1)
    return;

  q->q[++q->rear] = x;
}

int
dequeue (struct queue *q)
{
  if (!q || q->front == q->rear)
    return -1;                                                                  /* vacio */

  int x = q->q[++q->front];
  return x;
}

Desventajas de Queues usando Arrays

Una de las desventajas de usar queues usando arrays con dos pointers front y rear es que puede que hayan espacios libres por el lado de front pero no hayan espacios disponibles por rear por lo que no sea posible agregar nuevos elementos, y esa memoria este alojando elementos vacios. Basicamente, no se pueden reutilizar los espacios de elementos eliminados.

La primera solucion para este problema es la de reinicializar los pointers, es decir, cuando se eliminen todos los elementos de un queue, que ambos pointers sean inicializados de nuevo a -1. Aunque esto unicamente es viable cuando en el queue se eiliminan todos los elementos, lo que no quiere decir que siempre este garantizado que no vayan a haber espacios desperdiciados.

Otra de las soluciones es hacer que el queue sea circular, es decir, cuando no hayan espacios dsponibles en el lado de rear, que se mueva de nuevo a 0 y se agreguen elementos antes de front, e igual, cuando front sea igual a size se mueva de nuevo a 0.

Estos indices circulares se pueden obtener con el operador %.

rear = (rear + 1) % size

Ahora las operaciones quedarian asi:

void
enqueue (int x, struct queue *q)
{
  if (!q || (q->rear + 1) % q->size == q->front)
    return; // esta lleno

  q->rear = (q->rear + q) % q->size;
  q->q[q->rear] = x;
}

int
dequeue (struct queue *q)
{
  if (!q || q->front == q->rear)
    return -1;
  q->front = (q->front + 1) % q->size;
  return q->q[q->front];
}

Implementacion con Linked Lists

Para hacer la implementacion de un queue utilizando Linked Lists vamos a necesitar dos pointers: front y rear que apuntan al primer y ultimo nodo respectivamente. El motivo por el que necesitaremos el pointer rear es para hacer la insercion de elementos con una complejidad de tiempo constante.

Cuando el queue esta vacio, tanto front como rear van a ser NULL, por lo que la condicion para revisar si un queue esta vacio, es que front sea NULL. Mientras que la condicion para revisar si un queue esta lleno, es si ya no hay espacio disponible en el heap.

La funcion para insertar un elemento en un queue usando linked lists seria la siguiente:

void
queue_enqueue (int x)
{
  struct node *t = calloc (1, sizeof (*t));
  if (!t)
    return; // queue is full

  t->data = x;
  t->next = NULL;
  if (!front)
    {
      front = rear = NULL; // si el queue esta vacio, tanto front como rear
                           // apuntan al primer nodo.
      return;
    }

  rear->next = t;
  rear = t;
}

Y para eliminar elementos seria la sigueinte:

int
queue_dequeue ()
{
  int x = -1;
  struct node *p = front;
  if (!p)
    {
      return x; // el queue esta vacio
    }

  front = front->next;
  x = p->data;
  free (p);

  return x;
}

Double Ended Queues (DEQueues)

En un DEQueue podemos hacer tanto la insercion como la eliminacion ya sea del lado de front como del lado de rear.

Queues de Prioridad

Un queue de prioridad es un queue donde los elementos son manejados no en el orden en que fueron agregados, sino en una prioridad asignada.

Hay dos formas de implementar un queue de prioridad:

• Un conjunto limitado de prioridades.
• El elemento es una prioridad.

Conjunto Limitado de Prioridades

Supongamos que tenemos elementos con prioridades del 1 al 3 (donde 3 es la mas baja). Como tenemos 3 niveles de prioridades vamos a necesitar 3 queues distintos: Q1, Q2, y Q3.

Cada que vayamos a insertar un elemento vamos a comparar su prioridad, si la prioridad es 1 lo agregamos a Q1, si es 2 lo agregamos a Q2 y si es 3 lo agregamos a Q3.

Cuando se vaya a eliminar un elemento se tiene que hacer el front del queue con mas alta prioridad. Por ejemplo, si vamos a eliminar un elemento, tendremos que hacerlo primero con Q1. Si el queue Q1 esta vacio pasaremos a Q2 y asi suscesivamente.

El Elemento es una Prioridad

Supongamos que tenemos valores numericos del 1 al 10, el valor de cada uno de los elementos es su propia prioridad.

Para insertar elementos podemos hacerlo de dos maneras:

1. Insertar en el orden en el que se hagan las llamadas para insertar, y para eliminar el elemento se busca la prioridad.
2. Insertar en un orden incremental de prioridad, se elimina el ultimo elemento del array.

La diferencia con ambos metodos, es que con uno la complejidad de tiempo para agregar elementos es \(O(1)\) y para eliminarlos es \(O(n)\) y con el otro es al contrario.