Colas (Queues)#

Objetivos

Objetivo 1…
Objetivo 2…

1. Introduccion#

Una cola (queue en inglés) es una lista ordenada en la cual las operaciones de inserción se efectúan en un extremo llamado ultimo (last, rear o tail) y las operaciones de borrado se efectúan en el otro extremo llamado primero (first, front o head). Es una estructura FIFO (First Input First Output).

../_images/CH_02-S08-Q_fig1.jpg — Fig. 109 Representación de una cola en la vida real#

Una metáfora de esta terminología es una fila de las que se hace en los bancos cuando se esta haciendo en alguna diligencia. Tal y como sucede en la vida real; para el caso, una fila tiene dos extremos (tal y como se muestra en la figura anterior). En una cola. Cuando se esta haciendo una fila en un banco, y el cajero esta libre, este llama a la primera persona que se encuentra en la fila para ser atendida, una vez esta persona sale de la fila (es desencolada de la fila), la persona que seguia (segunda previamente) es colocada de primera a la espera de ser llamada. Por otro lado, cada vez que llega una persona a la fila, esta se ubica al final (se encola en la fila) haciendo que la fila crezca. La siguiente figura muestra un ejemplo de casos como estos:

../_images/CH_02-S08-Q_fig1a.png — Fig. 110 Casos de aplicación de una cola#

2. Sobre las colas (queues)#

Cuando hablamos de colas tenemos que tener en cuenta que se hace alución a un espacio de datos (buffer) donde se colocan datos de determinada manera tal y como se muestra en la siguiente representación:

../_images/CH_02-S08-Q_fig2.png — Fig. 111 Representación de una cola#

De la figura anterior podemos observar se usan tres variables para definir las caracteristicas de la cola:

buffer: espacio de memoria donde se ponen los datos.
tail: Variable que apunta al ultimo dato del buffer.
head: Variable que apunta al primer dato del buffer.

Por otro lado, para meter o sacar datos al buffer, se definen dos operaciones las cuales son:

Enqueue (Encolar): agrega un nuevo elemento al final de la cola.
Dequeue (Desencolar): elimina el primero de la cola y lo devuelve.

A continuación vamos a describir la implementación de la cola en C.

2. Implementación de una cola#

2.1. Implementación a partir array#

2.1.1. Definición de la cola#

La siguiente estructura se define una cola (stack) de tamaño fijo (CAPACITY = 4) cuyos miembros son:

count: Catidad de elementos agregados a la pila.
head: Indice asociado al primer elemento de la pila.
tail: Indice asociado al ultimo elemento de la pila.
list: Buffer donde se almacenan los datos agregados a la pila.

La implementación en C se muestra a continuación:

#define CAPACITY 4

typedef struct _queue {
    int count;
    int head;
    int tail;
    int list[CAPACITY];
} queue;

La siguiente figura muestra la estructura asociada a la cola (queue) previamente definida:

../_images/CH_02-S08-Q_array_fig1.png — Fig. 112 Implementación de una cola usando un array#

Simulación

En el siguiente link se muestra una simulación de una cola mediante un array.

La siguiente figura muestra en caso de simulación de una cola implementada mediante arrays:

../_images/CH_02-S08-Q_array_fig2a.png — Fig. 113 Simulación de una cola usando arrays#

2.1.2. Funciones de la cola#

Las operaciones basicas asociadas sobre la cola (queue) se resumen en la siguiente tabla:

Operación	Descripción
`void Queue_init(queue *q)`	Inicializa la cola `q`
`int Queue_isEmpty(queue *q)`	Retorna verdadero si la cola `q` esta vacia.
`int Queue_isFull(queue *q)`	Retorna verdadero si la cola `q` esta llena.
`int Queue_size(queue *q)`	Retorna el tamaño de la cola.
`int Queue_head(queue *q)`	Devuelve el valor del primer elemento de la cola `q`.
`int Queue_back(queue *q)`	Devuelve el valor del ultimo elemento de la cola `q`.
`void Queue_enqueue(queue *q, int data)`	Agrega un elemento con valor entero `data` al final de la cola `q`.
`int Queue_dequeue(queue q, int data)`	Elimina el primer elemento de la cola `q`.
`void Queue_clear(queue *q)`	Limpia la cola `q`.
`void Queue_print(queue *q)`	Imprime el contenido de la cola `q`.

A continuación, se describe la implementación en C de cada una de las funciones previamente descritas:

