Circular Queue

CIRCULAR-QUEUE

  What is a Circular Queue ?

 It is same like a queue with same FIFO operations .It is like the luggage belt on airport where the bags are there n the user picks the bag and the place becomes vacant .
Note:-Also always remember in queue's element is deleted from front and inserted at the end 

 

(Example of a conveyer belt at airport)

(Example of a circular queue)

ENQUEUE operation on the circular queue

In order to insert a element in a circular queue we need to check if the queue is full or not in order to do so we check if rear pointer has reached the DEFAULT_CAPACITY of our array and if front is at 0th element or front is at rear+1 position,we print "Queue is Full"

(front==0 && rear<DEFAULT_CAPACITY-1)
OR
front=rear+1

Now check if the rear is at the last element,if so set rear to first and insert

rear==0;

arr[rear]=data;

if not then we just insert an element in the array by

arr[++rear]=data

Also if in any case front =-1 i.e. initial state we need to set it to front=0 to get the front pointer at first position

DEQUEUE operation from the circular queue

In order to delete a element from a queue we need to check if the queue is empty or no.

In order to do so we check if our counters are at front=-1 and rear=-1 position that means initial position(Note:- here initial does not mean first element)so we print "Queue is Empty"

i.e.

front==-1 && rear==-1

If front and rear is at same position delete the element and make front go back one position as the element is deleted from front.

Now if front is at the last element point it to the first position after deletion i.e. front is set to 0 (front=0)

For normal scenario just delete the element and increase the front by 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114

/* * Circular queue using a array * @ Author Karan Deep Singh * */ public class CircularQueue { private static int DEFAULT_CAPACITY = 5; static int arr[]; static int front; static int rear; public CircularQueue() { arr = new int[DEFAULT_CAPACITY]; front = -1; rear = -1; } /* * Insertion :- * inserting an element - * 1. check if queue is full * 2. check if rear is at last element set rear to first and insert else just insert at position * 3. if front comes to be -1 reset it to 0 */ private void enqueue(int data) { if (isFull()) { System.out.println("queue is full"); return; } if (rear == DEFAULT_CAPACITY - 1) { rear = 0; arr[rear] = data; } else arr[++rear] = data; if (front == -1) front = 0; } /* * Deletion :- * 1. Check if queue is empty * 2. if front and rear are same position delete and make front go back one position as element is deleted from front * 3. if front is at last element point it to first position after deletion * 4. or just delete the element at given position and increment front * */ private void dequeue() throws Exception { if (isEmpty()) { System.out.println("queue is empty"); return; } if (front == rear) { System.out.println(arr[front]); front = rear = -1; } else if (front == DEFAULT_CAPACITY - 1) { System.out.println(arr[front]); front = 0; } else System.out.println(arr[front++]); } public static void main(String[] args) throws Exception { CircularQueue queue = new CircularQueue(); queue.enqueue(10); queue.enqueue(12); queue.enqueue(13); queue.enqueue(14); queue.enqueue(15); queue.dequeue(); queue.dequeue(); queue.enqueue(16); queue.enqueue(17); queue.enqueue(18); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.enqueue(19); queue.enqueue(20); queue.enqueue(21); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); } // check if queue is empty i.e. front and rear pointers are back to initial // state -1 boolean isEmpty() { if (rear == -1 && front == -1) return true; return false; } // check if queue is full i.e. front came back to 0th element and rear is at // last element or front is equal to rear+1 boolean isFull() { if ((front == 0 && rear == DEFAULT_CAPACITY - 1) || front == rear + 1) return true; return false; } }