Queue Using Linked Lists

Queue Using Linked Lists

Up until now, we have implemented queues using arrays. Today, we will explore another essential alternative: implementing queues using linked lists. This topic is a favorite among examiners, and understanding it is crucial for mastering both data structures.

Implementing queues with linked lists tests your proficiency in managing both queues and linked lists. If you are not familiar with either of these concepts, I recommend reviewing them before proceeding.

Recall that linked lists are chain-like structures where each node contains two parts: an integer variable to hold data and a node pointer to store the address of the next node. Below is an illustration of a linked list with three nodes. The last node points to NULL, and the first node is referred to as the head.

Moving to the basics of a queue, a queue represents a line or sequence of elements where the elements follow the FIFO discipline. The element inserting the first gets removed the first. We maintained two index variables, f, and r, to mark the beginning and the end of the queue. Below illustrated is a queue with three elements.

Since we are implementing this queue using a linked list, the index variables are no longer integers. These become the pointers to the front and the rear nodes. And the queue somewhat starts looking like this.

Enqueue in a Queue Linked List

Enqueuing in a queue implemented using a linked list is quite similar to inserting at the end of a regular linked list. Since we discussed this thoroughly in our previous lectures, you should find this process manageable. To insert a new node at the end, follow these steps:

1. Check for Available Space: Verify if there is enough space left in the heap for a new node.

2. Create and Initialize the New Node: If space is available, create a new node n, allocate memory for it in the heap, and fill its data with the new value provided by the user.

3. Update Pointers:

   • Set the next member of the new node n to NULL.
   • Point the next member of the r (rear) node to n.
   • Finally, make r equal to n to complete the insertion.

4. Handle the First Element Exception: When inserting the first element, both f (front) and r are initially NULL. Therefore, instead of just making r equal to n, you should also set f equal to n. This marks the beginning of the list.

Dequeue in a Queue Linked List

Dequeuing in a queue implemented using a linked list is similar to deleting the head node of a linked list. To delete the head node, follow these steps:

1. Check if the Queue is Empty: Use the isEmpty function to verify if the queue is empty.
2. Handle Empty Queue Case: If the queue is empty, return -1.
3. Create a Pointer for the Front Node: If the queue is not empty, create a new node pointer and set it equal to the front node (f). Also, store the data from the f node in an integer variable.
4. Update the Front Pointer: Set f equal to the next member of f to update the front of the queue.
5. Free the Old Node: Free the memory allocated for the old node pointer.
6. Return the Value: Finally, return the value that was stored from the f node.

Condition for isEmpty:

The only condition for the queue linked list to be empty is that the front node (f) is NULL, which indicates there is no beginning, and hence no elements in the queue.

Condition for isFull:

Queues implemented using linked lists typically never become full unless the heap memory is exhausted. Therefore, the only condition for the queue linked list to be full is when the new node becomes NULL upon creation.

We can easily complete the implementation of queues using linked lists, as we have extensively learned this topic in our previous documentation. We started with the basics of both queues and linked lists, allowing us to complete everything effectively. I encourage you to write the code for all these operations on your own, and feel free to share your progress with me. I would be delighted to see your advancement. We will discuss the C program in the next documentation.

Implementing Queue Using Linked List in C Language

We have learned to implement queues using linked lists, covering the enqueue and dequeue methods. In the queue linked list, we have examined the conditions for its full or empty state. Today, we will write these implementations in C. Before proceeding, ensure that you have reviewed the previous sections. If you missed any of it, I recommend going back, as those concepts are crucial for understanding today's material.

Let’s head to our editors. Below is the source code for your reference.

Understanding the Below Code Snippet:

1. Review Previous Concepts: I will first remind you of what we have already completed, boosting your confidence in handling linked lists and queues.
2. Recap on Linked Lists: We have previously studied linked lists, including traversal methods, insertion and deletion at different positions, and conditions for empty and full states.
3. Integrate Knowledge: Today, we will integrate our knowledge of both linked lists and queues to implement queues using linked lists.
4. Basic Implementation: We won't need to copy everything from the linked list lessons. Instead, we'll focus on the basics, which may serve as a revision of past documentation.
5. Create the Node Structure: Create a struct named Node with two members:
   • An integer variable data to store the data.
   • A pointer next of type struct Node to store the address of the next node.

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

Code Snippet 1: Creating the struct Node

6. Globally, create two struct Node pointers f and r, which would be used to mark the front and the rear ends. Declaring globally helps us use them in functions.

Creating Enqueue:

