Circular Queue Using Array in C

Queue is of diferent type (simple, circular, priority etc) and can be implemented using different data structures  (i.e. array, linked list etc). But in this lecture will  implements Circular Queue using array in C using dynamic memory allocation. Let’s break it down into its components.

First look at circular queue behaviors through the following diagram
Circular Queue in Data Structure

Global Variables

  1. int *queue: A pointer for dynamically allocated memory for the queue.
  2. int front, rear: Indices to track the front and rear of the queue. Both are initialized to -1, indicating the queue is initially empty.
  3. int Size: Maximum size of the queue, entered by the user at runtime.

Functions 

1. void Enqueue(int element)

  • Purpose: Adds an element to the rear of the queue.
  • Logic:
    • Check if the queue is full: if ((rear + 1) % Size== front).
    • If front == -1, it means the queue is empty, so set front = 0.
    • Increment rear circularly using (rear + 1) % Sizeand assign the value element to queue[rear].
  • Output: Prints confirmation of enqueue or “Queue Overflow” if full.

2. int Dequeue()

  • Purpose: Removes and returns the element at the front of the queue.
  • Logic:
    • Check if the queue is empty: if (front == -1).
    • Retrieve the front element (queue[front]).
    • If front == rear, the queue has only one element; reset front and rear to -1 (empty queue).
    • Otherwise, increment front circularly using (front + 1) % Size.
  • Output: Returns the dequeued element or -1 if the queue is empty.

3. int Peek()

  • Purpose: Returns the front element without removing it.
  • Logic:
    • Check if the queue is empty (front == -1).
    • Return the front element (queue[front]).
  • Output: Prints the front element or “Queue is Empty” if the queue is empty.

4. int IsEmpty()

Purpose: Checks if the queue is empty.

  • Initially, both front and rear are set to -1 when the queue is empty.
  • After all elements are dequeued, if front equals rear, the queue is again empty.

5. int IsFull()

Checks if the queue is full. When (rear + 1) % Size== front: This means the next position of rear coincides with front, leaving no space for new elements.

6. void DisplayQueue()

  • Purpose: Displays all elements in the queue in order.
  • Logic:
    • Check if the queue is empty (front == -1).
    • Loop from front to rear, using (i + 1) % Sizefor circular indexing.
  • Output: Prints all elements or “Queue is Empty” if the queue is empty.

7. main() Function

  • Input Maximum Size:
    • Prompts the user to enter the maximum size of the queue (Size).
    • Dynamically allocates memory for the queue using malloc.
  • Menu-Driven Interface:
    • Repeatedly displays a menu with options for various queue operations until the user selects Exit.
    • Menu Options:
      • 1. Enqueue: Calls Enqueue() to add an element to the queue.
      • 2. Dequeue: Calls Dequeue() to remove and print the front element.
      • 3. Peek: Calls Peek() to display the front element without removing it.
      • 4. Check if Empty: Calls IsEmpty() and prints Yes or No.
      • 5. Check if Full: Calls IsFull() and prints Yes or No.
      • 6. Display Queue: Calls DisplayQueue() to print all elements in the queue.
      • 7. Exit: Breaks the loop to terminate the program.
    • Validates user input and handles invalid choices.
  • Free Memory:
    • Frees the dynamically allocated memory (queue) before exiting.

Here is the Code in C programming to implement the circular queue using an array.

#include <stdio.h>
#include <stdlib.h>int *queue;
int front = -1;
int rear = -1;
int Size;void Enqueue(int element) {
if ((rear + 1) % Size== front) {
printf(“Queue Overflow\n”);
return;
}
if (front == -1) {
front = 0;
}
rear = (rear + 1) % Size;
queue[rear] = element;
printf(“Enqueued %d\n”, element);
}int Dequeue() {
if (front == -1) {
printf(“Queue Underflow\n”);
return -1; // Error code
}
int element = queue[front];
if (front == rear) {
front = rear = -1; // Queue becomes empty
} else {
front = (front + 1) % Size;
}
return element;
}

int Peek() {
if (front == -1) {
printf(“Queue is Empty\n”);
return -1; // Error code
}
return queue[front];
}

int IsEmpty() {
return (front == -1);
}

int IsFull() {
return ((rear + 1) % Size== front);
}

void DisplayQueue() {
if (front == -1) {
printf(“Queue is Empty\n”);
return;
}
printf(“Queue elements: “);
int i = front;
while (1) {
printf(“%d “, queue[i]);
if (i == rear) {
break;
}
i = (i + 1) % Size;
}
printf(“\n”);
}

int main() {
printf(“Enter the maximum size of the queue: “);
scanf(“%d”, &Size);

// Dynamically allocate memory for the queue
queue = (int *)malloc(Size* sizeof(int));

int choice, element;
do {
printf(“\nMain Menu:\n”);
printf(” 1. Enqueue\n”);
printf(” 2. Dequeue\n”);
printf(” 3. Peek\n”);
printf(” 4. Check if Empty\n”);
printf(” 5. Check if Full\n”);
printf(” 6. Display Queue\n”);
printf(” 7. Exit\n”);
printf(“Enter your choice: “);
scanf(“%d”, &choice);

switch (choice) {
case 1:
printf(“Enter element to enqueue: “);
scanf(“%d”, &element);
Enqueue(element);
break;
case 2:
element = Dequeue();
if (element != -1) {
printf(“Dequeued element: %d\n”, element);
}
break;
case 3:
element = Peek();
if (element != -1) {
printf(“Front element: %d\n”, element);
}
break;
case 4:
printf(“Is queue empty? %s\n”, IsEmpty() ? “Yes” : “No”);
break;
case 5:
printf(“Is queue full? %s\n”, IsFull() ? “Yes” : “No”);
break;
case 6:
DisplayQueue();
break;
case 7:
printf(“Exiting…\n”);
break;
default:
printf(“Invalid choice!\n”);
}
} while (choice != 7);

// Free the dynamically allocated memory
free(queue);

return 0;
}

Output:

Enter the maximum size of the queue: 10

Main Menu:
1. Enqueue
2. Dequeue
3. Peek
4. Check if Empty
5. Check if Full
6. Display Queue
7. Exit
Enter your choice: 6
Queue is Empty

Main Menu:
1. Enqueue
2. Dequeue
3. Peek
4. Check if Empty
5. Check if Full
6. Display Queue
7. Exit
Enter your choice: