Contents
Chapterwise Question Bank CBSE Class 12 Computer Science (C++) – Queue
Exam Practice
Very Short Answer Type Questions [1 Mark]
Question 1:
An array circular queue [10] of integers exist, where currently
Rear = 0, Front = 1
Answer the following questions based on the above given data:
(i) How many values are there in queue?
(ii) If five values are deleted, what would be the new value of Front?
Answer:
(i) 10
(ii) Front =6
Question 2:
Suppose a data structure is stored in a circular queue with N memory locations, what will be the queue full condition?
Answer:
Circular queue will be full if ((Front==Rear +1)| | (Front ==0 && Rear==N-l))
Question 3:
How will you know that a linear queue is full?
Answer:
In a linear queue, if Rear is equal to maximum size then queue is full.
Question 4:
Suppose a circular queue is stored in an array with N memory locations. Find the number of elements in the queue in terms of Front and Rear.
Answer:
(i) If Front<Rear
Then number of elements, = Rear – Front +1
(ii) IfFront>Rear
Then number of elements = N + (Rear – Front)+l
Short Answer Type Questions
Question 5:
Suppose a circular queue is maintained by an array Q with 12 memory locations and Front and Rear are the two pointers.
Find the number of elements in Q when:
(i) Front = 4, Rear = 8
(ii) Front = 10, Rear = 3
(iii) Front =5, Rear = 6
and then two elements are deleted.
Answer:
(i) Front = 4, Rear = 8
Here, Front < Rear
So, number of elements = Rear – Front +1
= 8-4+1=5
(ii) Front = 10, Rear = 3
Here, Front > Rear
So, number of elements = N+(Rear-Front) +1
= 12 + (3 -10) + 1 = 6
(iii) Front = 5, Rear = 6
Here, Front < Rear
So, number of elements = Rear – Front +1
= 6-5+1=2
Now, when first element is deleted from Front it will point to 6 index, i.e. Front becomes equal to Rear.
Then, after deleting one more element, queue will become empty and both Front and Rear becomes equal to -1.
Question 6:
What do Front and Rear signify in a queue? if in a queue, the Rear points to the Front, how many elements are there in queue?
Answer:
In queue, Front stands for beginning of the queue. From Front, element will be deleted. Rear stands for position of the last element of the queue.
From Rear new element will be added in queue. In a queue, if Rear points to the Front then queue is either empty or is having 1 element.
Question 7:
What are the drawbacks of linear queue?
Answer:
Drawbacks of linear queue are:
By the definition of a queue, when we add an element in queue, Rear pointer is increased by 1 whereas, when we remove an element, Front pointer is increased by 1.
But, in array implementation of queue this may cause problem as follows:
Consider the operations performed on a queue (with SIZE = 5) as follows:
(iv) Now, actually we have deleted 2 elements from queue so, there should be space for another 2 elements in the queue, but as Rear pointer is pointing at last position. So, queue overflow condition is reached.
(Rear == SIZE-1) is true, we can’t insert new element in the queue even if it has an empty space. To overcome this problem, there is another variation of queue called circular queue.
Question 8:
What is a circular queue? How is it different from queue?
Answer:
In a queue as a circular array we assume first element of the array as immediately next to its last element, i.e. if the last position of the array is having an element, a new element can be inserted next to it, at the first position of the array (if empty). A circular queue prevents an excessive use of memory.
The number of elements in a circular queue is given by, Number of elements = R – F + 1 (when R > F) and Number of elements = N + (R-F) + 1 (when F > R).
Question 9:
QUEUE is a queue with 6 memory locations and with Front = 2, Rear = 5. Indexing should be start from 1.
QUEUE:…………………….., London, Berlin, Rome, Paris,……………………..,
where…………………….., denoted empty locations.
Diagrammatically display the queue including Front and Rear as the following operations take place:
(i) Athens is added (ii) Two cities are deleted
(iii) Madrid is added (iv) Moscow is added
(v) Three cities are deleted (vi) Oslo is added
Answer:
(iii) Madrid is added, overflow occurs because queue is full. Insertion is not possible.
(iv) Moscow is added, overflow occurs because queue is full. Insertion is not possible.
(v) Three cities are deleted
Question 10:
Consider a queue of size 5. Insert elements 2, 4, 6, 8 and then delete first two elements. After deleting, insert 10, 12 in the queue. Show the status of Front and Rear in each step.
Answer:
Question 11:
(i) Give the number of elements in a circular queue,
(ii) With 12 memory locations if Front – 10 and
Rear = 3. If 4 elements are deleted from above
queue, what will be the value of Front and Rear?
Answer:
(i) if Front < Rear then
The total number of elements = Rear – Front +1
if Front > Rear then
The total number of elements = N +(Rear-Front) +1
(ii) Initial circular queue with size of 12 element
Long Answer Type Questions [4/5 Marks]
Question 12:
Write a function QINSERTf) in C++ to perform insert operation on a linked queue, which contains Client no and Client name. Consider the following definition of NODE in the code of QINSERT(): Delhi 2013
struct NODE { long int Cno; //Client number char Cname[20]; //Client name NODE *Next; };
Answer:
void QINSERT() { NODE *N = new NODE; cout<<"Enter the Client Number and Name"; cin>>N—>Cno>>N—>Cname; N—>Next = NULL; if(FRONT == NULL && REAR == NULL) FRONT = REAR = N; else { REAR—>Next = N; REAR = N; } }
Question 13:
Write a function QDELETEf) in C++ to perform delete operation on a Linked Queue, which contains Passenger number and Passenger name. Consider the following definition of node in the code: All India 2013
struct node { long int Pno; char Pname[20]; node *Link; };
Answer:
void QDELETE() { if(Front == NULL) { cout<<"Stack is empty"; exit(0); } else { node *temp; cout<<"Passenger Information^" ; cout<<"Number:"<<Front—>Pno<<endl; cout<<"Name:"<<Front—>Pname; temp = Front; Front = Front—>Link; delete temp; } }
Question 14:
Write a function in C++ to perform insert operation in a dynamic queue containing DVD’s information (represented with the help of an array of structure DVD). Delhi 2012
struct DVD { long No; char title[20]; DVD *Link; };
Answer:
void Insert() { DVD *p = new DVD; cout<<”Enter the DVD Number and Title"; cin>>p—>No; gets(p—>title); p —> Link = NULL; if((front == NULL)&&(rear = NULL)) { front = rear = 'p; } else { rear->Link = p; rear = p; } }
Question 15:
Write a complete program in C++ to implement a dynamically allocated queue containing names of cities. All India 2010
Answer:
#include<iostream.h> #include<conio.h> #include<string.h> #include<stdio.h> #include<ctype.h> #include<stdlib.h > struct Node { char city[30]; Node *link; }; class queue { Node *front, *rear; public: queue() {front = rear = NULL;} void add_Q(); //add queue void del_Q(); //delete queue void show_Q(); //show queue }; void queue :: add_Q() { Node *temp = new Node; char ct[30]; cout<<"Enter city"; gets(ct); strcpy(temp—>city,ct); temp—>link = NULL; rear—>link = temp; rear = temp; if(front == NULL) front = rear; } void queue :: del_Q() { Node *temp; char ct[20]; if(front == NULL) { cout<<"queue empty"; } else { temp = front; front = front—>link; strcpy(ct,temp—>city); temp—>link = NULL; cout<<"Deleted values are"<<ct; delete temp; } if(front == NULL) rear = front; } void queue :: show_Q() { Node *temp; temp = front; cout<<”The queue elements are"; while(temp != NULL) { cout<<"\n"<<temp—>city; temp = temp—>link; void main() { int choice; queue QUEUE; char opt = 'Y'; //Initialisation of queue clrscr(); do { cout<<"\nMain Menu"; cout<<"\nl.Addition of queue"; cout<<"\n2.Deletion of queue"; cout<<"\n3.Traverse of queue"; cout<<"\n4.Exit from queue"; cout<<"\nEnter your choice from above(1,2,3,4)"; cin>>choice; switch(choice) { case 1: do { QUEUE.add_Q(); cout<<"\nDo you want to add more elements<Y/N>?"; cin>>opt; } while(toupper(opt) == 'Y’); break; case 2: opt = 'Y'; do { QUEUE.del_Q(); cout<<”\nDo you want to delete more elements <Y/N>?"; cin>>opt; } whi1ettoupper(opt) == 'Y'); break; case 3: QUEUE.show_Q(); break; case 4: exit(0); default: cout<<”Your choice is wrong”; } }whi1e(choice != 4); getch(); }
Question 16:
Write a function in C++ to perform delete operation on a dynamically allocated queue containing members details as given in the following definition of NODE: All India 2011
struct NODE { long Mno; //Member Number char Mname[20]; //Member Name NODE *Link; }:
Answer:
Let front is declared as NODE *front; represents front of the queue, which is passed to the following function:
void remove(NODE *front) { NODE *nptr; if(front == NULL) { cout<<”Underflow”; return; } else { nptr = front; front = front—>Link; if(front == NULL) rear = NULL; delete nptr; } }
Question 17:
Write a function QUEINS() in C++ to insert an element in a dynamically allocated queue containing nodes of the folio wing given structure: Delhi 2009
struct Node { int Pid; //Product id char Pname[20]; //Product name Node *Next; };
Answer:
void QUEINS() { Node *temp=new Node; cout<<"Enter the PID and Name”; cin>>temp—>Pid; gets(temp—>Pname); temp—>Next=NULL; rear—>Next=temp; rear=temp; if(front == NULL) front=temp; }
Question 18:
Give the necessary declaration of a linked list implemented queue containing float type values. Also, write a user defined function in C++ to add a float type number in the queue.
Answer:
// Declares a queue structure struct node { float data; node *link; }; void QUEINSERT() { node *temp=new node; cout<<"Enter float data”; cin>>temp—>da*ta; temp—>link=NULL;- real—>11nk=temp; rear=temp; if(front = NULL) front=temp; }
Question 19:
Write a function in C++ to insert an element in a dynamically allocated queue, where each node contains a Name(char) as data. Assume the following definition of THENODE for the same: Delhi 2008
struct THENODE { { char Name[20]; THENODE *Link; };
Answer:
void insert(THENODE *rear) { THENODE *newptr = new THENODE; newptr—>Link = NULL; cout<<"Enter name for new node"; gets(newptr—>Name); if(rear == NULL) { front = rear = newptr; } else { rear—>Link = newptr; rear = newptr; } }
Question 20:
Write a function in C++ to delete an element in a dynamically allocated queue, where each node contains a real number as data. Assume the following definition of MYNODE for the same: All India 2008
struct MYNODE { float NUM; MYNODE *Link; };
Answer:
void Delete(MYNODE *front) { MYNODE *ptr = front; if(ptr == NULL) { COUt<<"UNDERFL0W"; exit(1); } else if(front == rear) { delete ptr; front = rear = NULL; } else { front = front—>Link; delete ptr; } }
Question 21:
Consider the following portion of a program, which implements passengers queue for a bus. Write the definition of function lnsert(), to insert a new node in the queue with required information.
struct NODE { int Ticketno; char PName[20]; //Passenger name NODE *Next; }; class Queueofbus { NODE *rear, *front; public: Queueofbus() { rear = NULL; front = NULL; } void Insert(); void Delete(); “Queueofbus(); };
Answer:
void Queueofbus :: Insert() { NODE *nptr = new NODE; nptr—>Next = NULL; coutC<<"Enter the ticket number"; cin>>nptr—>Ticketno; cout<<"Enter the passenger name"; gets(nptr—>PName); if(rear == NULL) { front = rear = nptr; } else { rear—>Next = nptr; rear = nptr; } }
Question 22:
Write a function QUEDEL() in C++ to display and delete an element in a dynamically allocated queue containing nodes of the follo wing given structure: All India 2009
struct Node { int Itemno; char Itemname[30]; Node *Link; };
Answer:
//Function t.o delete queue elements Node *QUEDEL(Node *front,int val,char val1[]) { Node *temp; if(front == NULL) cout<<"Queue Empty"; else { temp = front; val = temp—>Itemno; strcpy (val1, temp—>temname); front = front—>Link; if(front == NULL) rear = NULL; delete temp; } return(front); }
Question 23:
Write a function in C++ to delete a node containing customer’s information, from dynamically allocated queue of customers implemented with the help of the folio wing structure:
struct Customer { int CNo; char CName[20]; Customer *Link; };
Answer:
Let front is declared as
Customer *front;
Represents the front of the queue, which is passed to the following function:
void Delete(Customer *front) { Customer *ptr; int a; char b[20]; if(front = NULL) { cout<<"Queue Empty!!"; return; } else { ptr = front; front = front—>Link; a = ptr—>CNo; strcpy(b,ptr—>CName); cout<<"Deleted customer information"; cout<<endl ; cout<<"Customer No"<<a<<endl ; cout<<"Customer Name"<<b; delete ptr; } if(front == NULL) rear = front; }
Question 24:
class queue { int data[10]; int front,rear; public: queue() { front = -1; rear = -1; { void add( ); //To add an element into the queue void remove(); //To remove an element from the queue void Delete(int ITEM); //To delete all the elements which are //equal to ITEM }
Complete the class with all the function definitions for a circular queue. Use another queue to transfer data temporarily.
Answer:
class queue { int data[10]; int front,rear; public: queue() { front =-1; rear =-1; } void add(); void remove(); void Delete(int ITEM); }; void queue :: add() { if((front == 0 && rear == 9) || (rear == front-1)) { cout<<"0verflow"; return; } int x; cout<<"Enter the data”; cin>>x; if(ear == -1) { front = 0; rear = 0; } else if(rear f= 9) rear = 0; else rear++; data[rear] = x; } void queue :: remove() { if(front == -1) { cout<<”Underf1ow"; return; } int x; x = data[front]; if(front == rear) { front = -1; rear = -1; } else if(front == 9) front = 0; else front++; cout<<x<<"removed"; } void queue :: Delete(int ITEM) { if(front == -1) { cout<<"Underflow"; return; } queue t; t.front = 0; while(1) { if(data[front] != ITEM) { t.rear++; t.data[t.rear] = data[front]; } if(front == rear) break; front++; if(front == 10) front = 0; } //copy temp data to current data front = 0; rear = -1; while(t.front <= t.rear) { rear++; data[rear] = t.datatt.front]; t.front++; } }
Question 25:
Give the necessary declarations of a queue containing integers. Write a user defined function in C++ to delete an integer from the queue. The queue is to be implemented as a linked structure.
Answer:
struct node { int data; node *link; }: //Function body for delete an integer //from the queue node *del_Q(node *front,int &val) { node *temp; if(front == NULL) { cout<<"Queue empty"; val = -1; } else { temp = front; front = front—>link; val = temp—>data; temp—>link = NULL; delete temp; } return(front); }
Question 26:
Define member functions queins() to insert and quedel() to delete nodes of the linked list implemented class queue, where each node has the following structure:
struct node { char name[20]; int age; node *Link; }; class queue { node *rear,*front; public: queue() { rear=NULL; front=NULL; } void queins(); void quedel(); };
Answer:
//Function to insert node in a queue void queue :: queins() { node *temp = new node; cout<<"Enter the name"; gets(temp—>name); cout<<"Enter age”; cin>>temp—>age; temp—>Link = NULL; if(rear == NULL) { front = rear = temp; } else { rear—>Link = temp; rear = temp; } } // Function body for delete node queue elements void queue :: quedel() { node *temp; if(front == NULL) { cout<<"Queue empty"; } else { temp = front; front = front—>Link; temp—>Link = NULL; delete temp; } }
Question 27:
Consider a linked implementation of a queue with N memory locations. How are Prev and Next changed if an element is deleted, where PREV is pointer to previous node and NEXT is pointer to next node.
Answer:
Let temp be a pointer pointing to that node, which is deleted.
Computer ScienceChapterwise Question Bank for Computer ScienceNCERT Solutions