Mumbai University > Computer Engineering > Sem 3 > Data Structures

Marks: 10M

Years: Dec 2015

Queue as ADT

1. The queue abstract data type is defined by the following structure and operations.
2. A queue is structured, as described above, as an ordered collection of items which are added at one end, called the “rear,” and removed from the other end, called the “front.”

3. Queues maintain a FIFO ordering property. The queue operations are given below.

   • Queue() creates a new queue that is empty. It needs no parameters and returns an empty queue.
   • enqueue(item) adds a new item to the rear of the queue. It needs the item and returns nothing.
   • dequeue() removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.
   • isEmpty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
   • size() returns the number of items in the queue. It needs no parameters and returns an integer.

Program to demonstrate insert, delete and display operations in Circular Queue:

#include<stdio.h>
#define SIZE 4
int front,rear;
void main()
{
    void insert(int[],int);
    void del(int[]);
    void display(int[]);
    int Q[SIZE];
    char choice;
    int data;
    front=rear=-1;
    do
    {
        clrscr();
        printf("\nEnter : i(insert), d(delete), q(Quit):");
        scanf("%c",&choice);
        switch(choice)
        {
            case 'i':
            case 'I':
                printf("\nEnter the data:");
                scanf("%d",&data);
                insert(Q,data);
                break;
            case 'd':
            case 'D':
                del(Q);
                break;
            case 'q':
            case 'Q':exit(0);
            default: printf("\nWrong key pressed\n");
                     getch();
                     continue;
        }
        display(Q);
        fflush(stdin);
        getch();

    }while(1);
}
void insert(int Q[],int data)
{
    if(rear==SIZE-1)
        rear=0;
    else
        rear++;
    if(front==rear)
    {
        printf("\nQueue overflow\n");
        exit(1);
    }
    Q[rear]=data;
    if(front==-1)
        front++;
}
void del(int Q[])
{
    if(front<0)
    {
        printf("\nQueue underflow\n");
        exit(1);
    }
    printf("\nDelete element: %d\n",Q[front]);
    if(front==rear)
        front=rear=-1
    else
    {
        if(front==SIZE-1)
            front=0;
        else
            front++;
    }
}
void display(int Q[])
{
    int position;
    if(front>0)
    {
        printf("\nTotal size of the queue: &d\n",SIZE);
        printf("\nQueue after the operation performed:\n\n");
        if(front<=rear)
        {
            for(position=front;position<=rear;position++)
                printf("%d",Q[position]);
        }
        else
        {
            for(position=front;position<SIZE;position++)
                printf("%d",Q[position]);
            for(position=0;position<=rear;position++)
                printf("%d",Q[position]);
        }
    }
    printf("\n\nFront=%d Rear= %d\n",front,rear);
}

Output:

Enter: i (insert), d (delete), q (Quit): i

Enter the data: 10

Total size of the queue: 4

Queue after the operation performed:10

Front=0 Rear=0

Enter: i (insert), d (delete), q (Quit): i

Enter the data: 20

Total size of the queue: 4

Queue after the operation performed:10 20

Front=0 Rear=1

Enter: i (insert), d (delete), q (Quit): i

Enter the data: 30

Total size of the queue: 4

Queue after the operation performed:10 20 30

Front=0 Rear=2

Enter: i (insert), d (delete), q (Quit): i

Enter the data: 40

Total size of the queue: 4

Queue after the operation performed:10 20 30 40

Front=0 Rear=3

Enter: i (insert), d (delete), q (Quit): i

Enter the data: 10

Total size of the queue: 4

Queue overflow