Page 511 - Computer science 868 Class 12
P. 511
13.2 QUEUE
The literary meaning of Queue is “a line or a sequence of people or vehicles awaiting their turn to be attended to or to
proceed”. If we want to join the line, we have to stand at the last. The person standing in the front will be the first to
leave the line. In computing terminology, the operation of queue is also similar.
A queue is a linear data structure which works on FIFO principle, i.e., First In First Out. It has two ends namely the front
and the rear. Insertion in a queue takes place at the rear end and deletion from the front end.
13.2.1 Basic Operations on Queue
The following operations can be performed on a queue array.
1. Insertion: The technique to store an item in a queue is called Insertion or Push. An element in queue is always
entered from the rear end. So, the rear end pointer increases by 1 while the front end pointer remains unchanged.
If the rear index becomes equal to the size of the array then further attempt to insert any item results in an error
situation called “Queue Overflow”. First cell of the queue is kept vacant.
2. Deletion: The process to remove an element from a queue is called Deletion or Pop. An item in queue is always from
the front end. During deletion, the front index increases by 1 while the rear index retains its current value. When the
front index becomes equal to the rear index, then the Queue becomes empty and the situation is termed as “Queue
Underflow”.
Let us show the operations in Queue with an example. Let us assume that an integer array qu[] of size 4 is defined in
memory. Also the front and rear pointers are initialised to 0.
Operation Queue content
Step 1: 17 is inserted in queue
17
front = 0 rear = 1
Step 2: 23 is inserted in queue
17 23
front = 0 rear = 2
Step 3: Next item inserted is 28
17 23 28
front = 0 rear = 3
Step 4: Rear = size-1. Is we try to insert another
number say 46 Queue overflow condition 17 23 28
is reached
front = 0 rear = 3
The deletion operation is similarly illustrated below.
Operation Queue content
Step 1: 17 deleted from queue
17 23 28
front = 1 rear = 3
509
Data Structures 509

