DS Unit 4 Notes

UNIT –4 QUEUES
(2 , 4 & 8 MARKS QUESTIONS)

1) Define queue? Explain how pointer front and rear related to queue with diagram. (Definition 2 marks, explanation of each pointer 1M)
Ans:
A Queue is an ordered collection of items.
It has two ends, front and rear.
Front end is used to delete element from queue.
Rear end is used to insert an element in queue.
Queue has two ends; the element entered first in the queue is removed first from the queue. So it is called as FIFO(FIRST IN FIRST OUT) list.

queue
Element is inserted in the list at a position indicated by rear end.
For inserting an element rear end is incremented by one.
Before insertion:

beforeinsertion

Element can be deleted from a list from the position indicated by front end.
For deleting an element rear end is incremented by one.
Before deletion:

beforedeletion

 

2) Describe the queue as abstract data type.(Elements – 2 M, Operations – 2 M)
Ans:
Queue is a data structure which allows a programmer to insert an element at one end known as “Rear” and to delete an element at other end known as “Front”.
Queue is an abstract data type because it not only allows storing a elements but also allows to perform certain operation on these elements.
These operations are as follows.
 Insert
 Delete
 isempty
 isfull
Elements of queue:-
Following are elements of queue
 Front
 Rear
 array

 

3) Explain queue as an abstract data type, also give applications of queue. (ADT – 3 Marks, Application – 1 mark)
Ans:
Definition:
1. Queue is the most common abstract data type.
2. It follows the first in first out (FIFO) structure.
3. The elements are added in the end known as the ‘rear’ of the queue.
4. The elements are removed front the first, known as the ‘front’ of the queue.
Operations: Insert, delete an element.
Application areas of queue:
1. Banking 2. Network

 

4) Distinguish between stack and queue with minimum 4 points. (4 points each -1M)
Ans:

Stack Queue
In Stack insertion and deletion operations are performed at same end  In Queue insertion and deletion operations are performed at different end
 In stack the element which is
inserted last is first to delete so it is called Last In first Out
 In Queue the element which is
inserted first is first to delete so it is called first In first Out
 In stack only one pointer is used called Top  In Queue two pointer is used called front, rear
 In Stack Memory is not wasted  In Queue memory can be wasted/
unusable in case of linear queue.
 In computer system stack is for
procedure calls
 Queue is used for time/resource
sharing system;
 Plate Counter at marriage reception is an example of stack  students standing in a line at fee
counter is an example of queue

5) Write a procedure for inserting and element in a queue.
(Procedure- Any other logic shall be considered – 4 Marks)
[Note: Appropriate steps describing procedure for inserting shall be considered.]
Ans:
INSERT(QUEUE, F, R, N, item)
[This procedure will insert an element ‘item’ in QUEUE where ‘R’ is rear end of
queue, ‘F’ is front end of queue and ‘N’ is size of array.] 1. [Check for Overflow]
if (R >= N-1)
write queue is full.
return.
2. [Check position of rear pointer in a queue]
If( R==-1)
Set R=0;
F=0;
Else
[Increment R by 1] R =R + 1
3. [Insert Element]
QUEUE [R]=item.
4. Exit.

6) Write a procedure to insert an element into a queue and to delete an element from a queue. (Insert procedure- 2Marks, Delete procedure- 2Marks)
Ans:
Procedure for Insert:-
Step 1: [check overflow]
if rear = max -1 then write
“queue is full”
return
otherwise go to step 2
Step 2: [increment rear point]
rear = rear + 1
Step 3: [insert element]
a [rear] = item
Step 4: [check front pointer]
if front = -1 then assign 0 value to front
Step 5: End / return to calling function
Procedure for Delete:-
Step 1: [check Underflow]
if front = -1 then write
“queue is empty”
return
otherwise go to step 2
Step 2: [copy data]
Data = a [front] Step 3: [check front and rear pointer]
if front = rear then
front = rear = -1
otherwise
front = front + 1
Step 4: Return to calling function

