Topic: Circular Queues and DEQueue

Difficulty: Easy

Year(Marks): Dec2016(10 mks),May2018(10 mks)

1. Circular Queue
   1. In an Queue when elements are arranged in sequential manner but logically we assume it in circular format, then such queue is called as “Circular Queue”.
   2. It follows “First In First Out” method for insertion and deletion of elements.
   3. Liner Queue may appear to be full although there may be space in the queue, this problem is overcome due to circular nature of circular queue.
   4. A variable named “FRONT” stores position of the starting element of the queue. Its incremented on deletion of an element.
   5. A variable named “REAR” stores position of the last element of the queue. Its incremented on Insertion of new element.
   6. Example
      
   7. In the above example, if another element, G is added to the queue, i.e. rear and front coincide. 8.To check Queue is Full or Not following condition is used front == (rear+1)%SIZE, if the condition is true then the Queue is full or else not full.
   8. To check Queue is Empty or Not following condition is used rear == front, if the condition is true then the Queue is Empty or else not empty
2. Double Ended Queue
   1. A Queue in which inserting and deleting of elements is done from both the ends, such queue is called as Double Ended Queue(DeQueue).
   2. Consider the following
   3. Dequeue always consists of homogeneous list of elements.
   4. There are two types of DeQueue. A. Input restricted dequeues B. Output restricted dequeues
   5. Following are the types of DEQueue
   6. Input restricted dequeues allows insertion only at one end but allows deletion of element from both the ends.
   7. Output restricted dequeues allwos deletions of elements only at one end but allows insertion of element from both the ends.