Queue_init: Inicializa la cola (queue).
```
void Queue_init(queue *q) {
  q->head = 0;
  q->tail = CAPACITY - 1;
  q->count = 0;
}
```
La siguiente figura muestra el estado de la cola al ser inicializada.

Fig. 114 Inicialización de la cola.#

Queue_isEmpty: Devuelve 1 si la cola esta vacia o 0 en caso contrario.

int Queue_isEmpty(queue *q) {
  return (q->count == 0);
} 

Queue_isFull: Devuelve 1 si la cola esta llena o 0 en caso contrario.

int Queue_isFull(queue *q) {
  return (q->count == CAPACITY);
} 

Queue_size: Devuelve el tamaño de la cola.

int Queue_size(queue *q) {
  return CAPACITY;
}

Queue_head: Devuelve el valor del dato contenido en el primer nodo de la cola.

int Queue_head(queue *q) {
  assert(!Queue_isEmpty(q));
  return q->list[q->head];
}

Queue_back: Devuelve el valor del dato asociado al ultimo nodo de la cola.

int Queue_back(queue *q) {
  assert(!Queue_isEmpty(q));
  return q->list[q->tail];
}

Queue_enqueue: Agrega un nodo con valor data al final de la cola. En caso de que la cola se encuentre llena imprime un mensaje de error y sin modificar la cola.
```
void Queue_enqueue(queue *q,  int data) {  
  if(!Queue_isFull(q)) {
    q->tail = (q->tail + 1) % CAPACITY; 
    q->count++;
    q->list[q->tail] = data;   
  }
  else {
    printf("ERROR: Full queue\n");
  }
}
```
Para comprender la función anterior analicemos los siguientes escenarios.

Suponiendo que se parte de una cola q vacia, al insertar un elemento con valor 19, la estructura de datos asociada a la cola se actualiza tal y como se muestra en la siguiente figura.

Fig. 115 Inserción del 19 en la cola#

Notese que el contador de elementos (count) que actualmente estan en la cola se actualiza a 1 y lo mismo sucede con el indice tail, el cual se asocia al elemento acabado de agregar. La siguiente figura muestra el caso en el cual, se inserta nuevamente otro dato (45) en el caso.

Fig. 116 Inserción del 45 en la cola#

Notese que ya hay dos elementos (count = 2) y el indice del ultimo elemento en el array ya corresponde a valor recien agregado (45).

La siguiente figura muestra el ultimo caso en el cual se agregan los valores 13 y 7 respectivamente, observe como queda la cola al final.

Fig. 117 Inserción de los numeros 13 y 7 en la cola#

Es importante recordar que si la cola esta llena (estado anterior), se intenta agregar un nuevo elemento a la cola, se mostrara un mensaje de error y esta permancecera sin alterarse.
Queue_dequeue: Saca el primer elemento de la cola. El valor asociado al elemento que se saca de la cola es devuelto a traves del apuntador data (parametro por referencia de la función Queue_dequeue). Si la operación es exitosa se devuelve un 0, en caso contrario se devuelve un -1 y se muestra en pantalla el motivo del error.
```
int Queue_dequeue(queue *q, int *data) {
  if (!Queue_isEmpty(q)) {
      q->count--;
      *data = q->list[q->head];
      q->head = (q->head + 1) % CAPACITY;
      return 0;
  }
  else {
      printf("ERROR: Empty queue\n");
      return -1;
  }
}
```
Suponiendo que se tiene una cola Q con los elementos: 19, 45, 13, 7 y se saca el primer elemento mediante la invocación de la función desencolar, se actualiza el numero de elementos (validos) que la cola tiene actualmente pasando count de 4 a 3 y actualizando el indice head para que apunte al proximo elemento a sacar del array (45 ya que head = 1) la proxima vez que se llame nuevamente la función desencolar. Aunque el valor de que se saco (19) permanece en el array, este sera un valor invalido y llegado el momento sera sobreescrito por un nuevo valor que sea encolado.

Fig. 118 Sacando el primer elemento (19) de la cola#
Queue_clear: Vacia la cola inicializando los indices al valor original invalidando todos los valores que quedan en el buffer asociado a la cola.
```
void Queue_clear(queue *q) {
  q->head = 0;
  q->tail = CAPACITY - 1;
  q->count = 0;
} 
```

Queue_print: Imprime el contenido de la cola.