We learned in the last docs that to enqueue, we only use the rear pointer and add a new node at the end of the list. So, create a void function enqueue, and the value to enqueue is the only parameter since we have declared the pointers *f and r globally. In the function, create a new struct Node pointer n, and assign its memory in heap dynamically using malloc. Don’t forget to include the header file <stdlib.h>. Then check if the queue is full or, in other words, if there is no space in the heap. And that can be done by checking if the new pointer n equals NULL. If it does, then print the condition of the queue overflow and return. Else, insert the val in the data member of n, and make this node point to NULL. If you recall, we discussed a special case, where we were inserting in the list for the first time, when both f and r equals NULL. For this case, make both f and r equal to n, and for all the other cases, just make the r point the new node n. Ultimately make r equal to n since n becomes our new rear end. And that would be all.

void enqueue(int val){
    struct Node *n = (struct Node *) malloc(sizeof(struct Node));
    if(n==NULL){
        printf("Queue is Full");
    }
    else{
        n->data = val;
        n->next = NULL;
        if(f==NULL){
            f=r=n;
        }
        else{
            r->next = n;
            r=n;
        }
    }
}

Code Snippet 2: Creating the enqueue function

Exception case:

All the other cases:

Creating Dequeue:

As we discussed in the last lecture, Dequeue needs you to just delete the head node, which is the f node here. So, create an integer function dequeue. And we have no parameters to pass. Create a struct Node pointer ptr to hold the node we will delete. Make ptr equal to f. In the function, check if the queue is already not empty by checking if our front f is NULL or not. If it is NULL, then print the condition of the queue underflow and return. Else, make f equal to the next node to f. Store the data of ptr in an integer variable val. We can now free the pointer ptr. And return val, which is the data of the node we deleted.

int dequeue()
{
    int val = -1;
    struct Node *ptr = f;
    if(f==NULL){
        printf("Queue is Empty\n");
    }
    else{
        f = f->next;
        val = ptr->data;
        free(ptr);
    }
    return val;
}

Code Snippet 3: Creating the dequeue function

After every operation, we may need to have the traversal function, which you can copy from the previous lectures. Nothing in that needs to be modified.

Here is the whole source code:

#include <stdio.h>
#include <stdlib.h>
 
struct Node *f = NULL;
struct Node *r = NULL;
 
struct Node
{
    int data;
    struct Node *next;
};
 
void linkedListTraversal(struct Node *ptr)
{
    printf("Printing the elements of this linked list\n");
    while (ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}
 
void enqueue(int val)
{
    struct Node *n = (struct Node *) malloc(sizeof(struct Node));
    if(n==NULL){
        printf("Queue is Full");
    }
    else{
        n->data = val;
        n->next = NULL;
        if(f==NULL){
            f=r=n;
        }
        else{
            r->next = n;
            r=n;
        }
    }
}
 
int dequeue()
{
    int val = -1;
    struct Node *ptr = f;
    if(f==NULL){
        printf("Queue is Empty\n");
    }
    else{
        f = f->next;
        val = ptr->data;
        free(ptr);
    }
    return val;
}
 
int main()
{
    linkedListTraversal(f);
    printf("Dequeuing element %d\n", dequeue());
    enqueue(34);
    enqueue(4);
    enqueue(7);
    enqueue(17);
    printf("Dequeuing element %d\n", dequeue());
    printf("Dequeuing element %d\n", dequeue());
    printf("Dequeuing element %d\n", dequeue());
    printf("Dequeuing element %d\n", dequeue());
    linkedListTraversal(f);
    return 0;
}

Code Snippet 4: Implementing queues using linked lists

Now, let’s check if these methods work well. First, we’ll enqueue some elements in the queue, and to check if that actually happens, we’ll display the elements using traversal.

    enqueue(34);
    enqueue(4);
    enqueue(7);
    enqueue(17);
    linkedListTraversal(f);

Code Snippet 5: Using the enqueue function

And the output we received was:

Printing the elements of this linked list
Element: 34
Element: 4
Element: 7
Element: 17

Figure 1: Output of the above program

Let us now dequeue everything. And focus on the order of elements being dequeued.

    printf("Dequeuing element %d\n", dequeue());
    printf("Dequeuing element %d\n", dequeue());
    printf("Dequeuing element %d\n", dequeue());
    printf("Dequeuing element %d\n", dequeue());
    linkedListTraversal(f);

Code Snippet 6: Using the dequeue function

And the output this time was;

Dequeuing element 34
Dequeuing element 4
Dequeuing element 7
Dequeuing element 17
Printing the elements of this linked list

Figure 2: Output of the above program

As you can observe, there was no element left to display, and element 34 went out first since it entered the first. And here, we finish the implementation of queues using linked lists. The queue has been holding us all for quite some time now. Ah, that metaphor!