‹ 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.