void Queue_print(queue *q) {
  if(Queue_isEmpty(q)) {
    printf("Empty queue.\n");
  }
  else {
    // head - tail
    if(q->head < q->tail) {
      printf("<-- ");
      for(int i = q->head; i <= q->tail; i++){
        printf("%4d    ", q->list[i]);
      }
      printf("<-- \n");            
    }
    else {
      int i;
      printf("<-- ");
      for(i = q->head; i < CAPACITY; i++){
        printf("%4d    ", q->list[i]);
      }
      for(i = 0; i <= q->tail; i++) {
        printf("%4d    ", q->list[i]);
      }
      printf("<-- \n");    
    }
  }
}

2.1.3. Ejemplos#

En el siguiente ejemplo se muestra la implementación y manipulación de una cola usando las estructuras y funciones anteriormente descritas:

El código del ejemplo, con sus respectivos comentarios, se muestra a continuación:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define CAPACITY 4

typedef struct _queue {
  int count;
  int head;
  int tail;
  int list[CAPACITY];
} queue;

/*
Funciones de manipulación de la cola
*/
void Queue_init(queue *q);
int Queue_isEmpty(queue *q); 
int Queue_isFull(queue *q);
int Queue_size(queue *q);
int Queue_head(queue *q);
int Queue_back(queue *q);
void Queue_enqueue(queue *q,  int data);
int Queue_dequeue(queue *q, int *data);
void Queue_print(queue *q);
void Queue_clear(queue *q);

/* 
Función principal
*/
int main(int argc, char *argv[]) {
  queue Q;
  Queue_init(&Q);                      // La cola creada tiene 4 elementos --> [] -->
  if(Queue_isEmpty(&Q)) {
    printf("La cola esta vacia\n");
  }
  else if(Queue_isFull(&Q)) {
    printf("La cola esta llena\n");
  }
  printf("Tamaño de la cola Q: %d\n",Queue_size(&Q));
  // Agregando elementos a la cola
  Queue_enqueue(&Q, 19);               // --> [19] -->
  Queue_enqueue(&Q, 45);               // --> [45, 19] -->
  Queue_enqueue(&Q, 13);               // --> [13, 45, 19] -->
  Queue_enqueue(&Q, 7);                // --> [7, 13, 45, 19] -->
  // Despliegue de la cola
  Queue_print(&Q);
  // Mostrando el primer y ultimo elemento de la cola
  printf("Primer elemento de la cola: %d\n",Queue_head(&Q));
  printf("Ultimo elemento de la cola: %d\n",Queue_back(&Q));
  // Verificando si la cola esta llena
  if(Queue_isFull(&Q)) {
    printf("La cola esta llena\n");
  }
  // Encolando un dato cuando la cola esta llena
  Queue_enqueue(&Q, 21);
  // Sacando un dato de la cola (desencolar)
  int data;  // Valor en el que se llevara el dato sacado.
  Queue_dequeue(&Q, &data);            // --> [7, 13, 45] -->
  printf("Dato sacado de la cola: %d\n",data);
  // Despliegue de la cola
  Queue_print(&Q);
  // Encolando un nuevo dato
  data = 21;
  printf("Metiendo el %d a la cola \n", data);
  Queue_enqueue(&Q, data);              // --> [21, 7, 13, 45] -->
  Queue_print(&Q);
  // Vaciando la cola
  Queue_clear(&Q);
  if(Queue_isEmpty(&Q)) {
    printf("La cola esta vacia\n");
  }
  return 0;
}

void Queue_init(queue *q) {
  q->head = 0;
  q->tail = CAPACITY - 1;
  q->count = 0;
}

int Queue_isEmpty(queue *q) {
  return (q->count == 0);
} 

int Queue_isFull(queue *q) {
  return (q->count == CAPACITY);
} 

int Queue_size(queue *q) {
  return CAPACITY;
}

int Queue_head(queue *q) {
  assert(!Queue_isEmpty(q));
  return q->list[q->head];
}

int Queue_back(queue *q) {
  assert(!Queue_isEmpty(q));
  return q->list[q->tail];
}

void Queue_enqueue(queue *q,  int data) {  
  if(!Queue_isFull(q)) {
    q->tail = (q->tail + 1) % CAPACITY; 
    q->count++;
    q->list[q->tail] = data;   
  }
  else {
    printf("ERROR: Full queue\n");
  }
}

