Circular Queue / Ring Buffer / Circular Buffer

Reading time: 25 minutes | Coding time: 10 minutes

Definition

Circular Queue is also a linear data structure, which follows the principle of FIFO(First In First Out), but instead of ending the queue at the last position, it again starts from the first position after the last, hence making the queue behave like a circular data structure.It is also called ‘Ring Buffer’.

Circular Queue can be implemented using:

• Array
• Linked List

Basic Operations

INTIALIZATION

SIZE  = VALUE     // Size of Queue
ARRAY [SIZE]      // Array of Queue
FRONT = -1        // Initializing Front Pointer to -1
REAR  = -1        // Initializing Rear Pointer to -1   

Operation in Circular Queue are:

1. Front() : Function to get Front element of Circular Queue.

Front():
    IF FRONT != -1 :
        PRINT ARRAY[FRONT] // If FRONT !=-1 i.e. no. of elements != 0 then print the element at FRONT
    ELSE :
        PRINT "NO ELEMENTS IN QUEUE" // If circular queue is empty.

2. Rear() : Function to get Rear element of Circular Queue.

    Rear():
        IF REAR != -1 :
            PRINT ARRAY[REAR] // If REAR !=-1 i.e. no. of elements != 0 then print the element at REAR
        ELSE :
            PRINT "NO ELEMENTS IN QUEUE" // If circular queue is empty.

3. EnQueue(value) : Function to insert value at Rear position in Circular Queue.

EnQueue(value):
    IF (REAR+1)%SIZE == FRONT :   // If circular queue is full. 
        PRINT "QUEUE IS FULL"          
    ELSE IF FRONT == -1 :         // If circular queue is empty.
        FRONT = 0 
        REAR = 0
        ARRAY[REAR] = value
    ELSE :                     
        REAR = REAR + 1
        ARRAY[REAR] = value

4. DeQueue() : Function to remove element at Front position in Circular Queue.

DeQueue():
    IF FRONT == -1  :             // If circular queue is empty. 
        PRINT "QUEUE IS EMPTY"          
    ELSE IF FRONT == REAR :         // If circular queue has only one element
        TEMP = ARRAY[FRONT]
        FRONT = -1
        REAR = -1
        RETURN TEMP
    ELSE : 
        TEMP = ARRAY[FRONT]
        FRONT = (FRONT + 1)%SIZE
        RETURN TEMP

5. Size() : Function to display size of Circular Queue.

Size():
    IF FRONT == -1  :             // If circular queue is empty. 
        PRINT "QUEUE IS EMPTY"          
    ELSE IF FRONT == REAR :       // If circular queue has only one element.
        RETURN 1
    ELSE IF (REAR < FRONT):
        RETURN (REAR + (SIZE - FRONT + 1))                   
    ELSE :         
        RETURN (REAR - FRONT + 1)

6. Display() : Function to display all elements in Circular Queue.

    Display():
        IF FRONT == -1  :             // If circular queue is empty. 
            PRINT "QUEUE IS EMPTY"          
        ELSE IF FRONT == REAR :       // If circular queue has only one element.
            PRINT ARRAY[FRONT]
        ELSE IF (REAR < FRONT):
           FOR I IN RANGE(FRONT,SIZE):
               PRINT ARRAY[I] 
           FOR I IN RANGE(0,REAR):
               PRINT ARRAY[I]
        ELSE :
           FOR I IN RANGE(FRONT,REAR):
               PRINT ARRAY[I]

Complexity

• Time complexity of EnQueue(), DeQueue() operation is O(1) as there is no loop in any of the operation.
• Space complexity is O(n) where n is number of elements.

Implementation

front = rear = -1     # global declaration of front and rear pointer
circular_queue = []   # Initializaiton of Circular Queue
size = int(input("Enter the Size of Circular Queue : "))

def init(size):
  # initializing circular queue with none
  return [None for i in range(size)]

def Front():
  global front, rear, circular_queue
  if (front == -1):
    print('Circular Queue is Empty !!')
  else:
    print ("Element at Front : ",circular_queue[front])

def Rear():
  global front, rear, circular_queue
  if (rear == -1):
    print('Circular Queue is Empty !!')
  else:
    print ("Element at Rear : ",circular_queue[rear])


def EnQueue(value):
  global front, rear, circular_queue
  if (front == -1):
    front = 0 
    rear = 0
    circular_queue[rear] = value
  elif ((rear+1)%size == front):
      print("Circular Queue is Full !!")
  else :                     
    # next position of rear 
    rear = (rear + 1)%size
    circular_queue[rear] = value

def DeQueue():
  global front, rear, circular_queue
  if (rear == -1):
    print('Circular Queue is Empty !!')
  elif ( front==rear ):
    print("Element Deleted : ",circular_queue[front])
    front = -1
    rear = -1
  else : 
    print("Element Deleted : ",circular_queue[front])
    front = (front + 1)%size

def Size():
  global front, rear, circular_queue
  if (front == -1):
    print('Circular Queue is Empty !!')
  elif ( front==rear ):
    print('Size of Circular Queue : 1')
  elif (rear<front) :
    print('Size of Circular Queue : ',(rear + (size - front)))
  else :
    print('Size of Circular Queue : ',(rear - front + 1))  

def Display():
  global front, rear, circular_queue
  if (front == -1):
    print('Circular Queue is Empty !!')
  elif (rear == front):
    print("Circular Queue : ",circular_queue[front])
  else :
    if(rear < front):
      print("Circular Queue : ",circular_queue[front:size]+circular_queue[:rear+1])
    else :
      print("Circular Queue : ",circular_queue[front:rear+1])
    if ((rear+1)%size == front):
      print("Circular Queue is Full !!")  



circular_queue =  init(size)
print("After Initialization : ",circular_queue)

EnQueue(69)
EnQueue(75)
EnQueue(73)
EnQueue(67)
EnQueue(44)

Display()

Front()
Rear()
Size() 

Display()

DeQueue()
DeQueue()

Display()
Size() 

EnQueue(30)
EnQueue(51)

Front()
Rear()

Display()

EnQueue(31)
 
  
# This code is contributed by Vedant Wakalkar     

Output

Enter the Size of Circular Queue : 5
After Initialization :  [None, None, None, None, None]

Circular Queue :  [69, 75, 73, 67, 44]
Circular Queue is Full !!

Element at Front :  69
Element at Rear :  44
Size of Circular Queue :  5

Circular Queue :  [69, 75, 73, 67, 44]
Circular Queue is Full !!

Element Deleted :  69
Element Deleted :  75

Circular Queue :  [73, 67, 44]
Size of Circular Queue :  3

Element at Front :  73
Element at Rear :  51

Circular Queue :  [73, 67, 44, 30, 51]
Circular Queue is Full !!

Circular Queue is Full !!

Application

• In CPU scheduling viz Round Robin Scheduling.
• Memory Management : unused memory locations can be utilized using circular queue.
• Computer controlled Traffic Signal System uses circular queue.