C Program to Implement a Queue using Linked List

  • Write a program in C to implement a queue data structure using linked list.

Queue is a linear data structure. Queue follows First In First Out (FIFO) methodology. The element entered first in queue will leave first. Unlike Stack, Queue can be operated from both end. Elements always enter from read and leaves from front of queue.
Following are the fundamental queue operations:
  • enqueue : Add an element at the rear of the queue.
  • dequeue : Removes an element from front of the queue.
  • isEmpty : Returns if queue is empty.
  • getFrontElement : Returns front element of queue without removing it from queue.

We have to implement a Queue data structure using singly linked list. Linked list implementation of queue data structure must support basic queue operations like enqueue, dequeue, getQueueSize and isEmpty.
Given a singly linked list whose node structure is as follows: 

struct node {
    int data;
    struct node *next;
}
Algorithm to implement a queue using linked list
  • We will maintain two node pointer "front" and "back", which always points to the head and tail node of linked list respectively. This will ensure that we will add node at rear of linked list and remove node from front of linked list.
  • We will start with an empty linked list, where both front and back pointer is set to NULL.
  • Enqueue Operation : We will dynamically allocate memory for a struct node variable(let's say temp). Then we will attach new node at the end of linked list by setting back->next = temp. Finally set back pointer to temp.(back = temp;)
  • Dequeue Operation : Remove head node(pointed by front pointer) of the linked list. Store the front pointer in a temp variable. Now, move front pointer to next node(front = front->next;). Deallocate memory of temp node using free.
  • getFrontElement Operation : Returns the value of head node of linked list without removing it.(return front->data;)
  • isEmpty Check : If both front and back pointers are NULL, then Queue is empty otherwise non-empty.

C program to Implement a Queue using Linked List

/*
 * C Program to Implement Queue Data Structure using Linked List
 */
#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
} *front, *back;

/* Create an empty queue */
void initialize() {
    front = back = NULL;
}

/* Returns queue size */
int getQueueSize() {
    struct node *temp = front;
    int count = 0;
    
    if(front == NULL && back == NULL)
        return 0;

    while(temp != back){
        count++;
        temp = temp->next;
    }
    if(temp == back)
        count++;
        
    return count;
}

/* Returns Frnt Element of the Queue */
int getFrontElement() {
    return front->data;
}

/* Returns the Rear Element of the Queue */
int getBackElement() {
    return back->data;
}

/*
Check's if Queue is empty or not 
*/
void isEmpty() {
    if (front == NULL && back == NULL)
        printf("Empty Queue\n");
    else
        printf("Queue is not Empty\n");
}
/*
Adding elements in Queue
*/
void enqueue(int num) {
    struct node *temp;
    temp = (struct node *)malloc(sizeof(struct node));
    temp->data = num;
    temp->next = NULL;
    
    if (back == NULL) {
        front = back = temp;
    } else {
        back->next = temp;
        back = temp;
    }
}

/*
Removes an element from front of the queue
*/
void dequeue() {
    struct node *temp;
    if (front == NULL) {
        printf("\nQueue is Empty \n");
        return;
    } else {
        temp = front;
        front = front->next;
        if(front == NULL){
            back = NULL;
        }
        printf("Removed Element : %d\n", temp->data);
        free(temp);
    }
}
 
/*
 Print's Queue
*/
void printQueue() {
    struct node *temp = front;
 
    if ((front == NULL) && (back == NULL)) {
        printf("Queue is Empty\n");
        return;
    }

    while (temp != NULL) {
        printf("%d", temp->data);
        temp = temp->next;
        if(temp != NULL)
            printf("-->");
    }
}

int main() {
    /* Initializing Queue */
    initialize();
    /* Adding elements in Queue */
    enqueue(1);
    enqueue(3);
    enqueue(7);
    enqueue(5);
    enqueue(10);
    /* Printing Queue */
    printQueue();
    /* Printing size of Queue */
    printf("\nSize of Queue : %d\n", getQueueSize());
    /* Printing front and rear element of Queue */
    printf("Front Element : %d\n", getFrontElement());
    printf("Rear Element : %d\n", getBackElement());
    /* Removing Elementd from Queue */
    dequeue();
    dequeue();
    dequeue();
    dequeue();    
    dequeue();
    dequeue();
    
    return 0;
}
Output
1-->3-->7-->5-->10
Size of Queue : 5
Front Element : 1
Rear Element : 10
Removed Element : 1
Removed Element : 3
Removed Element : 7
Removed Element : 5
Removed Element : 10

Queue is Empty
Posted by
Labels: