Linear Queue:
- Linear queue follows “First In First Out” rule.
- We insert elements from Rear and delete from Front.
- In linear queue, “Front” is fixed location.
- When we delete an element from the queue, shifting of elements takes much time.
Circular Queue:
- Solution to Linear Queue data structure is Circular queue.
- In circular queue, we are representing the Linear Queue in circle form.
- We can move front location also after deletion of element from the queue.
- We can move both front and rear locations while inserting and deleting the elements.
- As front value is not fixed, front and rear values starts with -1
Declaration:
- We declare array variable with fixed size.
- Front and Rear variables are used to process the location data.
- Front and Rear variables not pointing to any location initially.
- Front location is not fixed in Circular Queue.
- int cqueue[8];
- int front=-1;
- int rear=-1;
Operations: We can perform following operations on Circular Queue.
- Insertion
- Deletion
- Display
Insertion:
- The following diagrams describe the queue initially.
- Inserting elements from ‘rear’.
- First insertion changes both the values of front and rear variables.
- Continues insertion of elements results “Queue is full”.
Deletion:
- Deleting elements using ‘front’ variable.
- After deletion of element, front value increase by 1.
When we insert the element and it rear value reaches size-1 then rear value again starts from 0.
Queue is Full: Inserting the elements continuously leads to Queue is Full condition
In circular queue, we need to check 2 situations for “Queue is Full” condition.
Deleting elements to make the front pointing to last location of Queue:
Note: While continuously deleting the elements, if it reaches the location “size-1”, it starts with 0 again in the next cycle.
- When front and rear values are equal means Queue has only 1 element.
- When we remove the last element from the queue, then front and read values become -1.
Display(): There are 2 cases to display the elements from the circular queue.
- Case1 : Rear greater than front
- Case2 : Front greater than rear
