Linear Queue using an array

Linear Queue using an Array

#include<stdio.h>

#include<stdlib.h>

#define MAX 5

int front = -1;

int rear = -1;

int q[MAX];

void insert();

void delete();

void display();

void main()

{

            int ch;

            while(1)

            {

                        printf("\n\nMenu\n1.Insert\n2.Delete\n3.Display\n4.exit");

                        printf("\nEnter your choice:\t");

                        scanf("%d",&ch);

                        switch(ch)

                        {

                                    case 1:                         insert();

                                                            display();

`                                                           break;

                                    case 2:                         delete();

                                                            display();

                                                            break;

                                    case 3:                         display();

                                                            break;

                                    case 4:                         exit(0);

                                    default:            printf("\nInvalid Choice\n");

                        }

            }

}

void insert()

{

            int item;

            if(rear == MAX-1)

            {

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

                        return;

            }

            printf("\nEnter the item to to be inserted:");

            scanf("%d", &item);

            rear = rear+1;

            q[rear] = item;

}

void delete()

{

            int item;

            if(front == rear)

            {

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

                        return;

            }

            front = front+1;

            item = q[front];

            printf("\nThe item that got deleted is: %d", item);

}

void display()

{

            int i;

            printf("\nfront = %d, rear = %d",front, rear);

            if(front == rear)

            {

                        printf("\nQueue is empty\n");

                        return;

            }

            else

            {

                        printf("\nElements of the queue are: ");

                        for(i=front+1; i<=rear;i++)

                                                            printf("%d\t",q[i]);

            }

}

Output:

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      1

Enter the item to to be inserted: 11

front = -1, rear = 0

Elements of the queue are: 11

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      1

Enter the item to to be inserted:       22

front = -1, rear = 1

Elements of the queue are: 11   22

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      1

Enter the item to to be inserted:         33

front = -1, rear = 2

Elements of the queue are: 11   22   33

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      1

Enter the item to to be inserted:       44

front = -1, rear = 3

Elements of the queue are: 11   22    33   44

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      1

Enter the item to to be inserted: 55

front = -1, rear = 4

Elements of the queue are: 11   22  33  44  55

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      1

~~~Queue Overflow~~~

front = -1, rear = 4

Elements of the queue are: 11  22  33  44  55

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      2

The item that got deleted is:            11

front = 0, rear = 4

Elements of the queue are: 22   33  44  55

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      2

The item that got deleted is:             22

front = 1, rear = 4

Elements of the queue are: 33   44   55

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      2

The item that got deleted is:             33

front = 2, rear = 4

Elements of the queue are: 44   55

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      2

The item that got deleted is:             44

front = 3, rear = 4

Elements of the queue are: 55

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      2

The item that got deleted is: 55

front = 4, rear = 4

Queue is empty

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      2

~~~Queue Underflow~~~

front = 4, rear = 4

Queue is empty

Menu

1.Insert

2.Delete

3.Display

4.exit

Enter your choice:      4

Queue

Queue Topics: Module 2 Data Structures (15CS33) 

• Linear Queue

• Circular Queue

• Double Ended Queue (DEQueue)

• Priority Queue

Two Stacks in a Single Array

Two Stacks in a Single Array

#include<stdio.h>
#define MAX 5
int s[MAX];
int top1 = -1, top2 = MAX;

void push(int stackno, int item)
{
         if(stackno==1)
        {
                 if(top1+1==top2)
                 {
                              printf("\nStack is full");
                  }
                  else
                  {
                             top1 = top1+1;
                             s[top1] = item;
                  }
          }
          else if(stackno==2)
          {
                  if(top2-1== top1)
                  {
                             printf("\nStack is full");
                   }
                   else
                  {
                             top2 = top2-1;
                             s[top2] = item;
                   }
          }
}

void pop(int stackno)
{
           int item;
           if(stackno == 1)
           {
                   if(top1 == -1)
                   {
                              printf("\nStack1 is empty");
                    }
                    else
                    {
                            item = s[top1];
                            top1 = top1-1;
                            printf("\nItem that got deleted from stack1 is %d", item);
                    }
           }
           else if(stackno == 2)
           {
                    if(top2 == MAX)
                   {
                           printf("\nStack2 is empty");
                   }
                   else
                   {
                           item = s[top2];
                           top2 = top2+1;
                           printf("\nItem that got deleted from stack2 is %d", item);
                   }
           }
}

void display()
{
           int i;
           if(top1 == -1)
           {
                   printf("\nStack 1 is empty");
           }
          else
          {
                   printf("\nStack 1 contents are:\n");
                   for(i=top1;i>=0;i--)
                              printf("| %d |\n", s[i]);
           }
           if(top2==MAX)
           {
                     printf("\nStack 2 is empty");
           }
          else
          {
                     printf("\nStack 2 contents are:\n");
                     for(i=top2;i<MAX;i++)
                                   printf("| %d |\n", s[i]);
          }
}

void main()
{
    int stackno, ch, item;
    while(1)
    {
        printf("\n\n~~~Menu~~~");
        printf("\n1.Push operation");
        printf("\n2.Pop operation");
        printf("\n3.Display");
        printf("\n4.exit");
        printf("\nEnter your choice: ");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1: printf("\nEnter the stack number: ");
                    scanf("%d",&stackno);
                    printf("\nEnter the item:  ");
                    scanf("%d", &item);
                    push(stackno, item);
                    display();
                    break;
            case 2: printf("\nEnter the stack number:  ");
                    scanf("%d", &stackno);
                    pop(stackno);
                    display();
                    break;
            case 3: display();
                    break;
            case 4:exit(0);
            default: printf("\nPlease enter a valid choice: ");

        }
    }
}


Output:
~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 1

Enter the stack number: 1
Enter the item:  11

Stack 1 contents are:
| 11 |

Stack 2 is empty

~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 1

Enter the stack number:  1
Enter the item:  12

Stack 1 contents are:
| 12 |
| 11 |

Stack 2 is empty

~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 1

Enter the stack number: 1
Enter the item:  13

Stack 1 contents are:
| 13 |
| 12 |
| 11 |

Stack 2 is empty

~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 1

Enter the stack number: 2
Enter the item:  21

Stack 1 contents are:
| 13 |
| 12 |
| 11 |

Stack 2 contents are:
| 21 |


~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 1

Enter the stack number: 2
Enter the item:  22

Stack 1 contents are:
| 13 |
| 12 |
| 11 |

Stack 2 contents are:
| 22 |
| 21 |


~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 1

Enter the stack number: 2
Enter the item:  23

Stack is full

Stack 1 contents are:
| 13 |
| 12 |
| 11 |

Stack 2 contents are:
| 22 |
| 21 |


~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 2

Enter the stack number:  2
Item that got deleted from stack2 is 22

Stack 1 contents are:
| 13 |
| 12 |
| 11 |

Stack 2 contents are:
| 21 |


~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 2

Enter the stack number:  1
Item that got deleted from stack1 is 13

Stack 1 contents are:
| 12 |
| 11 |

Stack 2 contents are:
| 21 |


~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 3

Stack 1 contents are:
| 12 |
| 11 |

Stack 2 contents are:
| 21 |


~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 4

Priority Queue using an array

Priority Queue 

#include<stdio.h>

#include<stdlib.h>

#define QUEUESIZE 5

int front = -1,rear = -1;

struct priority_queue

{

        int job;

        int priority;

}q[QUEUESIZE];

void insert(int job, int priority)

{

            int j;

            if(rear == (QUEUESIZE-1))

            {

                        printf("\n~~Queue overflow~~");

                        return;

            }

            else

            {

                        if(front == -1&&rear == -1)

                        {

                                    front = rear = 0;

                                    q[rear].job = job;

                                    q[rear].priority = priority;

                        }

                        else

                        {

                                     j = rear;

                                    while(j>=0 && priority <q[j].priority)

                                    /* To find the proper place to insert based on priority */

                                    {

                                                q[j+1].job = q[j].job;

                                                j--;

                                    }

                                    q[j+1].job = job;

                                    q[j+1].priority = priority;

                                    rear = rear + 1;

                        }

            }

}

void delete()

{

            int ele;

            if(front ==-1 && rear == -1)

            {

                        printf("\n~~Queue underflow~~");

            }

            else

            {

                        ele = q[front].job;

                        printf("\nJob%d deleted from queue", ele);

                        if(front == rear)

                                    front = rear = -1;

                        else

                                    front = front + 1;

            }

}

void display()

{

            int i;

            if(front ==-1  && rear == -1)

            {

                        printf("\nEmpty List!!! Nothing to display");

                        return;

            }

            else

            {

                        printf("\nContents of priority queue are : \n");

                        for(i=front; i<=rear; i++)

                                    printf("Job%d \t", q[i].job);

            }

}

void main()

{

            int job, priority, ch;

            while(1)

            {

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

                        printf("\n1: Insert into priority queue");

                        printf("\n2:Delete from priority queue");

                        printf("\n3:Display");

                        printf("\n4:Exit");

                        printf("\nEnter the choice:  ");

                        scanf("%d", &ch);

                        switch(ch)

                        {

                                    case 1: printf("\nEnter the job number: ");

                                                scanf("%d", &job);

                                                printf("\nEnter the priority of Job%d:  ", job);

                                                scanf("%d", &priority);

                                                insert(job, priority);

                                                display();

                                                break;

                                    case 2: delete();

                                                display();

                                                break;

                                    case 3: display();

                                                break;

                                    case 4: exit(0);

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

                                                break;

                        }

            }

 }

Output:

~~~Menu~~~

1: Insert into priority queue

2:Delete from priority queue

3:Display

4:Exit

Enter the choice:  1

Enter the job number: 3

Enter the priority of Job3:  2

Contents of priority queue are :

Job3

~~~Menu~~~

1: Insert into priority queue

2:Delete from priority queue

3:Display

4:Exit

Enter the choice:  1

Enter the job number: 7

Enter the priority of Job7:  1

Contents of priority queue are :

Job7    Job3

~~~Menu~~~

1: Insert into priority queue

2:Delete from priority queue

3:Display

4:Exit

Enter the choice:  1

Enter the job number: 5

Enter the priority of Job5:  3

Contents of priority queue are :

Job7    Job3    Job5

~~~Menu~~~

1: Insert into priority queue

2:Delete from priority queue

3:Display

4:Exit

Enter the choice:  1

Enter the job number: 9

Enter the priority of Job9:  2

Contents of priority queue are :

Job7    Job3    Job9    Job5

~~~Menu~~~

1: Insert into priority queue

2:Delete from priority queue

3:Display

4:Exit

Enter the choice:  1

Enter the job number: 2

Enter the priority of Job2:  5

Contents of priority queue are :

Job7    Job3    Job9    Job5    Job2

~~~Menu~~~

1: Insert into priority queue

2:Delete from priority queue

3:Display

4:Exit

Enter the choice:  1

Enter the job number: 4

Enter the priority of Job4:  2

~~Queue overflow~~

Contents of priority queue are :

Job7    Job3    Job9    Job5    Job2

~~~Menu~~~

1: Insert into priority queue

2:Delete from priority queue

3:Display

4:Exit

Enter the choice:  2

Job7 deleted from queue

Contents of priority queue are :

Job3    Job9    Job5    Job2

~~~Menu~~~

1: Insert into priority queue

2:Delete from priority queue

3:Display

4:Exit

Enter the choice:  2

Job3 deleted from queue

Contents of priority queue are :

Job9    Job5    Job2

~~~Menu~~~

1: Insert into priority queue

2:Delete from priority queue

3:Display

4:Exit

Enter the choice:  4