int Queue_dequeue(queue *q, int *data) {
  if (!Queue_isEmpty(q)) {
    q->count--;
    *data = q->list[q->head];
    q->head = (q->head + 1) % CAPACITY;
    return 0;
  }
  else {
    printf("ERROR: Empty queue\n");
    return -1;
  }
}

void Queue_print(queue *q) {
  if(Queue_isEmpty(q)) {
    printf("Empty queue.\n");
  }
  else {
    // head - tail
    if(q->head < q->tail) {
      printf("<-- ");
      for(int i = q->head; i <= q->tail; i++){
        printf("%4d    ", q->list[i]);
      }
      printf("<-- \n");            
    }
    else {
      int i;
      printf("<-- ");
      for(i = q->head; i < CAPACITY; i++){
        printf("%4d    ", q->list[i]);
      }
      for(i = 0; i <= q->tail; i++) {
        printf("%4d    ", q->list[i]);
      }
      printf("<-- \n");    
    }
  }
}

void Queue_clear(queue *q) {
  q->head = 0;
  q->tail = CAPACITY - 1;
  q->count = 0;
} 

La salida al ejecutar el código anterior, se muestra a continuación:

La cola esta vacia
Tamaño de la cola Q: 4
<--   19      45      13       7    <--
Primer elemento de la cola: 19
Ultimo elemento de la cola: 7
La cola esta llena
ERROR: Full queue
Dato sacado de la cola: 19
<--   45      13       7    <--
Metiendo el 21 a la cola
<--   45      13       7      21    <--
La cola esta vacia

2.2. Implementación como lista enlazada#

La siguiente figura muestra una cola implementada usando un lista enlazada:

../_images/CH_02-S08-Q_fig3a.png — Fig. 119 Cola implementada por medio de una lista enlazada.#

Simulación

En el siguiente link se muestra una simulación de una cola mediante una lista enlazada.

2.2.1 Estructuras asociadas la cola#

Inicialmente vamos a describir las estructuras y funciones por medio de las cuales se implementa la cola (queue).

2.2.1.1. Nodo (`node`)#

La estructura asociada al nodo nodo (node) se muestra a continuación:

../_images/CH_02-S08-Q_fig3.png — Fig. 120 Estructura de un nodo (`node`)#

El siguiente fragmento de código muestra la implementación en lenguaje C del nodo:

struct _node {
    int data;
    struct _node* next;
};

typedef struct _node node;

Los miembros (de la estructura node) data y next hacen referencia a los datos y el proximo nodo (node)

2.2.1.2. Cola#

La siguiente figura muestra la implementación de una estructura de datos tipo cola (queue)

../_images/CH_02-S08-Q_fig4.png — Fig. 121 Representación de una cola (`queue`) mediante listas enlazadas.#

La definición en lenguaje C de la estructura queue se muestra a continuación:

typedef struct _queue {
    node *head;
    node *tail;
} queue;

Luego, usando esta estructura de datos, podemos definir las funciones necesarias para su manipulación.

2.2.2 Funciones#

Las operaciones basicas asociadas sobre una lista enlazada se muestran a continuacion:

Operación	Descripción
`void Queue_init(queue *q)`	Inicializa la cola `q`
`int Queue_isEmpty(queue *q)`	Retorna verdadero (`1`) si la cola q esta vacia.
`int Queue_size(queue *q)`	Devuelve el tamaño (numero de elementos) de la cola `q`.
`int Queue_front(queue *q)`	Devuelve el valor del primer elemento de la cola `q`.
`int Queue_back(queue *q)`	Devuelve el contenido del último elemento de la cola `q`.
`void Queue_enqueue(queue *q, int data)`	Agrega un elemento con contenido `data` al final de la cola `q`.
`int Queue_dequeue(queue q, int data)`	Elimina el primer elemento de la cola `q`.
`void Queue_print(queue *q)`	Imprime el contenido de la cola `q`.
`void Queue_clear(queue *q)`	Vacia la cola `q` eliminando sus elementos.

A continuación se muestra la implementación en C de cada una de las funciones anteriormente descritas.

Queue_init: Inicializa la cola colocando los punteros head y tail en NULL.
```
void Queue_init(queue *q){
  q->head = NULL;
  q->tail = NULL;
}
```
La siguiente muestra el resultado de la invocación de la función anterior:

Fig. 122 Inicializacón de la cola (queue)#