7) Write a menu driven program to insert, delete an element in a queue and display the queue. ( 2 marks each for insert, delete and display function. 2 marks for menu driven main program)
Ans:
// Implementation Of Queue And Operations On Queue
#include<stdio.h>
#include<conio.h>
# define max 6
int q[max];
int f=0,r=-1;
void empty( );
void full( );
void dis( );
void insert( );
void del( );
void empty( )
{
if(r<=-1)
{
printf(“\nQueue is empty”);
}
else
{
printf(“\nQueue is full”);
}
}
void full( )
{
if(r>=(max-1))
{
printf(“\nQueue is full”);
}
else
{
printf(“\nQueue is not completely
full”);
}
}
void insert( )
{
Int x,j;
if(r>(max-1))
{
printf(“\nQueue is full”);
}
Else
{
r=r+1;
printf(“\nEnter the element:”);
scanf(“%d”,&q[r]);
}
}
void del( )
{
int t=0;
if(r<=-1)
{
printf(“\nQueue is empty:”);
}
else
{
t=q[f];
if(f!=r)
{
f++;
}
else
{
f=0;
r=-1;
}
}
printf(“\nThe deleted element
is:%d”,t);
}
void dis( )
{
if(r<=-1)
{
printf(“\nQueue is empty”);
}
else
{
int i;
for(i=f;i<=r;i++)
{
printf(“\t%d”,q[i]);
}
}
}
void main()
{
int ch;
clrscr();
do
{
printf(“\n….Queue Operations….”);
printf(“\n1.Insert \t2.Delete \t3.Queue
Full”);
printf(“\t 4.Queue Empty \t5.Display
\t6.Exit”);
printf(“\nEnter your choice:”);
scanf(“%d”, &ch);
switch(ch)
{
case 1: insert();
break;
case 2: del();
break;
case 3: full();
break;
case 4: empty();
break;
case 5: dis();
break;
case 6: break;
default: printf(“\n\n!!!!!Invalid
Option!!!!!”);
}
}while (ch!=6);
getch();
}
Note: program can be written differently depending on the same
logic

8) Define circular queue. Explain insertion and deletion operation on circular queue.(Circular queue definition – 1 Mark, Diagram – 1 Mark, Explanation of insert operation -1Mark, delete operation – 1 Mark)
Ans:
Definition:-A queue, in which the last node is connected back to the first node to form a cycle, is called as circular queue.

circularqueue
Insert operation: (Algorithm or explanation of an algorithm shall be considered)
Step 1: Check for queue full
If rear=max–1 and front=0
or
if front=rear+1
then circular queue is full and insertion operation is not possible.
otherwise go to step 2
Step 2: Check position of rear pointer
If rear=max–1 then set rear=0 otherwise increment rear by 1.
Step 3: Insert element at the position pointer by rear pointer.
Step 4: Check the position of front pointer
If front=–1 then set front as 0.
Delete operation:-(Algorithm or explanation of an algorithm shall be considered)
Step 1: Check for queue empty
if front = -1 then circular queue is empty and deletion operation is not possible.
otherwise
go to step 2
Step 2: check for position of front and rear pointers.
if front = rear then set front=rear=-1
Step 3: check position of front
if front = Max-1 then set front=0;
otherwise
front = front+1
Step 4: Stop

9) Explain the concept of circular queue.( Explanation 3 m and example 1 m)
Ans:
 Circular queue are the queues implemented in circular form rather than in a straight line.
 Circular queues overcome the problem of unutilized space in linear queue implemented as an array.
 The main disadvantage of linear queue using array is that when elements are deleted from the queue, new elements cannot be added in their place in the queue, i.e. the position cannot be reused.
 After rear reaches the last position, i.e. MAX-1 in order to reuse the vacant positions, we can bring rear back to the 0th position, if it is empty, and continue incrementing rear in same manner as earlier.
 Thus rear will have to be incremented circularly.
 For deletion, front will also have to be incremented circularly.
 Rear can be incremented circularly by the following code.
If ((rear == MAX-1) and (front !=0)
Rear =0;
Else
Rear= rear +1;
Example: Assuming that the queue contains three elements.

queue1
Now we insert an element F at the beginning by bringing rear to the first position in the queue. This can be represented circularly as shown.

circularq
In the above example, if another element, G is added to the queue, i.e. rear and front coincide.
But rear and front coincide even when the queue is full is empty.
Thus rear and front cannot be used for both i.e. to check for empty queue as well as the condition for a full queue.
The rear ==front condition is used to check for the empty queue since initially both are initialized to the same value.
Thus to check for queue full condition there are three methods.
1. Use a counter to keep track of the number of elements in the queue.
if this counter reaches to MAX the queue is full.
2. After remove operation rear= front, then set to -1.
After add operation if rear = front then will say that queue is full.
3. By checking (rear + 1) % MAX== front.

10) Explain the concept of the double ended queue. (Explain-3m,Diagram–1 M)
Ans:
1. A double-ended queue or dequeue is an abstract data structure that implements a queue for which elements can only be added to or removed from the front (head) or back (tail).
2. It is also often called a head-tail linked list.
3. Dequeue is a special type of data structure in which insertions and deletions will be done either at the front end or at the rear end of the queue.
4. The operations that can be performed on dequeues are
a. Insert an item from front end
b. Insert an item from rear end
c. Delete an item from front end
d. Delete an item from rear end
e. Display the contents of queue

doubleendedqueue

11) Describe priority queue and list its advantages.
(Description -2Marks, any two advantages- 2Marks)
[Note: array representation or linked representation shall be considered]
Ans:

