PRASHNIKAप्रश्निका
‹ Back to the paper

A double ended queue is a linear data structure which enables the user to add and remove integers…

Computer Science20234 marksProgram
A double ended queue is a linear data structure which enables the user to add and remove integers from either ends i.e., from front or rear. The details of the class deQueue are given below:
Class name:deQueue
**Data members/ instance variables:**
Qrr[ ]:array to hold integer elements
lim:maximum capacity of the dequeue
front:to point the index of the front end
rear:to point the index of the rear end
**Methods / Member functions:**
deQueue(int l):constructor to initialise $lim = l$, $front = 0$ and $rear = 0$
void addFront(int v):to add integers in the dequeue at the front end if possible, otherwise display the message “OVERFLOW FROM FRONT”
void addRear(int v):to add integers in the dequeue at the rear end if possible, otherwise display the message “OVERFLOW FROM REAR”
int popFront( ):removes and returns the integers from the front end of the dequeue if any, else returns -999
int popRear( ):removes and returns the integers from the rear end of the dequeue if any, else returns -999
void show( ):displays the elements of the dequeue
(i) Specify the class deQueue giving details of the functions void addFront(int) and int popFront( ). Assume that the other functions have been defined. The main( ) function and algorithm need NOT be written.

Answer

Answer

AI
class deQueue
{
    int Qrr[];   // array holding the elements
    int lim;     // maximum capacity
    int front;   // front end index
    int rear;    // rear end index

    deQueue(int l)
    {
        lim = l;
        front = 0;
        rear = 0;
        Qrr = new int[lim];
    }

    // adds v at the front end if there is room before front
    void addFront(int v)
    {
        if (front > 0)
        {
            Qrr[front] = v;
            front--;
        }
        else
            System.out.println("OVERFLOW FROM FRONT");
    }

    // removes and returns the element at the front end, or -999 if empty
    int popFront()
    {
        if (front == rear)
            return -999;
        front++;
        return Qrr[front];
    }
}
The elements occupy positions front + 1 to rear, so the dequeue is empty when front == rear (both start at 0, as the constructor sets). addFront() stores the value at index front and moves front one step left; when front is 0 there is no room at the front, so it reports overflow. popFront() moves front one step right and returns the element there, or -999 if the dequeue is empty. (addRear() correspondingly does rear++ then Qrr[rear] = v while rear < lim - 1.) Tested with the other functions filled in: after addRear(10), addRear(20), addRear(30), popFront() returned 10 and then 20; addFront(15) then put 15 in front of 30; popFront() gave 15, 30 and then -999.
Data structures

From ISC 2023 Computer Science Paper 1, question 9(i).

More from this chapter