Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   Queue implementation through linked list (http://www.go4expert.com/articles/queue-implementation-linked-list-t1279/)

shabbir 27Aug2006 18:08

Queue implementation through linked list
 
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;
    }
}


shabbir 15Oct2006 14:32

Re: Queue implementation through linked list
 
You can also refer to Priority Queue implementation using Linked List.

aisha.ansari84 5Mar2008 18:53

Re: Queue implementation through linked list
 
good it

aisha.ansari84 5Mar2008 18:53

Re: Queue implementation through linked list
 
i suppose arrays are better than linked lists

rahul.mca2001 6Mar2008 13:16

Re: Queue implementation through linked list
 
linked list implementation is compile time or run time

shabbir 6Mar2008 13:21

Re: Queue implementation through linked list
 
Quote:

Originally Posted by rahul.mca2001
linked list implementation is compile time or run time

Run Time

ahamed101 27Sep2008 23:20

Re: Queue implementation through linked list
 
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 30Nov2008 20:54

Re: Queue implementation through linked list
 
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 30Nov2008 21:02

Re: Queue implementation through linked list
 
@ 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 13Jan2009 14:44

Re: Queue implementation through linked list
 
excellent.

Awais 9Dec2009 14:29

Re: Queue implementation through linked list
 
I want queue implementation using linked list with Classes
By the way Nice work

tehdoughnut 14Mar2012 11:57

Re: Queue implementation through linked list
 
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;
        if((*front) == NULL)
            (*rear) = NULL;

        free(delnode);
    }
}



All times are GMT +5.5. The time now is 05:26.