CodingBison

A queue is a popular data-structure where we can store elements using the first-in first-out (FIFO) rule. In its simplest form, a queue allows applications to add (enqueue) an element and remove (dequeue) an element. Due to its FIFO semantics, when we enqueue an element, the element sits at the tail of the queue and when we dequeue and element, the element is removed from the head of the queue.

Let us understand the enqueue and dequeue operations using a simple figure. The figure (provided below) starts with a queue that has certain elements. Next, we enqueue a new element (with value 880); this element goes at the tail of the queue. Following that, we dequeue an element; the element in this case is 280, which is at the head of the queue.

```                                     -------------------
head  -----> | 280 | 480 | 680 | <------ tail
-------------------
A Queue with 3 elements
|
|  Enqueue a new value (880)
V
-------------------------
head  -----> | 280 | 480 | 680 | 880 | <------ tail
-------------------------
|
|  Dequeue a value (we get 280)
V
-------------------
head  -----> | 480 | 680 | 880 | <------ tail
-------------------

Queue: Enqueue at the tail and Dequeue from the head
```

Implementation

We can implement a queue using either a linked list or an array. On this page, we discuss the implementation using a linked list. The advantage of using a linked list versus array is that the linked list can grow as much as we want. However, with an array, we would need to re-allocate the array, whenever we go beyond the currently allocated size. The cost comes in the form of linkedlist having to have an additional member that connects two links in the list.

Things To Remember
A queue works using the first-in-first-out (FIFO) rule. By contrast, a stack works using the last-in-first-out (LIFO) rule.

In terms of data-structures, the implementation (provided below) defines a data-structure for the queue element (queue_elem). The queue_elem pointer holds a next pointer that links it to the next element in the linked list. Next, it also holds a "int" data type which holds the information attached with the queue element. In terms of functions, the implementation supports three functions that allow us to enqueue, dequeue, and print elements in a queue: queue_enqueue(), queue_dequeue(), and queue_print().

The queue_enqueue() function mallocs a new queue element (queue_elem, to be precise) and then assigns the passed data to the data field of the element. Next, it adds the newly created element to the tail of the queue. The queue_dequeue() does the opposite. It returns the data from the head element, frees the head element, and then makes the head element point the next element. The queue_print() simply does a walk and prints all the elements.

Here is the C file that provides the implementation.

``` #include <stdio.h>
#include <stdlib.h>

/* Representation of a queue element */
typedef struct queue_elem_ {
struct queue_elem_ *next;
int                 data;
} queue_elem;

queue_elem *tail = NULL;

/* Adds to the tail */
void queue_enqueue (int data) {
queue_elem *elem = NULL;

/* Build the element that needs to be inserted */
elem = (queue_elem *) malloc(sizeof(queue_elem));
if (!elem) {
fprintf(stderr, "Malloc failed.\n");
return;
}
elem->data = data;
elem->next = NULL;

/* Move the tail to point to this element */
if (tail) {
tail->next = elem;
}
tail = elem;

/* If this elem is the first one, then make the head point to it */
}
printf("Enqueued: %d\n", data);
}

/* Removes from the head. */
void queue_dequeue () {

/* Queue is NULL or head points to NULL. Nothing to return */
printf("Dequeued: Queue is Empty\n");
return;
}

/* Move the head to the next element. Also, save it so to free it later. */

/* Update the tail if all elements are gone */
tail = NULL;
}

/* Free the previous head */
}

void queue_print () {
queue_elem *elem = NULL;

printf("Printing Queue: ");
for (elem = head; elem != NULL; elem = elem->next) {
printf("%d  ", elem->data);
}
printf("\n");
}

int main () {

/* Enqueue few values to the queue. */
queue_enqueue(280);
queue_enqueue(480);
queue_enqueue(680);
queue_print();

/* Dequeue one value and enqueue one. */
queue_dequeue();
queue_enqueue(880);
queue_print();

/* Dequeue all of them! */
queue_dequeue();
queue_dequeue();
queue_dequeue();
queue_print();
queue_dequeue();
return 0;
}
```

In the above implementation, the main() function basically enqueues and dequeues various elements to the queue. It also calls the queue_print() routine to dump the elements present in the queue. To run the above file ("queue.c"), we use "gcc" for compiling it. Here is the output.

``` user@codingbison \$ gcc queue.c -o queue
user@codingbison \$ ./queue
Enqueued: 280
Enqueued: 480
Enqueued: 680
Printing Queue: 280  480  680
Dequeued: 280
Enqueued: 880
Printing Queue: 480  680  880
Dequeued: 480
Dequeued: 680
Dequeued: 880
Printing Queue:
Dequeued: Queue is Empty
```