Queue_isEmpty: Determina si la cola esta vacia devolviendo 1 en caso de que lo este y 0 en caso contrario.

int Queue_isEmpty(queue *q) {
  if ((q->head == q->tail) & (q->head == NULL)) {
      return 1;
  }
  else {
      return 0;
  }
} 

Queue_size: Devuelve el numero de nodos que hay la cola.

int Queue_size(queue *q) {
  int tam = 0;
  if (q->head == NULL) {        
      return 0;
  } 
  else {      
    node *current = q->head;
    while (current) {
      tam++;
      current = current->next;
    } 
    return tam;
  } 
}

Queue_front: Devuelve el contenido almacenado en el primer nodo de la cola.

int Queue_front(queue *q) {
  assert(q->head != NULL);
  return q->head->data;
}

Queue_back: Devuelve el contenido almacenado en el último nodo de la cola.

int Queue_back(queue *q) {
  assert(q->head != NULL);
  return q->tail->data;
}

Queue_enqueue: Agrega un nodo con valor data al final de la cola.
```
void Queue_enqueue(queue *q,  int data) {  
  node *new = malloc(sizeof(node));
  assert(new != NULL);
  new->data = data;
  if (q->head != NULL) {
    // El resto de los elementos
    new->next = NULL;
    q->tail->next = new;
    q->tail = new;
  }
  else {
    // Primer elemento    
    new->next = NULL;        
    q->head = q->tail = new;   
  }
}
```
Suponiendo que se tiene una cola cuyos elementos son 45, 13 y 7 tal y como se muestra en la siguiente figura.

Fig. 123 Estado inicial de la cola.#

Si se desea encolar un nuevo dato (21) tal y como se muestra en la siguiente figura:

Fig. 124 Encolando un dato#

Se recuerre a llamar la función Queue_enqueue de tal manera que si el resultado es el esperado, este elemento se agrega a la lista enlazada que implementa la cola y el apuntador que indica el final de la lista (tail) se actualiza para apuntar a este elemento recien agregado tal y como se muestra en la siguiente figura:

Fig. 125 Estado de la cola despues de que se mete el dato en la cola#
Queue_dequeue: Saca el primer elemento de la cola. El valor asociado al elemento que se saca de la cola es devuelto a traves del apuntador data (parametro por referencia de la función Queue_dequeue). Si la operación es exitosa se devuelve un 0, en caso contrario se devuelve un -1 y se muestra en pantalla el motivo del error.
```
int Queue_dequeue(queue *q, int *data) {
  if (q->head == NULL) {
      printf("ERROR: Empty Queue\n");
      return -1;
  }
  else {
      node *current = q->head;
      q->head = current->next;
      *data = current->data;
      free(current);
      return 0;
  }
}
```
Para ver comprender esta función; supongamos que inicialmente se tiene una cola cuyos elementos son: 19, 45, 13 y 7 tal y como se muestra en la siguiente figura.

Fig. 126 Estado inicial de la cola.#

Cuando se invoca la función para desencolar, saca obtiene el dato (19 en el caso) asociado al primer nodo (el cual es eliminado) de la cola y se actualiza el puntero head para que apunte al siguiente nodo tal y como se muestra a continuación:

Fig. 127 Estado de la cola despues de que se mete el dato en el buffer.#

Queue_print: Imprime el contenido de la cola.

void Queue_print(queue *q) {
  node *current = q->head;
  if (current == NULL) {
      printf("Empty queue.\n");
      return;
  } 
  else { 
      printf("<-- ");
      while (current) {
          if(current) { 
              printf("%4d    ", current->data);
          }
          current = current->next;
      } 
      printf("<-- \n");
  } 
}

Queue_clear: Función que limpia la cola eliminando todos sus elementos.

void Queue_clear(queue *q) {
  int dummy_data;
  while(!Queue_isEmpty(q)) {
      if(!Queue_dequeue(q, &dummy_data)) {
          break;
      }
  }
  q->head = NULL;
  q->tail = NULL;
}

2.2.3. Ejemplos#

En el siguiente código se muestra un ejemplo donde se hace uso de una cola implementada usando una lista enlazada.

A continuación se muestra el fragmento de código donde se ejemplifica la cola y las funciones asociadas a esta:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

struct _node {
  int data;
  struct _node* next;
};

typedef struct _node node;

typedef struct _queue {
  node *head;
  node *tail;
} queue;

