Simple Queue | Data Structure

QUEUE:

Queue is data structure which follow the concept of FIFO & LIFO. In other words insertion can be made at one end called RARE and deletion can be done at other end called FRONT.

INSERTION IN QUEUE:

For inserting element in queue we check following conditions.

Necessary Conditions:

1. For empty queue

    If ( F == -1  and R == -1 )

    {

        printf ("Queue is empty");

    }

2. For single element

    If (F == R != -1)

    {

        printf ("Queue has a single element");

    }

3. For Queue is full

    If (R==Size-1)

    {

        printf ("Queue is full");

    }

    

Algorithm for Inserting Element in Queue:

X IS AN INSERTING ELEMENT

STEP 1: IF (R==SIZE-1)

STEP 2: "OVERFLOW"

STEP 3: ELSE

STEP 4: IF(R==-1)

STEP 5: R=0

STEP 6: F=0

STEP 7: QUEUE[R] =X

STEP 8: ELSE

STEP 9: R=R+1

STEP 10: QUEUE[R]=X

STEP 11: END IF

STEP 12: END IF

STEP 13: END

Program for Inserting Elements in Queue :

void insert_q(int x)

{

    if(R==size-1)

    {

        printf("Queue overflow");

    }

    else

    {

        if(R==-1)

        {

            R=0;

            F=0;

            queue[R]=x;

        }

        else

        {

            R++;

            queue[R]=x;

        }

    }

    //printf("Queue:%d",queue[R]);

}

Out Put :

Trace the Insert queue program by taking  an example:

Suppose we take size=4

x is inserting element

Suppose we want to insert 10,20,30,40 in queue

We know that insert takes place from Rare.

For insertion we check four condition known as IFFG here

I - Insertion

F- Full

F-First

G- General

So, when we insert the first element in a queue then we first check weather queue is full or not.

If it is not full than we come in else part and check     if( R == -1)

So here condition is true than we initialize R=0 & F=0

After that we insert the element in queue .i.e queue[R]=x

we get 

Now we want to insert next element i.e 20. Before that we check the condition of overflow which is false because queue contain only one element and R=0.

So control come in else part and check   if (R ==-1), condition is false because R=0 at that time than again control come in else part i.e R++ means increment R by one and R become 1 that means R points to 1st location and than queue[R]=x that means the next element is inserted the queue at 1st location. we get

Same procedure is applied till the whole queue is not filled and finally we get 

Now here (R==size-1) it is condition of overflow.

DELETION IN QUEUE:

For deleting element in queue we check following condition.

Algorithm for Deleting Element in Queue:

X IS AN DELETING ELEMENT

STEP 1: IF (F==-1)

STEP 2: WRITE QUEUE IS EMPTY

STEP 3: ELSE

STEP 4: IF(F==R)

STEP 5: F=-1

STEP 6: R=-1

STEP 7: X=QUEUE[F]

STEP 8: ELSE

STEP 9:X=QUEUE[F]

STEP 10: F=F+1

STEP 11: END IF

STEP 12: END IF

STEP 13 END

Procedure for Deleting Elements in Queue :

void delete_q()

{

    int x;

    if(F==-1)

    {

        printf("Queue underflow");

    }

    else

    {

        if(F==R)

        {

            x=queue[F];

            F=-1;

            R=-1;

        }

        else

        {

            x=queue[F];

            F++;

        }

    }

    //return(x);

}

Out Put:

Complete Program for Insertion & Deletion in Queue:

#include <stdio.h>

#include <conio.h>

#define size 50

int queue[size];

int R=-1,F=-1;

void insert_q(int x)

{

    if(R==size-1)

    {

        printf("Queue overflow");

    }

    else

    {

        if(R==-1)

        {

            R=0;

            F=0;

            queue[R]=x;

        }

        else

        {

            R++;

            queue[R]=x;

        }

    }

    //printf("Queue:%d",queue[R]);

}

void display()

{

    if(R==-1 && F==-1)

    {

        printf("Now Queue is empty!\n");

    }

   else

   {

    printf("Elements of queue are:");

    for(int i=F;i<=R;i++)

    {

        printf("|%d|",queue[i]);

    }

   }

}

int delete_q()

{

    int x=0;

    if(F==-1)

    {

        printf("Queue underflow\n");

    }

    else

    {

        if(F==R)

        {

            x=queue[F];

            F=-1;

            R=-1;

        }

        else

        {

            x=queue[F];

            F++;

        }

    } 

    return(x);

}

void main()

{

   int x,ch=1;

   do{

   if(ch==1)

   {

   printf("Enter Element of Queue:");

   scanf("%d",&x);

   insert_q(x);

   display();

   printf("\n");

   }

   printf("Do you want to insert element in queue:0-Exit, 1-Insert, 2-Delete:");   

   scanf("%d",&ch);

   if(ch==2)

   {

       int d=delete_q();

       printf("%d is deleted element\n",d);

       display();

       printf("\n");

   }

   }while(ch!=0);

   getch();

}

Note:

Drawback of Simple Queue:

If Simple Queue have a single element at its last position i.e (size-1) and if  we try to insert a new element than simple queue gives message " Queue is Full" , But almost queue is empty.

For overcoming this drawback we use Circular Queue.