Circular Queue Implementation

Overview

• Discussing the concept of circular queues and their implementation using arrays.
• Previously covered linear queues using arrays and linked lists.
• Major drawback of linear queues leads to the introduction of circular queues.

Key Concepts

Definition of Queue

• Follows FIFO (First In, First Out) principle.
• Insertion occurs at the rear end.
• Deletion occurs from the front end.
• Both operations have a time complexity of O(1).

Drawback of Linear Queue

• Fixed size leads to wasted space when elements are dequeued.
• Example: If a queue of size 5 is filled and then elements are dequeued, the space cannot be reused until all elements are dequeued.
• Condition for a full queue in linear implementation:
  • front is at position 0 and rear at position (size - 1).

Circular Queue Concept

• Circular queues allow reuse of empty spaces created by dequeued elements.
• Conditions for full queue need to be modified:
  • Full Condition: (rear + 1) % n == front

Implementation Steps

Initial Setup

• Both front and rear start at -1 to indicate an empty queue.

NQ (Enqueue) Operation

1. Check if Queue is Empty:
   • If front and rear are both -1, set both to 0.
2. Check if Queue is Full:
   • Use modified condition: (rear + 1) % n == front
3. Insert Element:
   • Update rear using (rear + 1) % n.
   • Place the element in the queue at position rear.

DQ (Dequeue) Operation

1. Check if Queue is Empty:
   • Both front and rear being -1 indicates an empty queue.
2. Check for Single Element:
   • If front equals rear, reset both to -1 after dequeuing the element.
3. Dequeue Element:
   • Print the dequeued element from position front.
   • Update front using (front + 1) % n.

Display Functionality

• Loop through the queue using a while loop until i equals rear, and print elements.
• Use modulo arithmetic to ensure circular traversal.
• At the end of the loop, print the element at rear to ensure all elements are displayed.

Peek Operation

• Return the element at the front of the queue without removing it.
• Check if the queue is empty first.

Next Lecture

• Next topic will cover implementation of queues using stacks.