Circular Queue Using an Array

Circular Queue Using an Array

#include <stdio.h>

#include<stdlib.h>

#define MAX 3

char cq[MAX];

int front = -1,rear = -1;

void add(char);

void del();

void display();

int main()

{

            int ch;

            char item;

            while(1)

            {

                        printf("\n\n~~Main Menu~~");

                        printf("\n==> 1. Insertion and Overflow Demo");

                        printf("\n==> 2. Deletion and Underflow Demo");

                        printf("\n==> 3. Display");

                        printf("\n==> 4. Exit");

                        printf("\nEnter Your Choice: ");

                        scanf("%d", &ch);

                        switch(ch)

                        {

                                    case 1: printf("\n\nEnter the element to be inserted: ");

                                                scanf("%d", &item);

                                                add(item);

                                                break;

                                    case 2: del();

                                                break;

                                   case 3: display();

                                                break;

                                    case 4: exit(0);

                                    default: printf("\n\nPlease enter a valid choice");

                        }

            }

}

void add(char item)

{

            if(front == (rear+1)%MAX)

                        printf("\n\n~~Circular Queue Overflow~~");

            else

            {

                        if(front == -1)

                                    front = rear = 0;

                        else

                                    rear = (rear+1)%MAX;

                        cq[rear] = item;

            }

}

void del()

{

            char item;

            if(front == -1)

            {

                        printf("\n\n~~Circular Queue Underflow~~");

            }

            else

            {

                        item = cq[front];

                        if(front == rear) //only one element

                                    front = rear = -1;

                        else

                                    front = (front+1)%MAX;

                        printf("\n\nDeleted element from the queue is: %d ", item );

            }

}

void display ()

{

            int i ;

            if(front == -1)

            {

                        printf("\n\nCircular Queue Empty");

                        return;

            }

            else

            {

                        printf("\nCircular Queue contents are:\n");

                        printf("\nFront[%d]-> ", front);

                        for(i=front; i!=rear ; i=(i+1)%MAX)

                        {

                                    printf("  %d", cq[i]);

                        }

                        printf("  %d",cq[i]);

                        printf(" <-[%d]Rear", rear);

    }

}

Output:

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 11

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 22

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 33

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 44

~~Circular Queue Overflow~~

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 3

Circular Queue contents are:

Front[0]->   11  22  33 <-[2]Rear

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 2

Deleted element from the queue is: 11

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 2

Deleted element from the queue is: 22

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 3

Circular Queue contents are:

Front[2]->   33 <-[2]Rear

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 66

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 3

Circular Queue contents are:

Front[2]->   33  66 <-[0]Rear

Queue

Queue Topics: Module 2 Data Structures (15CS33) 

• Linear Queue

• Circular Queue

• Double Ended Queue (DEQueue)

• Priority Queue

Double Ended Queue using an array

Double Ended Queue using an array

#include<stdio.h>
#define MAX 5
int q[MAX];
int front = -1, rear= -1;

void insertAtRear(int item)
{
         if ( rear == MAX - 1 )
{
printf ( "\nDequeue is overflow" );
}
else
        {
                if(front==-1 &&rear==-1)
                           front=rear=0;
                else
                            rear=rear+1;
                q[rear] = item;
         }
}

void deleteAtFront()
{
           int item;
           if(front==-1)
                         printf("\nDequeue underflow");
           else
           {
                        item = q[front];
                        printf("\nItem deleted from queue is %d",item);
                        if(front == rear)  
                                    front = rear = -1;
                        else
                                    front = front+1;
            }
}

void insertAtFront(int item)
{
          int i;
          if( front == 0 && rear == MAX - 1 )
          {
                    printf ( "\nDequeue is overflow" ) ;
          }
          else
          {
                     if(front == -1 &&rear == -1)
                     {
                                 front = rear = 0;
                     }
                     else if(front == 0 && rear>=0)
                     {
                                for(i = rear; i>=front; i--)
                                              q[i+1] = q[i];
                                 rear = rear+1;
                      }
                      else if(front != 0)
                     {
                                 front = front - 1;
                     }
                     q[front]=item;
           }
}

void deleteAtRear()
{
            int item;
            if(front==-1)
                          printf("\nDequeue underflow");
            else
            {
                          item = q[rear];
                          printf("\nItem deleted from queue is %d", item);
                          if(front == rear)
                                      front = rear = -1;
                          else
                                      rear = rear-1 ;
            }
}

void display()
{
             int i;
             printf("\nfront  = %d  rear=%d", front, rear);
             if(front == -1)
             {
                         printf("\nEmpty");
                         return;
              }
              else
             {
                        printf("\nContents are: \n");
                        for(i=front; i<=rear; i++)
                                         printf("%d ", q[i]);
             }
}

void main()
{
     int ch, item;
    while(1)
    {
        printf("\n\n~~Menu~~");
        printf("\n1.Insert at front");
        printf("\n2.Delete from front");
        printf("\n3.Insert at rear");
        printf("\n4.Delete at rear");
        printf("\n5.Display");
        printf("\n6.Exit");
        printf("\nPlease enter a valid choice:");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1: printf("\nEnter the item to be inserted:  ");
                    scanf("%d", &item);
                    insertAtFront(item);
                    display();
                    break;

            case 2: deleteAtFront();
                    display();
                    break;

            case 3: printf("\nEnter the item to be inserted:  ");
                    scanf("%d",&item);
                    insertAtRear(item);
                    display();
                    break;

            case 4: deleteAtRear();
                    display();
                    break;

            case 5: display();
                    break;
            case 6: exit(0);
            default: printf("\nEnter the valid choice:  ");
                    break;
        }
    }
}


Output

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:1

Enter the item to be inserted:  11

front  = 0  rear = 0
Contents are:
11

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:1

Enter the item to be inserted:  22

front  = 0  rear = 1
Contents are:
22     11

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:1

Enter the item to be inserted:  33

front  = 0  rear = 2
Contents are:
33      22       11

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:2

Item deleted from queue is 33

front  = 1  rear = 2
Contents are:
22      11

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:2

Item deleted from queue is 22

front  = 2  rear = 2
Contents are:
11

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:3

Enter the item to be inserted:  33

front  = 2  rear = 3
Contents are:
11    33

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:1

Enter the item to be inserted:  22

front  = 1  rear = 3
Contents are:
22    11    33

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:1

Enter the item to be inserted:  44

front  = 0  rear = 3
Contents are:
44     22      11      33

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:3

Enter the item to be inserted:  55

front  = 0  rear=4
Contents are:
44     22     11     33      55

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:3

Enter the item to be inserted:  77
Dequeue is overflow

front  = 0  rear=4
Contents are:
44     22     11      33      55

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:4

Item deleted from queue is 55

front  = 0  rear = 3
Contents are:
44    22     11    33

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:2

Item deleted from queue is 44

front  = 1  rear = 3
Contents are:
22    11     33

~~Menu~~
1.Insert at front
2.Delete from front
3.Insert at rear
4.Delete at rear
5.Display
6.Exit
Please enter a valid choice:6

Data Structures and Applications(15CS33): Module 2

Data Structures and Applications (15CS33):

Module 2

• Stack

• Recursion

• Queue