Queue implementation through linked list

shabbir's Avatar author of Queue implementation through linked list
This is an article on Queue implementation through linked list in C.
Queue implementation using linked list
Code: C
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
/*****  Structure template  *****/
struct list{
                char data;
                struct list *next;
};
/*****  Redefining struct list as node  *****/
typedef struct list node;
void qinsert(node**,node**); /** Inserting character function in queue **/
void qdelete(node**,node**); /** Deleting character function in queue **/
void disp(node*);            /** Output displaying function **/

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
|*"front" and "rear" pointer needed to be changed when inserting and *|
|*  deleting so addresses of them is passed in qinsert and qdelete   *|
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */


void main()
{
    int opt;        /* Option inputing variable */   
    char ch;        /* choice inputing variable */   
    node *front;    /* front pointer in queue*/   
    node *rear;     /* rear pointer in queue */
    rear=front=NULL;
    do
    {
        printf("\nEnter your option to perform in a queue\n");
        printf("\n1. Insert\n");
        printf("\n2. delete\n");
        printf("\n3. Display the list\n");
        scanf("%d",&opt);
        switch(opt)
        {
        case 1:
            qinsert(&front,&rear);
            break;
        case 2:
            qdelete(&front,&rear);
            break;
        case 3:
            disp(front);
            break;
        }
        printf("\nDo you wish to continue[y/n]\n");
        ch=(char)getche();
    }while(ch=='Y' || ch=='y');
    printf("\nDone by \"SHABBIR\"\n");
    printf("\nPress any key to exit\n");
    getch();
}

void qinsert(node **front,node **rear)
{
    node *newnode;      /* New node to be inserted */
    newnode=(node*)malloc(sizeof(node));
    newnode->next=NULL;
    printf("\nEnter the character to push\n");
    fflush(stdin);
    scanf("%c",&(newnode->data));
    if(*front==NULL && *rear==NULL)
    {
        *front=newnode;
        *rear=newnode;
    }
    else
    {
    /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
    |*  "rear" points to last node whose next field must be pointed to *|
    |*  newnode and then rear points to the latest node i.e. new node  *|
    \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

        (*rear)->next=newnode;
        *rear=newnode;
    }
}

void qdelete(node **front,node **rear)
{
    node *delnode;      /* Node to be deleted */
    if((*front)==NULL && (*rear)==NULL)
        printf("\nQueue is empty to delete any element\n");
    else
    {
        delnode=*front;
        (*front)=(*front)->next;
        free(delnode);
    }
}
void disp(node *f)
{
    while(f!=NULL)
    {
        printf(" %c ",f->data);
        f=f->next;
    }
}
habibussamahms like this
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
You can also refer to Priority Queue implementation using Linked List.
like this
aisha.ansari84's Avatar, Join Date: Feb 2008
Contributor
good it
aisha.ansari84's Avatar, Join Date: Feb 2008
Contributor
i suppose arrays are better than linked lists
rahul.mca2001's Avatar, Join Date: Feb 2008
Ambitious contributor
linked list implementation is compile time or run time
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Quote:
Originally Posted by rahul.mca2001
linked list implementation is compile time or run time
Run Time
ahamed101's Avatar, Join Date: Sep 2008
Go4Expert Member
Hi Shabbir,
Thanks a lot for the program...

I think there is small change required in the qdelete function...

Code:
void qdelete(node **front,node **rear)
{
    node *delnode;      /* Node to be deleted */
    if((*front)==NULL && (*rear)==NULL)
        printf("\nQueue is empty to delete any element\n");
    else
    {
        delnode=*front;
        (*front)=(*front)->next;
        (*front)->rear = NULL;
        free(delnode);
    }
}
Regards,
Ahamed.
back from retirement's Avatar, Join Date: Nov 2008
Contributor
Hello....I have used an initialisation in it as well....alike Shabbir used in Doubly or Circular linkd list...

Here's my code...
Code:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

typedef struct node
{
	int data;
	struct node *next;
};

void init(node *front, node *rear, int value)
{
	node *newnode;
	newnode=(node *)malloc(sizeof(node));
	newnode->data=value;
	front->next=newnode;
	rear->next=newnode;
	newnode->next=NULL;
}

void ins(node *rear, int value)
{
	node *newnode;
	newnode=(node *)malloc(sizeof(node));
	newnode->data=value;
	newnode->next=NULL;
	(rear->next)->next=newnode;
   rear->next=newnode;
}

void del(node *front, node *rear)
{
	node *del;
	if(front->next==NULL && rear->next==NULL)
		printf("\nList is empty....nothing to delete\n");
	else if(front->next==rear->next && (rear->next)->next==NULL)
		printf("\nYou cannot delete the last node\n");
	else
	{
		del=front->next;
		front->next=(front->next)->next;
		free(del);
		}
}

void display(node *front, node *rear)
{
	node *move=front->next;
	if(front->next==NULL && rear->next==NULL)
		printf("\nList is empty....nothing to display\n");
	else
	{
		while(move->next!=NULL)
		{
			printf("\n%5d\n", move->data);
			move=move->next;
		}
		printf("\n%5d\n", move->data);
	}
}

void main()
{
	node *front, *rear;
	int i,n;
	static int k=0;
	char ch;
	front=(node *)malloc(sizeof(node));
	rear=(node *)malloc(sizeof(node));
	front->next=NULL;
	rear->next=NULL;
	printf("\nWelcome\n");
	do
	{
		again:
		printf("\nEnter 1 for INITIALISE, 2 for INSERT, 3 for DELETE, 4 for DISPLAY\t");
		scanf("%d", &i);
		if(k==0 && i!=1)
		{
			printf("\nYou must initialise first\n");
			goto again;
		}
		else if(k==0 && i==1)
			k=1;
		else if(k==1 && i==1)
		{
			printf("\nInitialisation can occur only once....now you can push values\n");
			goto again;
		}
		else
			goto done;

		done:
		switch(i)
		{
			case 1:
			{
				printf("\nEnter the value you want to initialise=");
				scanf("%d", &n);
				init(front,rear,n);
				break;
			}

			case 2:
			{
				printf("\nEnter the value you want to insert=");
				scanf("%d", &n);
				ins(rear,n);
				break;
			}

			case 3:
			{
				del(front,rear);
				break;
			}

			case 4:
			{
				display(front,rear);
				break;
			}

			default:
			{
				printf("\nERROR...please re-enter the code\n");
				break;
			}
		}
		printf("\nDo you wish to continue?[y/n]\t");
		ch=getche();
		printf("\n");
	}while(ch=='y'||ch=='Y');
	printf("\nThank you....press any key to exit\n");
	getch();
}
back from retirement's Avatar, Join Date: Nov 2008
Contributor
@ Ahmed....sorry, but the program is running without the line as well....in my pc...

Maybe we are using different type of compilers...
please do not take it otherwise...
skp819's Avatar
Contributor
excellent.