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
   506   507   508   509   510   511   512   513   514   515   516