Queue (Linked List Implementation)

In previous post we introduced Queue and discussed its implementation using array. In this post we are discussing linked list implementation.

As we know we need to maintain two pointers, front and rear.

front-> points to first item

rear-> points to last item.

And , enQueue(): adds new node after rear and moves rear to the next node.

deQueue(): removes the front node and moves front to the next node.

---

Implementation:

#include <stdio.h>
#include <stdlib.h>
 
struct node
{
    int info;
    struct node *ptr;
}*front,*rear,*temp,*front1;
 
int frontelement();
void enQueue(int data);
void deQueue();
void empty();
void display();
void create();
void queuesize();
 
int count = 0;
 
void main()
{
    int no, ch, e;
 
    printf("\n 1 - enQueue");
    printf("\n 2 - deQueue");
    printf("\n 3 - Front element");
    printf("\n 4 - Empty");
    printf("\n 5 - Exit");
    printf("\n 6 - Display");
    printf("\n 7 - Queue size");
    create();
    while (1)
    {
        printf("\n Enter choice : ");
        scanf("%d", &ch);
        switch (ch)
        {
        case 1:
            printf("Enter data : ");
            scanf("%d", &no);
            enQueue(no);
            break;
        case 2:
            deQueue();
            break;
        case 3:
            e = frontelement();
            if (e != 0)
                printf("Front element : %d", e);
            else
                printf("\n No front element in Queue as queue is empty");
            break;
        case 4:
            empty();
            break;
        case 5:
            exit(0);
        case 6:
            display();
            break;
        case 7:
            queuesize();
            break;
        default:
            printf("Wrong choice, Please enter correct choice  ");
            break;
        }
    }
}
 

void create()
{
    front = rear = NULL;
}
 

void queuesize()
{
    printf("\n Queue size : %d", count);
}
 

void enQueue(int data)
{
    if (rear == NULL)
    {
        rear = (struct node *)malloc(1*sizeof(struct node));
        rear->ptr = NULL;
        rear->info = data;
        front = rear;
    }
    else
    {
        temp=(struct node *)malloc(1*sizeof(struct node));
        rear->ptr = temp;
        temp->info = data;
        temp->ptr = NULL;
 
        rear = temp;
    }
    count++;
}
 

void display()
{
    front1 = front;
 
    if ((front1 == NULL) && (rear == NULL))
    {
        printf("Queue is empty");
        return;
    }
    while (front1 != rear)
    {
        printf("%d ", front1->info);
        front1 = front1->ptr;
    }
    if (front1 == rear)
        printf("%d", front1->info);
}
 

void deQueue()
{
    front1 = front;
 
    if (front1 == NULL)
    {
        printf("\n Error: Trying to display elements from empty queue");
        return;
    }
    else
        if (front1->ptr != NULL)
        {
            front1 = front1->ptr;
            printf("\n dequeued value : %d", front->info);
            free(front);
            front = front1;
        }
        else
        {
            printf("\n dequeued value : %d", front->info);
            free(front);
            front = NULL;
            rear = NULL;
        }
        count--;
}
 

int frontelement()
{
    if ((front != NULL) && (rear != NULL))
        return(front->info);
    else
        return 0;
}
 
void empty()
{
     if ((front == NULL) && (rear == NULL))
        printf("\n Queue empty");
    else
       printf("Queue not empty");
}

Output:

 1 - enQueue
 2 - deQueue
 3 - Front element
 4 - Empty
 5 - Exit
 6 - Display
 7 - Queue size
 Enter choice : 1
Enter data : 1

 Enter choice : 1
Enter data : 2

 Enter choice : 1
Enter data : 3

 Enter choice : 3
Front element : 1
 Enter choice : 6
1 2 3
 Enter choice : 7

 Queue size : 3
 Enter choice : 2

 dequeued value : 1
 Enter choice : 7

 Queue size : 2
 Enter choice : 4
Queue not empty
 Enter choice : 5

---

*Time complexity in both operations is O(1) as we only change few pointers in both operations. And also there is no loops in any of the operations.

---

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Follow Programmers Door for more.❤ Keep supporting.

#programming #blog #queue