Implement Queue in C – Example

In the previous post, we implemented stacks, which is quite useful in real life. However, there is another data structure that we see everyday around us, which we call it a queue. In computer science, we can find its applications in simulations, print spooling, processes, and many more. Before starting to implement queue with an example in C, I recommend you to understand about self-referential structures. The post here will be useful to understand about self-referential structures and linked list.

Meanwhile, let’s see the code below:

#include <stdio.h>
#include <stdlib.h>
// Self-referential Structure
struct queueNode {
    char data;  // A character data in the queue
    struct queueNode *nextPtr;   // Pointer to next node
}; // end struct queuNode
typedef struct queueNode QueueNode; // alias for the struct
typedef QueueNode *QueueNodePtr;  // alias for QueueNode*
// Declarations
void enqueue(QueueNodePtr *headPtr, QueueNodePtr *tailPtr, char value);
char dequeue(QueueNodePtr *headPtr, QueueNodePtr *tailPtr);
int isEmpty(QueueNodePtr headPtr);
void showQueue(QueueNodePtr currentPtr); 
void showMenu(void);
int main() {
    // Initially, there are no nodes
    QueueNodePtr headPtr = NULL;
    QueueNodePtr tailPtr = NULL;
    // User's choice
    unsigned int ch;
    // User's entered character
    char item;
    
    // Display the menu
    showMenu();
    printf("? ");
    scanf("%u", &ch);
    
    // Loop unless user chooses 3
    while(ch != 3) {
        switch(ch) {
            case 1:
                printf("Enter a character: ");
                scanf("\n%c", &item);
                
                // insert the item in queue
                enqueue(&headPtr, &tailPtr, item);
                showQueue(headPtr);
                break;
            case 2:
                // if queue is not empty
                if(!isEmpty(headPtr)) {
                    item = dequeue(&headPtr, &tailPtr);
                    printf("%c is dequeued.\n", item);
                }// end if
                showQueue(headPtr);
                break;
            default:
                printf("Invalid choice.\n");
                showMenu();
                break;
        }
        showMenu();
        printf("? ");
        scanf("%u", &ch);
    }
    printf("Thank You!\n");
    return 0;
}
// Display Menu Function
void showMenu(void) {
    printf("Enter your choice:\n"
        "   1 to enqueue element into the queue.\n"
        "   2 to dequeue element from the queue.\n"
        "   3 to end" );
}
// insert a new value into the queue
void enqueue(QueueNodePtr *headPtr, QueueNodePtr *tailPtr, char value) {
    QueueNodePtr newPtr; // pointer to new node
    newPtr = malloc(sizeof(QueueNode)); // Create a node
    
    // if allocated
    if (newPtr != NULL) {
        newPtr->data = value;   // put value in the node
        newPtr->nextPtr = NULL;
        
        // if empty, insert node to head 
        if (isEmpty(*headPtr)) {
          *headPtr = newPtr;
        } 
        else {
          // assign nextPtr of tail node to the address of newPtr
          (*tailPtr)->nextPtr = newPtr;
        }
        *tailPtr = newPtr; // finally point the tail to the newPtr
    }
    else {
        printf("%c is not inserted. \n", value);
    }
}
// dequeue a queue element
char dequeue(QueueNodePtr *headPtr, QueueNodePtr *tailPtr) {
    char item; // value of the node
    QueueNodePtr tmpPtr; // temporary node pointer
    item = (*headPtr)->data;
    tmpPtr = *headPtr;
    *headPtr = (*headPtr)->nextPtr;
    // if queue is empty 
    if(*headPtr == NULL) {
      *tailPtr = NULL;
    }
    free(tmpPtr);
    return item;
    
}
// return 1 if the queue is empty, otherwise 0
int isEmpty(QueueNodePtr headPtr) {
    return headPtr == NULL;
}
// show the queue
void showQueue(QueueNodePtr currentPtr) {
    // if queue is empty
    if (isEmpty(currentPtr)) {
        printf("The queue is empty!\n");
    }
    else {
        printf("The queue is: \n");
        
        // while not the end of list
        while(currentPtr != NULL) {
            printf("%c ==> ", currentPtr->data);
            currentPtr = currentPtr->nextPtr;
        }
        printf("NULL\n");
    }
}

Firstly, we have to understand the operation of the queue. A queue has a head and a tail from which data are dequeued and enqueued respectively. So, let’s look at the enqueue operation:

QueueNodePtr newPtr; // pointer to new node
newPtr = malloc(sizeof(QueueNode)); // Create a node

The above lines of code allocate the required memory for a new node in the queue.

 // if allocated
    if (newPtr != NULL) {
        newPtr->data = value;   // put value in the node
        newPtr->nextPtr = NULL;
        
        // if empty, insert node to head 
        if (isEmpty(*headPtr)) {
          *headPtr = newPtr;
        } 
        else {
          // assign nextPtr of tail node to the address of newPtr
          (*tailPtr)->nextPtr = newPtr;
        }
        *tailPtr = newPtr; // finally point the tail to the newPtr
    }

In the above lines of code, we assigned the entered value to the data of the new node and the nextPtr to NULL. Let’s suppose, the queue is empty, then we have to point the head to the newPtr, otherwise, to the nextPtr of the tailPtr.

Similarly, let’s view the code for the dequeue operation.

// dequeue a queue element
char dequeue(QueueNodePtr *headPtr, QueueNodePtr *tailPtr) {
    char item; // value of the node
    QueueNodePtr tmpPtr; // temporary node pointer
    item = (*headPtr)->data;
    tmpPtr = *headPtr;
    *headPtr = (*headPtr)->nextPtr;
    // if queue is empty 
    if(*headPtr == NULL) {
      *tailPtr = NULL;
    }
    free(tmpPtr);
    return item;
}

Here, we just removed the data from the head and point to the nextPtr. Importantly, we have freed the memory.

In this way, we implement a queue in C as shown in the example above. Lastly, if you want to view the code, you can find it in the gist here.

If you like to learn about Rest API in Django, you can click here: https://nepcodex.com/2019/07/django-rest-api-from-scratch-part-1/

Also, if you want a boilerplate to start a project in React, Redux and Router, you can visit this link here: https://nepcodex.com/2019/07/a-guide-to-react-redux-router-latest-version/