void Queue_init(queue *q);
int Queue_isEmpty(queue *q); 
int Queue_size(queue *q);
int Queue_front(queue *q);
int Queue_back(queue *q);
void Queue_enqueue(queue *q,  int data);
int Queue_dequeue(queue *q, int *data);
void Queue_print(queue *q);
void Queue_clear(queue *q);

int main(int argc, char *argv[]) {
  queue* Q = (queue*)malloc(sizeof(queue));
  assert(Q != NULL);
  // Inicializacion de la cola
  Queue_init(Q);                  // --> [(T) -> | | -> (H)] -->
  if(Queue_isEmpty(Q)) {
    printf("La cola esta vacia\n");
  }
  else {
    printf("La cola tiene elementos\n");
  }
  printf("Tamaño Q: %d\n",Queue_size(Q));    
  // Agregando elementos a la cola
  Queue_enqueue(Q, 19);         // --> [(T) -> |19| -> (H)] -->
  Queue_enqueue(Q, 45);         // --> [(T) -> |45 --> 19| -> (H)] -->
  Queue_enqueue(Q, 13);         // --> [(T) -> |13 --> 45 --> 19| -> (H)] -->
  Queue_enqueue(Q, 7);          // --> [(T) -> |7 --> 13 --> 45 --> 19| -> (H)] -->
  printf("Tamaño Q: %d\n",Queue_size(Q));
  printf("Primer elemento de Q: %d\n",Queue_front(Q));
  printf("Ultimo elemento de Q: %d\n",Queue_back(Q));
  Queue_print(Q);
  int data;
  Queue_dequeue(Q, &data);      // --> [(T) -> |7 --> 13 --> 45| -> (H)] -->
  printf("Dato sacado: %d (elementos disponibles: %d)\n",data, Queue_size(Q));
  Queue_print(Q);    
  Queue_dequeue(Q, &data);      // --> [(T) -> |7 --> 13| -> (H)] -->
  printf("Dato sacado: %d (elementos disponibles: %d)\n",data, Queue_size(Q));
  Queue_print(Q);    
  Queue_dequeue(Q, &data);      // --> [(T) -> |7| -> (H)] -->
  printf("Dato sacado: %d (elementos disponibles: %d)\n",data, Queue_size(Q));
  Queue_print(Q);    
  Queue_dequeue(Q, &data);      // --> [(T) -> | | -> (H)] -->
  printf("Dato sacado: %d (elementos disponibles: %d)\n",data, Queue_size(Q));
  Queue_print(Q);    
  Queue_dequeue(Q, &data);      // --> [(T) -> | | -> (H)] -->
  data = 1;
  Queue_enqueue(Q, data++);     // --> [(T) -> |1| -> (H)] -->
  Queue_enqueue(Q, data++);     // --> [(T) -> |2 --> 1| -> (H)] -->
  Queue_enqueue(Q, data++);     // --> [(T) -> |3 --> 2 --> 1| -> (H)] -->
  Queue_print(Q);    
  printf("Vaciando la cola de %d elementos\n",Queue_size(Q));
  Queue_clear(Q);                // --> [(T) -> | | -> (H)] -->
  printf("Numero de elementos en la cola: %d\n",Queue_size(Q));
  Queue_print(Q);   
  assert(Q!=NULL);  
  free(Q);
  return 0;
}

void Queue_init(queue *q){
  q->head = NULL;
  q->tail = NULL;
}

int Queue_isEmpty(queue *q) {
  if ((q->head == q->tail) & (q->head == NULL)) {
    return 1;
  }
  else {
    return 0;
  }
} 

int Queue_size(queue *q) {
  int tam = 0;
  if (q->head == NULL) {        
    return 0;
  } 
  else {      
    node *current = q->head;
    while (current) {
      tam++;
      current = current->next;
    } 
    return tam;
  } 
}

int Queue_front(queue *q) {
  assert(q->head != NULL);
  return q->head->data;
}

int Queue_back(queue *q) {
  assert(q->head != NULL);
  return q->tail->data;
}

void Queue_enqueue(queue *q,  int data) {  
  node *new = malloc(sizeof(node));
  assert(new != NULL);
  new->data = data;
  if (q->head != NULL) {
    // El resto de los elementos
    new->next = NULL;
    q->tail->next = new;
    q->tail = new;
  }
  else {
    // Primer elemento    
    new->next = NULL;        
    q->head = q->tail = new;   
  }
}

