Showing posts with label queue. Show all posts
Showing posts with label queue. Show all posts

Friday 2 September 2016

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) 



Tuesday 30 August 2016

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