{"id":528,"date":"2024-10-19T13:52:29","date_gmt":"2024-10-19T08:22:29","guid":{"rendered":"https:\/\/codexplained.in\/?p=528"},"modified":"2025-11-24T15:33:34","modified_gmt":"2025-11-24T10:03:34","slug":"implement-queue-using-linked-list","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=528","title":{"rendered":"Implement Queue using Linked List"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Structure to represent a node in the queue\nstruct Node {\n    int data;\n    struct Node* next;\n};\n\n\/\/ Structure to represent the queue with pointers to the front and rear\nstruct Queue {\n    struct Node *front, *rear;\n};\n\n\/\/ Function to create a new node with the given data\nstruct Node* newNode(int data) {\n    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));\n    temp->data = data;\n    temp->next = NULL;\n    return temp;\n}\n\n\/\/ Function to create an empty queue\nstruct Queue* createQueue() {\n    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));\n    q->front = q->rear = NULL;\n    return q;\n}\n\n\/\/ Function to add an element to the queue\nvoid enqueue(struct Queue* q, int data) {\n    \/\/ Create a new node\n    struct Node* temp = newNode(data);\n    \n    \/\/ If the queue is empty, the new node will be the front and rear\n    if (q->rear == NULL) {\n        q->front = q->rear = temp;\n        printf("Enqueued %d to the queue.\\n", data);\n        return;\n    }\n\n    \/\/ Attach the new node at the end of the queue and change the rear\n    q->rear->next = temp;\n    q->rear = temp;\n    printf("Enqueued %d to the queue.\\n", data);\n}\n\n\/\/ Function to remove an element from the queue\nvoid dequeue(struct Queue* q) {\n    \/\/ If the queue is empty, there is nothing to dequeue\n    if (q->front == NULL) {\n        printf("Queue is empty, nothing to dequeue.\\n");\n        return;\n    }\n\n    \/\/ Store the previous front and move the front one node ahead\n    struct Node* temp = q->front;\n    q->front = q->front->next;\n\n    \/\/ If the front becomes NULL, then the queue is empty, so set rear to NULL\n    if (q->front == NULL) {\n        q->rear = NULL;\n    }\n\n    printf("Dequeued %d from the queue.\\n", temp->data);\n    free(temp);\n}\n\n\/\/ Function to display the current elements of the queue\nvoid displayQueue(struct Queue* q) {\n    struct Node* temp = q->front;\n    if (temp == NULL) {\n        printf("Queue is empty.\\n");\n        return;\n    }\n\n    printf("Queue elements: ");\n    while (temp != NULL) {\n        printf("%d ", temp->data);\n        temp = temp->next;\n    }\n    printf("\\n");\n}\n\n\/\/ Main function to demonstrate queue operations\nint main() {\n    struct Queue* q = createQueue();\n\n    enqueue(q, 10);\n    enqueue(q, 20);\n    enqueue(q, 30);\n\n    displayQueue(q);\n\n    dequeue(q);\n    displayQueue(q);\n\n    dequeue(q);\n    dequeue(q);\n    dequeue(q);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation:<\/h3>\n\n\n\n
    \n
  1. Data Structure Design<\/strong>:\n
      \n
    • The Node<\/code> structure represents a node in the linked list, containing data<\/code> (to store the integer value) and next<\/code> (a pointer to the next node).<\/li>\n\n\n\n
    • The Queue<\/code> structure has two pointers: front<\/code> (points to the front of the queue) and rear<\/code> (points to the end of the queue).<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • Node Creation<\/strong>:\n
        \n
      • newNode(int data)<\/code>: This function creates a new node using malloc<\/code> and initializes it with the provided data<\/code>. It returns a pointer to the newly created node.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Queue Initialization<\/strong>:\n
          \n
        • createQueue()<\/code>: This function initializes a new Queue<\/code> by allocating memory for it and setting both front<\/code> and rear<\/code> pointers to NULL<\/code>, indicating an empty queue.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Enqueue Operation<\/strong>:\n
            \n
          • enqueue(struct Queue* q, int data)<\/code>:\n
              \n
            • A new node is created.<\/li>\n\n\n\n
            • If the rear<\/code> is NULL<\/code>, it means the queue is empty, so both front<\/code> and rear<\/code> pointers are set to this new node.<\/li>\n\n\n\n
            • Otherwise, the next<\/code> pointer of the current rear<\/code> is updated to the new node, and then rear<\/code> is updated to this new node.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Dequeue Operation<\/strong>:\n
                \n
              • dequeue(struct Queue* q)<\/code>:\n
                  \n
                • If the front<\/code> is NULL<\/code>, the queue is empty, so a message is printed.<\/li>\n\n\n\n
                • Otherwise, the front node is removed, and the front<\/code> pointer is updated to the next node in the queue.<\/li>\n\n\n\n
                • If the queue becomes empty after the removal (i.e., front<\/code> becomes NULL<\/code>), then rear<\/code> is also set to NULL<\/code>.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                • Display Function<\/strong>:\n
                    \n
                  • displayQueue(struct Queue* q)<\/code>: It traverses from front<\/code> to rear<\/code> and prints each node\u2019s data<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                  • Main Function<\/strong>:\n
                      \n
                    • Creates an empty queue.<\/li>\n\n\n\n
                    • Enqueues elements 10<\/code>, 20<\/code>, and 30<\/code>.<\/li>\n\n\n\n
                    • <\/li>\n\n\n\n
                    • Displays the queue.<\/li>\n\n\n\n
                    • Dequeues elements one by one and displays the queue after each operation.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                      Enqueued 10 to the queue.\nEnqueued 20 to the queue.\nEnqueued 30 to the queue.\nQueue elements: 10 20 30 \nDequeued 10 from the queue.\nQueue elements: 20 30 \nDequeued 20 from the queue.\nDequeued 30 from the queue.\nQueue is empty, nothing to dequeue.\n<\/code><\/pre>\n\n\n\n
                      Explanation of the Output:<\/h3>\n\n\n\n
                        \n
                      1. The elements 10<\/code>, 20<\/code>, and 30<\/code> are added to the queue. After enqueueing, the queue looks like 10 -> 20 -> 30<\/code>.<\/li>\n\n\n\n
                      2. The first dequeue<\/code> operation removes 10<\/code>, leaving 20 -> 30<\/code>.<\/li>\n\n\n\n
                      3. The next dequeue<\/code> removes 20<\/code>, leaving only 30<\/code>.<\/li>\n\n\n\n
                      4. After removing 30<\/code>, the queue becomes empty.<\/li>\n\n\n\n
                      5. Trying to dequeue from an empty queue gives a message indicating that there is nothing to remove.<\/li>\n<\/ol>\n\n\n\n
                        This implementation demonstrates how to use a linked list to efficiently manage a queue, ensuring that elements can be added or removed dynamically as needed.<\/p>\n