Page 146 - DCAP407_DATA_STRUCTURE

Unit 8: Queues

incremented and the value entered by the user (num) is assigned to Q.
The value of R is returned. The second if loop checks if the F pointer is
not equal to 0. If the result is true, then the F pointer is decremented and
the value entered by the user (num) is assigned to Q. The value of F is
returned. Else, the program prints the message “front insertion not
possible”
5. When the user enters 2, rear_delete() function is called. In the
rear_delete() function the if loop calls the Q_E() function with the
current pointer values of F and R. If the condition is true, the program
prints the message “Queue underflow”. It returns the value of F and R.
The program prints the deleted element.
6. When the user enters 3, the function display() is called. In the function
display() the if loop checks for the queue size. If the queue is not empty
the program displays the elements.
7. When the user enters 4, the program terminates.

Write an algorithm to perform insertion of an element at the rear end and deletion of an
element at the front end for a deque.

8.4.2 Circular Queue
In a circular queue, the rear end is connected to the front end forming a circular loop. An advantage of
circular queue is that, the insertion and deletion operations are independent of one another. This
prevents an interrupt handler from performing an insertion operation at the same time when the main
function is performing a deletion operation. The figure 8.5 depicts a circular queue. The queue elements
are stored in an array. The front end of the queue is represented as F and the rear end is represented as
R. Before inserting an element into the queue, the R pointer should be set to -1. The value of R is then
incremented to insert the elements. In the first figure of figure 8.5, only one element (20) is present in the
queue. Hence, the value of F and R pointer will be 0. In the second figure of figure 8.5, two elements are
added (40 and 60) to the queue. This can be done by incrementing the R pointer. The following
statement depicts the increment operation:
R=(R+1) % SIZE
Here,
SIZE is the queue size. In this case, the size is 5.

LOVELY PROFESSIONAL UNIVERSITY 139