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.


All times are GMT +5.5. The time now is 16:55.