Prashnikaप्रश्निका
Code
About
‹ Back to the paper

Question 11

5 marks

Computer ScienceISC 2020 Specimen Computer Science Paper 1ProgramData structures

Write the program described below.

Circular Queue is a linear data structure in which the operations are performed based on FIFO…

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. Define a class Cqueue with the following details: Class name : Cqueue Data member/instance variable: ele[ ] : array to hold the integer elements cap : stores the maximum capacity of the array front : to point the index of the front rear : to point the index of the rear. Member functions/methods: Cqueue(int max) : constructor to initialize the data member cap = max, front = rear = 0 and create the integer array void insert(int v) : to add integers from the front index if possible else display the message(“full from rear”) int delete( ) : to remove and return elements from rear, if any, else returns -999 void display() : to display elements of circular queue Specify the class Cqueue giving the details of void insert(int) and int delete( ). Assume that the other functions have been defined. The main( ) function and algorithm need NOT be written.

Answer

Answer

void insert(int v)
{
    if ((front + 1) % cap == rear)
        System.out.println("full from rear");
    else
    {
        ele[front] = v;
        front = (front + 1) % cap;
    }
}

int delete()
{
    if (front == rear)
        return -999;
    int v = ele[rear];
    rear = (rear + 1) % cap;
    return v;
}
Explanation: As given in the question, elements are added at the front index and removed from the rear end, and front and rear both start at 0, so front == rear means the queue is empty. insert() checks whether moving front one step forward (with wrap-around using % cap) would meet rear; if so the queue is full and the message full from rear is shown (one position is kept unused to tell a full queue from an empty one). Otherwise the value is stored at ele[front] and front moves circularly. delete() returns -999 if the queue is empty; otherwise it returns the element at rear and moves rear forward circularly, so the element inserted first is removed first (FIFO). Tested with cap = 4: three inserts were accepted, the fourth printed full from rear, deletes returned the values in FIFO order and a delete on the empty queue returned -999.