int Queue_dequeue(queue *q, int *data) {
  if (q->head == NULL) {
    printf("ERROR: Empty Queue\n");
    return -1;
  }
  else {
    node *current = q->head;
    q->head = current->next;
    *data = current->data;
    free(current);
    return 0;
  }
}

void Queue_print(queue *q) {
  node *current = q->head;
  if (current == NULL) {
    printf("Empty queue.\n");
  }  
  else { 
    printf("<-- ");
    while (current) {
      if(current) { 
        printf("%4d    ", current->data);
      }
      current = current->next;
    } 
    printf("<-- \n");
  }  
}

void Queue_clear(queue *q) {
  int dummy_data;
  while(!Queue_isEmpty(q)) {
    if(!Queue_dequeue(q, &dummy_data)) {
      break;
    }
  }
  q->head = NULL;
  q->tail = NULL;
}

El resultado de la salida del código anterior, se muestra a continuación:

La cola esta vacia
Tamaño Q: 0
Tamaño Q: 4
Primer elemento de Q: 19
Ultimo elemento de Q: 7
<--   19      45      13       7    <--
Dato sacado: 19 (elementos disponibles: 3)
<--   45      13       7    <--
Dato sacado: 45 (elementos disponibles: 2)
<--   13       7    <--
Dato sacado: 13 (elementos disponibles: 1)
<--    7    <--
Dato sacado: 7 (elementos disponibles: 0)
Empty queue.
ERROR: Empty Queue
<--    1       2       3    <--
Vaciando la cola de 3 elementos
Numero de elementos en la cola: 0
Empty queue.

3. Enlaces#

