Queue implementation through Linked List

Discussion in 'C' started by shabbir, Aug 27, 2006.

  1. Queue implementation using linked list
    Code:
    #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;
    	}
    }
    
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  3. aisha.ansari84

    aisha.ansari84 New Member

    Joined:
    Feb 13, 2008
    Messages:
    82
    Likes Received:
    1
    Trophy Points:
    0
  4. aisha.ansari84

    aisha.ansari84 New Member

    Joined:
    Feb 13, 2008
    Messages:
    82
    Likes Received:
    1
    Trophy Points:
    0
    i suppose arrays are better than linked lists
     
  5. rahul.mca2001

    rahul.mca2001 New Member

    Joined:
    Feb 13, 2008
    Messages:
    103
    Likes Received:
    0
    Trophy Points:
    0
    linked list implementation is compile time or run time
     
  6. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Run Time
     
  7. ahamed101

    ahamed101 New Member

    Joined:
    Sep 27, 2008
    Messages:
    10
    Likes Received:
    0
    Trophy Points:
    0
    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;
            [U][B](*front)->rear = NULL;[/B][/U]
            free(delnode);
        }
    }
    
    Regards,
    Ahamed.
     
  8. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    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();
    }
    
     
  9. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    @ 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...
     
  10. skp819

    skp819 New Member

    Joined:
    Dec 8, 2008
    Messages:
    89
    Likes Received:
    3
    Trophy Points:
    0
    excellent.
     
  11. Awais

    Awais New Member

    Joined:
    Dec 8, 2009
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    I want queue implementation using linked list with Classes
    By the way Nice work
     
  12. tehdoughnut

    tehdoughnut New Member

    Joined:
    Mar 14, 2012
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    This code has an error. If the list empties all of the way then rear doesn't point to null when it should. The delete function should be:

    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;
    [U][B]        if((*front) == NULL)
                (*rear) = NULL;[/B][/U]
            free(delnode);
        }
    }
    
    
    
    
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice