Search This Blog

Loading...

Dequeue represented using a Linked List

#include<conio.h>
#include<stdio.h>

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

typedef struct Q
{
    node  *R,*F;
}Q;

void initialise(Q *);
int empty(Q *);
int full(Q *);
void enqueueR(Q *,int);//insert at the rear end
void enqueueF(Q *,int);//insert at the front end
int dequeueF(Q *);//Delete the front element
int dequeueR(Q *);//Delete the rear element
void print(Q *);
void main()
{
    Q q;
    int x,i,op;
    initialise(&q);
    clrscr();
    do
       {
        printf("\n\n1)Insert(Rear)\n2)Insert(Front)");
        printf("\n3)Delete(Front)\n4)Delete(Rear)\n5)Print\n6)Quit");
        printf("\nEnter Your Choice:");
        scanf("%d",&op);
        switch(op)
           {
            case 1: printf("\n Enter a value:");
                scanf("%d",&x);
                enqueueR(&q,x);
                break;
            case 2: printf("\n Enter a value:");
                scanf("%d",&x);
                enqueueF(&q,x);
                break;
            case 3: if(!empty(&q))
                   {
                    x=dequeueF(&q);
                    printf("\Deleted Data=%d",x);
                   }
                else
                    printf("\nQueue is empty !!!!");
                break;
            case 4: if(!empty(&q))
                   {
                    x=dequeueR(&q);
                    printf("\Deleted Data=%d",x);
                   }
                else
                    printf("\nQueue is empty !!!!");
                break;
            case 5: print(&q);break;
           }
    }while(op!=6);
}

void initialise(Q *qp)
{
    qp->R=NULL;
    qp->F=NULL;
}
void enqueueR(Q *qp,int x)
{
    node *p;
    p=(node*)malloc(sizeof(node));
    p->data=x;
    p->next=NULL;
    if(empty(qp))
    {
        qp->R=p;
        qp->F=p;
    }
    else
    {
        qp->R->next=p;
        qp->R=p;
    }
}
void enqueueF(Q *qp,int x)
{
    node *p;
    p=(node*)malloc(sizeof(node));
    p->data=x;
    p->next=NULL;
    if(empty(qp))
    {
        qp->R=p;
        qp->F=p;
    }
    else
    {
        p->next=qp->F;
        qp->F=p;
    }
}


int dequeueF(Q *qp)
{
    int x;
    node *p;
    p=qp->F;
    x=p->data;
    if(qp->F==qp->R)  //deleting the last element
        initialise(qp);
    else
        qp->F=p->next;
    free(p);
    return(x);
}
int dequeueR(Q *qp)
{
    int x;
    node *p,*q;
    p=qp->R;
    x=p->data;
    if(qp->F==qp->R)  //deleting the last element
        initialise(qp);
    else
        {  //locate the predecessor of rear node
           q=qp->F;
           while(q->next != qp->R)
            q=q->next;
           q->next=NULL;
           qp->R=q;
        }
    free(p);
    return(x);
}

void print(Q *qp)
{
    int i;
    node *p;
    p=qp->F;
    printf("\n");
    while(p!=NULL)
    {
        printf("%d  ",p->data);
        p=p->next;
    }
}
int empty(Q *qp)
{
    if(qp->R==NULL)
        return 1;
    return 0;
}

3 comments:

  1. Q q;

    initialise(&q);
    how to do this in class....

    ReplyDelete
  2. thank you so much!! this is the best code i have found so far :D

    ReplyDelete
  3. These are technically incorrect since you violate the contract of the interface. This gives performance in linear time for dequeueRear. It should be O(1).

    ReplyDelete