Circular Queue using Array

 

What is a Circular Queue?

A Circular Queue is a special form of a queue where:

  • It behaves in a circular fashion.

In a normal (linear) queue, once the rear reaches the last index of the array, we cannot insert even if there are empty spaces at the beginning.
➔ Circular Queue solves this by wrapping around.

Circular Queue Operations


OperationMeaning
enqueue(x)    Insert an element into the queue.
dequeue()    Remove an element from the queue.
peek()    Get the front element without removing it.
isEmpty()    Check if the queue is empty.
isFull()    Check if the queue is full.

Circular Queue Algorithms

✅ Assume:

  • Queue array: queue[MAX]

  • Initially: front = 0, rear = 0

  • A slot is wasted to distinguish full and empty.

Algorithm for isEmpty()

Algorithm isEmpty(front, rear)
1. If front == rear
       Return TRUE
2. Else
       Return FALSE
Meaning:
If front == rear, queue is empty.

Algorithm for isFull()

1. If (rear + 1) mod MAX == front
       Return TRUE
2. Else
       Return FALSE

Meaning:
If the next position of rear is front, the queue is full.

Algorithm for Enqueue (Insert an element)

1. If isFull() then
       Output "Queue Overflow"
       Exit
2. Else
       rear = (rear + 1) mod MAX
       queue[rear] = item
3. End If

Algorithm for Dequeue (Remove an element)


1. If isEmpty() then
       Output "Queue Underflow"
       Exit
2. Else
       front = (front + 1) mod MAX
       item = queue[front]
3. End If
4. Return item

Algorithm for Peek (View Front Element)

1. If isEmpty() then
       Output "Queue is Empty"
       Exit
2. Else
       temp = (front + 1) mod MAX
       Return queue[temp]

🚀 Time Complexity of Circular Queue Operations

OperationTime ComplexityReason
Enqueue (Insert)    O(1)Insert element at rear, just update rear index (with wrap around)
Dequeue (Remove)    O(1)Remove element from front, just update front index (with wrap around)
Front (Peek)    O(1)Access the element at front index
Rear (Peek)    O(1)Access the element at rear index
isEmpty    O(1)Compare front and rear indices or check size
isFull    O(1)Check if queue is full by comparing front and rear


C Program - Circular Queue using array
#include <stdio.h>
#include<stdlib.h>
#include <stdbool.h>
#define MAX 10
// initilazing queue
int cqueue[MAX];
int rear = 0;
int front = 0;
// Function to check if the cqueue is empty
bool isEmpty() {
    return front==rear ;
}

// Function to check if the cqueue is full
bool isFull() {
    return (rear+1)%MAX == front;
}

void enqueue() // enqueue
{
int item;
if (isFull())
  printf("Queue Overflow \n");
else
 {
 printf("\nInset the element in queue : ");
 scanf("%d", &item);
 rear = (rear + 1)%MAX;
 cqueue[rear] = item;
 }
} /*End of insert()*/
void dequeue() //dequeue
{
     if(isEmpty())
     {
       printf("\nQueue Underflow \n");
       return ;
     }
    else
    {
    front = (front + 1) %MAX;
    printf("\nElement deleted from queue is : %d\n", cqueue[front]);
    }
} /*End of delete() */
void display()// print queue
{
int i;
    if (isEmpty() )
        printf("\nQueue is empty \n");
     else
    {  printf("\nQueue is : ");
        
        for (i = (front+1)%MAX; i != (rear+1)%MAX; i=(i+1)%MAX)
            printf("%d ", cqueue[i]);
        
        printf("\n");
        
    }
}
// Function to peek at the front item
int peek() {
    if (isEmpty()) {
        printf("Queue is empty. Nothing to peek.\n");
        return -1; // Error value
    } else {
        return cqueue[front+1];
    }
}

int main()
{
int choice;
while (1)
{
printf("\n1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Peek \n");
printf("5.Quit \n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
    enqueue();
    break;
case 2:
    dequeue();
    break;
case 3:
    display();
    break;
case 4:
    int x=peek();
    if(x!=-1) printf("\nfront element is=%d\n",x);
    break;
case 5:
    exit(1);

default:

printf("\nWrong choice \n");

} /*End of switch*/

} /*End of while*/
return 0;
} /*End of main()*/


An alternate implementation without wasting a slot
C Program Implementation- Circular Queue
#include <stdio.h>
#include<stdlib.h>
#include <stdbool.h>
#define MAX 10
// initilazing queue
int cqueue[MAX];
int rear = - 1;
int front = -1;
// Function to check if the cqueue is empty
bool isEmpty() {
    return front==-1 ;
}

// Function to check if the cqueue is full
bool isFull() {
    return (rear+1)%MAX == front;
}

void insert() // enqueue
{
int item;
if (isFull())
  printf("Queue Overflow \n");
else
 {
 printf("\nInset the element in queue : ");
 scanf("%d", &item);
    if(isEmpty())
       front=rear=0;
    else
      rear = (rear + 1)%MAX;
 cqueue[rear] = item;
 }
} /*End of insert()*/
void delete() //dequeue
{
     if(isEmpty())
     {
       printf("\nQueue Underflow \n");
       return ;
     }
     printf("\nElement deleted from queue is : %d\n", cqueue[front]);
    
if ( rear == front )
    {
    front=rear=-1;//make it empty
    }
    else
    {
    front = (front + 1) %MAX;
    }
} /*End of delete() */
void display()// print queue
{
int i;
    if (isEmpty() )
        printf("\nQueue is empty \n");
     else
    {  printf("\nQueue is : ");
        if(front==rear)
            printf("%d\n", cqueue[front]);
        else
        {
        for (i = front; i != rear; i=(i+1)%MAX)
            printf("%d ", cqueue[i]);
        
        printf("%d ", cqueue[i]); //print the element at rear
        printf("\n");
        }
    }
}
// Function to peek at the front item
int peek() {
    if (isEmpty()) {
        printf("Queue is empty. Nothing to peek.\n");
        return -1; // Error value
    } else {
        return cqueue[front];
    }
}
// Function to get the size of the queue
int size() {
    if (isEmpty()) {
        return 0;
    } else {
        if (rear >= front ) return rear - front + 1;
        else return MAX-front+rear-0+1;
    }
}
int main()
{
int choice;
while (1)
{
printf("\n1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Peek \n");
printf("5.Size of the queue\n");
printf("6.Quit \n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
    insert();
    break;
case 2:
    delete();
    break;
case 3:
    display();
    break;
case 4:
    int x=peek();
    if(x!=-1) printf("\nfront element is=%d\n",x);
    break;
case 5:
    printf("\nsize of the queue is =%d\n",size());
    break;
case 6:
    exit(1);

default:

printf("\nWrong choice \n");

} /*End of switch*/

} /*End of while*/
return 0;
} /*End of main()*/

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more