DS Menu

Queues using linkedlist

Queue Implementation Using an Linked List

Initialize the Queue

The Queue struct initializes with a pointers, head set to null.

Pseudocode

Struct node
    int data
    struct node next

struct node head := NULL

Enqueue Operation

Adds an element at the end of the queue list. If the queue list is empty, head is set to the new node. Otherwise, the new node is added at the end of the queue list.

Pseudocode

// Add an item to the rear of the queue
function enqueue(data):
    newNode = new Node(data)
    temp := head;
    if head = NULL
        head := newNode
    else:
        while temp.next != NULL
            temp := temp.next
        temp.next = newNode

Dequeue Operation

Removes and returns the element from the front of the queue list. It checks if the queue is empty to avoid underflow. If the queue becomes empty after the operation, the head pointer is also set to null.

Pseudocode

// Remove an item from the front of the queue
function dequeue():
    if head = NULL
        display "Queue Underflow"
        return null
    else:
        dequeuedNode := head
        head := head.next
        return dequeuedNode.

C Program to implement queue using Linked List

Program

#include<stdio.h>
#include<stdlib.h>

struct node{
    int data;
    struct node*next;
}*head=NULL;

struct node *create(int value)
{
    struct node *temp;
    temp=(struct node*)malloc(sizeof(struct node));
    temp->data=value;
    temp->next=NULL;
    return temp;
}

void insert(int value)
{
    struct node *newnode, *temp;
    newnode=create(value);
    if(head==NULL)
    {
        head=newnode;
    }
    else
    {
        temp=head;
        while(temp->next!=NULL)
        {
            temp=temp->next;
        }
        temp->next=newnode;
    }
}

void deleteq()
{
    struct node *temp;
    if(head==NULL)
    {
        printf("deletion is not possible");
    }
    else
    {
        temp=head;
        head=head->next;
        free(temp);
    }
}

void display()
{
    struct node *temp;
    if(head==NULL)
    {
        printf("list is empty");
    }
    else
    {
        temp=head;
        while(temp->next!=NULL)
        {
            printf("%d, ",temp->data);
            temp=temp->next;
        }
        printf("%d",temp->data);
    }
}

void main()
{
    int ch,pos,value;
    do
    {
        printf("\n1.insert\n2.delete end\n3.display\n4.exit\n");
        printf("enter your choice:");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1: printf("enter the value:");
                scanf("%d",&value);
                insert(value);
                break;
        case 2: deleteq();
                break;
        case 3: display();
                break;
        case 4:break;
        default: printf("\nyour choice is wrong!.. ");
        }
    }while(ch!=4);
}

Next Topic :Stack Applications