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
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.
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;
/* Global head/tail pointers */
queue_elem *head = NULL;
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 */
if (!head) {
head = elem;
}
printf("Enqueued: %d\n", data);
}
/* Removes from the head. */
void queue_dequeue () {
queue_elem *prev_head = NULL;
if (!head) {
/* Queue is NULL or head points to NULL. Nothing to return */
printf("Dequeued: Queue is Empty\n");
return;
}
printf("Dequeued: %d\n", head->data);
/* Move the head to the next element. Also, save it so to free it later. */
prev_head = head;
head = head->next;
/* Update the tail if all elements are gone */
if (!head) {
tail = NULL;
}
/* Free the previous head */
free(prev_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
The above implementation covers the basic bare-bone of a queue data structure. However, if we were to make it more generic, we would need to make a few changes. First and foremost, the only type that the above implementation allows us to store is the integer type; a generic implementation would need to do more than that -- it should allow us to store any type of data. Second, the above code sits in one single file. A generic library implementation would be in the form of a header file and an implementation file. Application files that need to use a queue can simply call the APIs defined in the header file.
If you have read the above implementation and would like to try an implementation that is more generic, you can visit our page: Advanced Implementation of a Queue. However, if you are trying to learn the basics of a queue, please feel free to ignore the advanced implementation for now.