One of the basic data-structures is that of a queue. A queue supports a structure where we can store a set of elements using the first-in first-out (FIFO) approach. In its simplest form, a queue allows applications to add (enqueue) an element to it and remove (dequeue) and element from it. 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. Please note that this behavior is different than that of a stack -- a stack works using the last-in first-out (LIFO) basis.
Let us understand the enqueue and dequeue for a queue 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 can be done using both a linked list and 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.
We provide an implementation that supports functions (APIs) that allow us to enqueue/dequeue elements in a queue. Our implementation in the form of three files: (a) a header file, (b) an implementation file, and (c) file that calls the APIs defined in the header file. This way, different applications can reuse the same implementation by merely including the header file and calling its APIs.
By the way, if you are looking for a simpler implementation to understand the basics of a queue data-structure, you are welcome to try our page that offers a simpler version of the implementation: Simple Implementation of a Queue.
The implementation supports APIs (public functions) for enqueuing and dequeuing elements in a queue. The dequeue function returns an error to indicate if the queue is empty. Next, it has an API that returns the number of the elements in the queue. Lastly, it has an API that applications can call to initialize the queue structure -- it is a must to call this init API before starting to use the structure.
queue_init(): Initializes the queue structure queue_enqueue(): Adds an element to the tail queue_dequeue(): Removes the head element. If queue is empty, then err to QUEUE_ERRNO_EMPTY queue_get_size(): Return the size of the Queue
With that, let us begin with the header file. The header file starts with a data-structure for the queue element (queue_elem) and the queue itself. The queue_elem pointer holds a next pointer that links it to the next element in the linked list. Next, it also holds a "void *" data type which holds the information attached with the queue element. Since it is a "void *" type, the application can store pretty much any type of data they want in the queue. The queue structure consists of two queue_elem pointers: head and tail. These two pointers point to the start and the end of the queue which is built using a linked list.
By the way, since the data stored is of "void *" type, the implementation does not know how to print them and hence, we do not provide an API for printing the queue. However, the application is free to define its own print routine and our example (on this page) does the same.
Next, the header file publishes the above four APIs. For each API, it also accepts a pointer to the queue structure. All operations are done on head/tail values belonging to this queue. Encapsulating these values, instead of keeping them global, means that different applications can define the queue structure in their scope and thus, reuse this implementation. Here is the header file (let us call it "queue.h").
#ifndef __QUEUE_H__
#define __QUEUE_H__
#define QUEUE_ERRNO_SUCCESS 1
#define QUEUE_ERRNO_EMPTY -1
typedef struct queue_elem_ {
struct queue_elem_ *next;
void *data; /* Holds the data */
} queue_elem;
/* Representation of the Queue */
typedef struct queue_ {
struct queue_elem_ *head;
struct queue_elem_ *tail;
int size;
} queue;
/* Initializes the Queue. */
void queue_init(queue *sq);
/* Adds to the tail. */
void queue_enqueue(queue *sq, void *data);
/* Removes from the head. If err is QUEUE_ERRNO_EMPTY, then queue is empty. */
void *queue_dequeue(queue *sq, int *err);
/* Returns the size of the Queue. */
int queue_get_size(const queue *sq);
#endif /* __QUEUE_H__ */
With that, let us provide the actual implementation of the above APIs. The implementation (provided below) shows us the gut of the earlier published APIs. The queue_enqueue() function mallocs a new queue element and then assigns the pass data to the data field of the element. Next, it increases the queue size. On the other hand, queue_dequeue() retrieves the head of the queue and then decreases the queue size. More importantly, if the queue size is empty, then it sets the passed error number variable to indicate the same. Applications should check this error number before accepting the returned value.
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include "queue.h"
/* Initializes the Queue. */
void queue_init (queue *sq) {
bzero((void *)sq, sizeof(queue));
return;
}
/* Return the size of the Queue. */
int queue_get_size (const queue *sq) {
if (!sq) {
return -1;
} else {
return (sq->size);
}
}
/* Adds to the tail. */
void queue_enqueue (queue *sq, void *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 (sq->tail) {
sq->tail->next = elem;
}
sq->tail = elem;
/* If this elem is the first one, then make the head point to it */
if (!sq->head) {
sq->head = elem;
}
/* Increase the size. */
sq->size += 1;
}
/* Removes from the head. */
void *queue_dequeue (queue *sq, int *err) {
queue_elem *hd = NULL;
void *retData;
if (!sq || !sq->head) {
/* Queue is NULL or head points to NULL. Nothing to return */
*err = QUEUE_ERRNO_EMPTY;
return NULL;
}
/* This is the head and we need to return data associated with that */
hd = sq->head;
retData = hd->data;
/* Move the head to the next element */
sq->head = sq->head->next;
/* Update the tail if all elements are gone */
if (!sq->head) {
sq->tail = NULL;
}
/* Free the previous head */
free(hd);
/* Decrease the size. */
sq->size -= 1;
*err = QUEUE_ERRNO_SUCCESS;
return retData;
}
Please note that we do not provide an API to free the queue because when we free the queue element, the application might have added malloced data to each element. Upon freeing the queue element without application's input, we would lose the handle to the previously malloced data leading to memory leak. However, an application is free to implement its own free function that can dequeue each element of the queue and call free() for the application data. When we do a dequeue, the queue implementation already does a free() of the queue element, so that way, both memory allocations would be taken care of.
With the above header file and the C file that implements those APIs, we are all set to write an application that uses them. Accordingly, we write an application that does exactly the same and provide it below; let us call this file "main_queue.c" since it houses the main() function.
#include <stdio.h>
#include "queue.h"
void print_queue_for_me (queue *sq) {
queue_elem *elem = NULL;
printf("Printing Queue (size: %d): ", queue_get_size(sq));
for (elem = sq->head; elem != NULL; elem = elem->next) {
printf("%d ", *(int *)(elem->data));
}
printf("\n");
}
int main(int argc, char *argv[]) {
queue q;
int *retVal;
int error_no;
int x1 = 280, x2 = 480, x3 = 680, x4 = 880;
queue_init(&q);
/* Enqueue few values to the queue. */
queue_enqueue(&q, (void *)&x1);
printf("Enqueued: %d\n", x1);
queue_enqueue(&q, (void *)&x2);
printf("Enqueued: %d\n", x2);
queue_enqueue(&q, (void *)&x3);
printf("Enqueued: %d\n", x3);
print_queue_for_me(&q);
/* Dequeue one and enqueue one. */
retVal = (int *)queue_dequeue(&q, &error_no);
if (error_no != QUEUE_ERRNO_EMPTY)
printf("Dequeued: %d\n", *retVal);
queue_enqueue(&q, (void *)&x4);
print_queue_for_me(&q);
/* Do some more dequeues! */
retVal = (int *)queue_dequeue(&q, &error_no);
if (error_no != QUEUE_ERRNO_EMPTY)
printf("Dequeued: %d\n", *retVal);
else
printf("Dequeued: Queue is Empty\n");
retVal = (int *)queue_dequeue(&q, &error_no);
if (error_no != QUEUE_ERRNO_EMPTY)
printf("Dequeued: %d\n", *retVal);
else
printf("Dequeued: Queue is Empty\n");
print_queue_for_me(&q);
return 0;
}
In the above implementation, the main() function defines a queue (q), uses queue_init() to initialize it, and then enqueues and dequeues various elements. When queue_dequeue(), the application should check the error number. If the error number is QUEUE_ERRNO_SUCCESS, then the dequeue was valid but if the error number is QUEUE_ERRNO_EMPTY, then the queue is empty. The file also contains a function (print_queue_for_me()) that prints various elements of the queue. To run the above file, we use "gcc" for compiling the above file along with the "queue.c" as well. Here is the output.
user@codingbison $ gcc main_queue.c queue.c -o queue user@codingbison $ ./queue Enqueued: 280 Enqueued: 480 Enqueued: 680 Printing Queue (size: 3): 280 480 680 Dequeued: 280 Printing Queue (size: 3): 480 680 880 Dequeued: 480 Dequeued: 680 Printing Queue (size: 1): 880