Description:- A priority Queue is a collection of elements where each element is assigned a priority and the order in which elements are deleted and processed is determined from the following rules:
1) An element of higher priority is processed before any element of lower priority.
2) Two elements with the same priority are processed according to the order in which they are added to the queue.
Advantages:-
 Preferences to the higher priority process are added at the beginning.
 Keep the list sorted in increasing order.

12) Describe priority queue with an example?( Explanation 2M, example 2M)
Ans:
A priority queue is a queue in which the intrinsic ordering among the elements decides the result of its basic operations i.e. the ordering among the elements decides the manner in which Add and Delete operations will be performed.
In a priority queue,
1) Each element is assigning a priority.
2) The elements are processed according to, higher priority element is processed before lower priority element and two elements of same priority are processed according to the order of insertion.
(Represent either with array or linked list)
Array representation: Array element of priority queue has a structure with data, priority and order. Priority queue with 5 elements:

C,1,4 B,3,2 B,3,5 A,4,1 D,5,3

Linked representation:

linkedlist
Above figure shows priority.
Queue with 5 elements where B & C have same priority number.
Each node in above priority queue contains three items.
i. Information field INFO
ii. A priority number PR No
iii. Link Next
An example where priority queue are used is in operating systems.
The operating system has to handle a large number of jobs.
These jobs have to be properly scheduled.
The operating system assigns priorities to each type of job.
The jobs are placed in a queue and the job with the highest priority will be executed first.

13) Consider the following queue of characters where QUEUE is a circular array which is allocated six memory cells.
FRONT=2, REAR=4, QUEUE=__,A,C,D,__,__
Describe queue as the following operations takes place.
i) F is added to queue ii) two letters are deleted
iii) k,l,m are added to queue iv) two letters are deleted
v) R is added to queue vi) Two letters are deleted
vii) S is added to queue viii) one letter is deleted
ix) one letter is deleted
Ans:-

SR.NO. OPERATIONS QUEUE REAR FRONT
 1  Initially  -,A,C,D,-,-   4  2
 2  F Is Added   -,A,C,D,F,-   5  2
 3  Two letters are deleted  -,-,-,D,F,-   5  4
 4  K,L,M are added   L,M,-,D,F,K   2 4
 5  Two letters are deleted   L,M,-,-,-,K  2  6
 6  R is added  L,M,R,-,-,K   3  6
 7  Two letters are deleted  -,M,R,-,-,-  3   2
 8   S is added  -,M,R,S,-,-   4   2
 9  One letter is deleted   -,-,R,S,-,-  4  3
 10  One letter is deleted   -,-,-,S,-,-,  4  4

14) State any two applications of Queue.( 1 advantage 1M)
Ans:
1) Scheduling of processes (Round Robin Algorithm)
2) Spooling (to maintain a queue of jobs to be printed)
3) A queue of client processes waiting to receive the service from the server process
4) Queue is used in breadth first traversal of tree and graph structure
5) Simulation of a real life problem for understanding the behaviour.

15) Describe priority queue with an example? Explain its type.
( Explanation 1 mark, example 1 mark , type explanation 1 mark each)
Ans:
 A priority queue is a queue in which the intrinsic ordering among the elements decides the result of its basic operations i.e. the ordering among the elements decides the manner in which Add and Delete operations will be performed.
 In a priority queue,
 Each element has a priority.
 The elements are processed according to, higher priority element is processed before lower priority element and two elements of same priority are processed according to the order of insertion.
 An example where priority queue are used is in operating systems.
 The operating system has to handle a large number of jobs.
 These jobs have to be properly scheduled.
 The operating system assigns priorities to each type of job.
 The jobs are placed in a queue and the job with the highest priority will be executed first.
Types of priority queues:
1) Ascending priority queue:
This is a priority queue in which elements can be inserted in any
order i.e. arbitrarily, but only the smallest element can be removed.
This means that the element having smallest value has highest
priority.
2) Descending priority queue:
This is priority queue in which elements can be inserted in any
order i.e. arbitrarily, but only the largest element can be removed.
This means that the element having largest value in the queue has
highest priority.

16) Write an algorithm to insert and delete an element from queue.
(2 marks-insertion & 2 marks-deletion)
Ans:
Insert procedure:
1. Check queue full i.e. check rear position.
If it is full then display message and return to calling function.
Otherwise go to step 2.
2. Increment Rear by 1.
3. Insert element with rear pointer.
4. Check position of front.
If inserted element is first element then set front to 0.
5. Return to calling function
Delete procedure:
1. Checks for queue empty i.e. check front position.
If it is empty then display message and return to calling function.
Otherwise go to step 2.
2. Copy data of front into variable.
3. Check front and rear positions.
If front and rear both are equal then show queue empty
otherwise increment front by one.
4. Return to calling function

2 thoughts on “DS Unit 4 Notes

Leave a Reply

Your email address will not be published. Required fields are marked *