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
Global Variables
int *queue
: A pointer for dynamically allocated memory for the queue.int front, rear
: Indices to track the front and rear of the queue. Both are initialized to-1
, indicating the queue is initially empty.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 setfront = 0
. - Increment
rear
circularly using(rear + 1) % Size
and assign the valueelement
toqueue[rear]
.
- Check if the queue is full:
- 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; resetfront
andrear
to-1
(empty queue). - Otherwise, increment
front
circularly using(front + 1) % Size
.
- Check if the queue is empty:
- 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]
).
- Check if the queue is empty (
- 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
andrear
are set to-1
when the queue is empty. - After all elements are dequeued, if
front
equalsrear
, 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
torear
, using(i + 1) % Size
for circular indexing.
- Check if the queue is empty (
- 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
.
- Prompts the user to enter the maximum size of the queue (
- 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 printsYes
orNo
. - 5. Check if Full: Calls
IsFull()
and printsYes
orNo
. - 6. Display Queue: Calls
DisplayQueue()
to print all elements in the queue. - 7. Exit: Breaks the loop to terminate the program.
- 1. Enqueue: Calls
- Validates user input and handles invalid choices.
- Free Memory:
- Frees the dynamically allocated memory (
queue
) before exiting.
- Frees the dynamically allocated memory (
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() { int IsEmpty() { int IsFull() { void DisplayQueue() { int main() { // Dynamically allocate memory for the queue int choice, element; switch (choice) { // Free the dynamically allocated memory 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: