Linear Data Structure 489
Fig. 14.12 shows that insertion is done at the rear end and deletion at the front end.
p
Q
R
S
(a)
Front
Q R
Rear
(b)
Q R
(c)
Fig. 14.13 Queues
Fig. 14.13 illustrates queue containing elements. Queue (a) contains four elements P, Q, R and S.
The element P is at the front end and element S is at the rear end. In (b), element P has been deleted
from the queue. The element Q is now the first element and now it is in the front. In (c) elements S
and T are inserted. The elements are inserted from the rear end of queue. The element S is inserted
before T. As far as removal operation is concerned, S is to be removed before T.
Frequently two operations are carried on a queue. They are insertion and deletion of elements.
These two operations depend upon the status of the queue. The insertion operation is possible only
when the queue contains elements less than the capacity it can hold. The delete operation is only
possible when the queue contains at least one element. The queue containing no elements is called
underflow as shown in Fig. 14.14.
Fig. 14.14 Empty queue (underflow)
14.16 VARIOUS POSITIONS OF QUEUE
Consider the following figures.
rear = -1
front = -1
(a) Empty queue
490 Programming and Data Structures
In Fig. 14.15 (a) the above queue is empty, hence the value of rear = -1 and front = -1. The above
queue is called an empty queue. The status of the queue initially always remains empty
rear = 0
front = 0
(b)
In Fig. 14.15(b), the queue holds one element. The value of rear=0 and front=0. Both front and rear
end are on same element because the queue contains only one element. The next element appended
will be stored followed by 5. Just then, the front will remain at 5 but rear will be shifted on the new
element. The value of front is changed only once while inserting first element in the queue. Later for
every insertion of element, the front remains the same.
5 3
front = 0
rear = 1
0
1 2 3
4
5
(c)
As per Fig. 14.15(c), an element is inserted from the rear side and it is stored behind five. Whenever
we insert an element in the queue the value of rear is incremented, that is, the rear end is shifted
towards the right side. At this step the value of front =0 and rear=l.
5 3 2
front = 0
rear = 1
0
1 2 3 4 5
(d)
Fig. 14.15(d), the value of rear is 2.
front = 1
rear = 2
0 1 2 3 4 5
(e)
Fig. 14.15 Various positions of queue
In Fig. 14.15 (e), one element is deleted from the queue. Now the front is shifted towards bottom.
Thus, the front will be on element 3 now. The value of front will be increased when an element is
removed. The value of front=l and rear = 2. The programs on the above discussion are explained in
queue implementation.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.