Page 522 - Computer science 868 Class 12
P. 522

76              case 5:
                77                    ob.display();

                78                    break;
                79              default:

                80                   System.out.println(" Exit");
                81               }

                82           }while(ch>=1 && ch<=5);
                83           }
                84       }


              13.2.5 Circular Queue
              Circular queue is a special type of queue where the front and rear ends are connected to form a circular structure.
              Circular queue follows the queue principle of FIFO that is First In First Out.
              Like Queue, an element is inserted from the front end and deleted from rear end. But as a circular structure does not
              have a definite front and rear, the drawback of unutilised front space is taken care of in a circular queue.

              Like a linear queue, two operations can be performed on a circular queue. They are as follows:
              1.  Enqueue: Inserting an element in a circular queue is done from the rear end. But the rear pointer changes by rear
                 = (rear+1) % sizeOfCircularQueue.
              2.  Dequeue: Deleting an element from a circular queue is done from the front end. But the front index pointer changes
                 by front = (front+1) % sizeOfCircularQueue.
              Generally, in Circular Queue one cell is kept vacant as a demarcation between front and rear.

              Let us see diagrammatically how a circular queue works. Let us assume that the following the circular queue can store
              maximum 4 elements.
                                                                               rear=3
                           front=0
                     3   0 rear=0      3  17  Insert 17      3  17 0  Insert 23  3 17  Insert 29   3 17  Insert 35
                                                                    front=0
                                                                                      front=0
                                                                                                         front=0
                                             front=0
                    2                 2    0                2   1              2 29  0           2 29  0  rear=0
                        1                1             rear=2  23                23 1               23 1  Queue=full
                                           rear=1
                                                                 front=3     Delete               Delete
                       3     Delete             3     Delete           3   0 rear=0        3   0 Queue empty
                      2    0  rear=0          2    0  rear=0          2                   2
                      29  1                   29   1
                        23                                               1                    1
                           front=1       front=2
              The algorithm to insert an element in a circular queue is given below.

              void enqueue(int qu[] , int max , int val)

              Step 1:  Start.
              Step 2:  Initialise front and rear to 0
              Step 3:  If (rear +1)% max =front then display “Queue Overflow”, go to Step 8

              Step 4:  Assign qu[rear]= val
              Step 5:  Assign rear=(rear+1)%max




                520520  Touchpad Computer Science-XII
   517   518   519   520   521   522   523   524   525   526   527