https://github.com/ErdemOzgen/Cpp-Learning-Archive/blob/master/README.md
https://ranger.uta.edu/~alex/courses/3318/
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
http://cslibrary.stanford.edu/
https://web.stanford.edu/dept/cs_edu/resources/textbook/
https://web.stanford.edu/class/cs106x/handouts.html
https://web.stanford.edu/class/cs107/
https://web.stanford.edu/class/archive/cs/cs107/cs107.1248/calendar
https://web.stanford.edu/class/cs106x/res/reader/CS106BX-Reader.pdf
http://cslibrary.stanford.edu/
https://www.cs.swarthmore.edu/~newhall/cs45/s14/#schedule
https://www.cs.swarthmore.edu/~newhall/unixlinks.html#lang
https://publications.gbdirect.co.uk/c_book/
https://www.cs.swarthmore.edu/~newhall/unixlinks.html#Clang
https://www.cs.swarthmore.edu/~newhall/unixhelp/os_stats.php
https://www.cs.swarthmore.edu/~newhall/cs35/
https://www.cs.swarthmore.edu/~newhall/unixhelp/C_linkedlists.pdf
https://www.cs.princeton.edu/courses/archive/spring20/cos217/
https://www.cs.princeton.edu/courses/archive/spring20/cos217/precepts/09voidptrs/symtablelist.pdf
https://www.cs.princeton.edu/courses/archive/spring20/cos217/lectures/01_Intro.pdf
https://august.princeton.edu/
https://www.cs.princeton.edu/courses/archive/fall07/cos217/lectures/
https://ocw.mit.edu/courses/6-s096-introduction-to-c-and-c-january-iap-2013/
https://ocw.mit.edu/courses/6-s096-introduction-to-c-and-c-january-iap-2013/pages/lectures-and-assignments/data-structures-debugging/
https://ocw.mit.edu/courses/6-s096-introduction-to-c-and-c-january-iap-2013/pages/lectures-and-assignments/data-structures-debugging/
https://ocw.mit.edu/courses/6-033-computer-system-engineering-spring-2018/
https://ocw.mit.edu/courses/6-828-operating-system-engineering-fall-2012/
https://ocw.mit.edu/courses/6-087-practical-programming-in-c-january-iap-2010/
https://ocw.mit.edu/courses/6-087-practical-programming-in-c-january-iap-2010/pages/lecture-notes/
https://ocw.mit.edu/courses/1-00-introduction-to-computers-and-engineering-problem-solving-spring-2012/
https://ocw.mit.edu/courses/6-0002-introduction-to-computational-thinking-and-data-science-fall-2016/
https://ocw.mit.edu/courses/6-100l-introduction-to-cs-and-programming-using-python-fall-2022/
https://ocw.mit.edu/collections/introductory-programming/
https://cs61c.org/su24/
https://www.cs.princeton.edu/courses/archive/spr24/cos126/schedule/
https://web2.qatar.cmu.edu/~mhhammou/15122-s23/
https://web2.qatar.cmu.edu/~mhhammou/15122-s23/schedule.html
https://bytesoftheday.wordpress.com/2014/07/04/q14/
https://www.cs.princeton.edu/courses/archive/spring20/cos217/
https://embeddedwala.com/Blogs/embedded-c/memory-layout-of-c-program
https://www.cs.mtsu.edu/~cs2170/C++labs/lab18/OSmemlayout.pdf
https://d1b10bmlvqabco.cloudfront.net/attach/j6fe5friemd22w/hzd1madqsie3ts/j7kw6i4tmqf8/61C_Note_1_Memory.pdf
https://ocw.mit.edu/courses/6-s096-introduction-to-c-and-c-january-iap-2013/bba9056d5290198d563edc47dfcff0e9_MIT6_S096_IAP13_lec3.pdf
https://cs61c.org/su24/
http://wla.berkeley.edu/~cs61c/fa17/
https://www.cs.princeton.edu/courses/archive/fall07/cos217/index.html
https://web2.qatar.cmu.edu/~mhhammou/15122-s23/lectures/21-cmem/writeup/pdf/main.pdf
https://cs.gmu.edu/~zduric/cs262/Slides/teoX.pdf
https://d1b10bmlvqabco.cloudfront.net/attach/j6fe5friemd22w/hzd1madqsie3ts/j7kw6i4tmqf8/61C_Note_1_Memory.pdf
https://www.cs.princeton.edu/courses/archive/fall07/cos217/
https://www.cs.mtsu.edu/~cs2170/C++labs/lab18/OSmemlayout.pdf
https://web2.qatar.cmu.edu/~mhhammou/15122-s23/lectures/21-cmem/writeup/pdf/main.pdf
https://www.cs.princeton.edu/courses/archive/spr24/cos126/schedule/
https://github.com/vishwa27yvs/Intro-to-Computer-Science-COS-126
https://www.berthon.eu/wiki/foss:wikishelf:linux:memory
http://resources.infosecinstitute.com/system-address-map-initialization-in-x86x64-architecture-part-1-pci-based-systems/#gref
https://fypandroid.wordpress.com/2011/01/17/anatomy-of-a-program-in-memory/
https://www.securitysift.com/windows-exploit-development-part-1-basics/
https://www.ibm.com/developerworks/library/j-nativememory-linux/
https://gabrieletolomei.wordpress.com/miscellanea/operating-systems/in-memory-layout/
http://www.cs.utexas.edu/users/fussell/cs310h/lectures/Lecture_17-310h.pdf
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-087-practical-programming-in-c-january-iap-2010/lecture-notes/
https://stackoverflow.com/questions/2128728/allocate-matrix-in-c
https://www.geeksforgeeks.org/dynamically-allocate-2d-array-c/
https://www.programiz.com/c-programming/c-dynamic-memory-allocation
https://www.cs.swarthmore.edu/~newhall/unixhelp/C_arrays.html
https://engineering.purdue.edu/ece264/

Introducción al lenguaje C

Colas (Queues)

Contents

Colas (Queues)#

1. Introduccion#

2. Sobre las colas (queues)#

2. Implementación de una cola#

2.1. Implementación a partir array#

2.1.1. Definición de la cola#

2.1.2. Funciones de la cola#

2.1.3. Ejemplos#

2.2. Implementación como lista enlazada#

2.2.1 Estructuras asociadas la cola#

2.2.1.1. Nodo (`node`)#

2.2.1.2. Cola#

2.2.2 Funciones#

2.2.3. Ejemplos#

3. Enlaces#

Introducción al lenguaje C

Colas (Queues)

Contents

Colas (Queues)#

1. Introduccion#

2. Sobre las colas (queues)#

2. Implementación de una cola#

2.1. Implementación a partir array#

2.1.1. Definición de la cola#

2.1.2. Funciones de la cola#

2.1.3. Ejemplos#

2.2. Implementación como lista enlazada#

2.2.1 Estructuras asociadas la cola#

2.2.1.1. Nodo (node)#

2.2.1.2. Cola#

2.2.2 Funciones#

2.2.3. Ejemplos#

3. Enlaces#

2.2.1.1. Nodo (`node`)#