Write a C program to implement queue, enqueue and dequeue operations using array. In this post I will explain queue implementation using array in C programming. We will learn how to implement queue data structure using array in C language. And later we will learn to implement basic queue operations enqueue and dequeue.
Required knowledge
While loop, Switch case, Array, Functions, Queue
What is queue?
Queue is a linear data structure where elements are ordered in special fashion i.e. FIFO (First In First Out). Which means element inserted first to the queue will be removed first from the queue.
In real life you have come across various queue examples. Such as queue of persons at ticket counter, where the first person entering queue gets ticket first.
Operations performed on queue
In this post I will explain queue implementation using array in C language. I will explain the logic behind basic operations performed on queue.
There are two basic operations that we generally perform on queue.
How to create queue data structure using array
Example:
int queue[CAPACITY];The above statement creates a queue, where CAPACITY is constant defining max capacity of the queue. Along with the queue definition we need few other variables to perform operations on queue.
unsigned int size = 0;
unsigned int rear = CAPACITY - 1;
unsigned int front = 0;Where,
- size will keep track of the size of queue. Initially queue size is 0.
- rear will keep track of the rear array index. The insertion point of the queue. Initially it is indexed to last element of queue. To facilitate first enqueue at zeroth index of array (see enqueue).
- front keep track of index from where elements are removed.
Note: I have declared these fields as unsigned. Since these values will never go in negative.
Read more about unsigned int data type in C.
How to enqueue an element to queue?
Enqueue is the process of inserting an element to queue. In queue elements are always inserted at rear of queue.
Step by step descriptive logic to enqueue an element to queue.
- Verify queue overflow and throw error if queue overflow happens, otherwise move to next step. You can use
if (size >= CAPACITY)to verify queue overflow. - Increment rear size by 1. Note, that the increment should not cross array index bounds.
Which means if suppose queue capacity is 100 and size is 10 and rear is at 99 which means front will be at 89. Now when you enqueue a new element to queue, rear must get updated to 0 instead of 100. Otherwise array index will go beyond its bounds.
To do so we use
rear = (rear + 1) % CAPACITY;. - Increment size of the queue by 1.
- Insert new element at the rear of queue i.e.
queue[rear] = data;.
How to dequeue an element from queue?
Dequeue is the process of removing an element from queue. Elements from queue are always removed from front of queue.
Step by step descriptive logic to dequeue element from queue.
- Check queue underflow and throw error if queue is empty, otherwise move to next step. You can use size to check empty queue i.e.
if (size <= 0). - Copy current element at front of queue to some temporary variable. Say
data = queue[front]; - Increment front by 1. Similar to enqueue, the increment should not cross array index bounds.
Which means if suppose queue capacity is 100 and size is 10 and rear is at 9 which means front will be at 99. Now when you dequeue element from queue, front must get updated to 0 instead of 100. Otherwise array index will go beyond its bounds.
To do so we use
front = (front + 1) % CAPACITY;. - Decrement queue size by 1.
datais required element dequeued from queue.
Program to implement queue using array
/**
* Queue implementation using array.
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Queue capacity
#define CAPACITY 100
/**
* Global queue declaration.
*/
int queue[CAPACITY];
unsigned int size = 0;
unsigned int rear = CAPACITY - 1; // Initally assumed that rear is at end
unsigned int front = 0;
/* Function declaration for various operations on queue */
int enqueue(int data);
int dequeue();
int isFull();
int isEmpty();
int getRear();
int getFront();
/* Driver function */
int main()
{
int ch, data;
/* Run indefinitely until user manually terminates */
while (1)
{
/* Queue menu */
printf("--------------------------------------\n");
printf(" QUEUE ARRAY IMPLEMENTATION PROGRAM \n");
printf("--------------------------------------\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Size\n");
printf("4. Get Rear\n");
printf("5. Get Front\n");
printf("0. Exit\n");
printf("--------------------------------------\n");
printf("Select an option: ");
scanf("%d", &ch);
/* Menu control switch */
switch (ch)
{
case 1:
printf("\nEnter data to enqueue: ");
scanf("%d", &data);
// Enqueue function returns 1 on success
// otherwise 0
if (enqueue(data))
printf("Element added to queue.");
else
printf("Queue is full.");
break;
case 2:
data = dequeue();
// on success dequeue returns element removed
// otherwise returns INT_MIN
if (data == INT_MIN)
printf("Queue is empty.");
else
printf("Data => %d", data);
break;
case 3:
// isEmpty() function returns 1 if queue is emtpy
// otherwise returns 0
if (isEmpty())
printf("Queue is empty.");
else
printf("Queue size => %d", size);
break;
case 4:
if (isEmpty())
printf("Queue is empty.");
else
printf("Rear => %d", getRear());
break;
case 5:
if (isEmpty())
printf("Queue is empty.");
else
printf("Front => %d", getFront());
break;
case 0:
printf("Exiting from app.\n");
exit(0);
default:
printf("Invalid choice, please input number between (0-5).");
break;
}
printf("\n\n");
}
}
/**
* Enqueue/Insert an element to the queue.
*/
int enqueue(int data)
{
// Queue is full throw Queue out of capacity error.
if (isFull())
{
return 0;
}
// Ensure rear never crosses array bounds
rear = (rear + 1) % CAPACITY;
// Increment queue size
size++;
// Enqueue new element to queue
queue[rear] = data;
// Successfully enqueued element to queue
return 1;
}
/**
* Dequeue/Remove an element from the queue.
*/
int dequeue()
{
int data = INT_MIN;
// Queue is empty, throw Queue underflow error
if (isEmpty())
{
return INT_MIN;
}
// Dequeue element from queue
data = queue[front];
// Ensure front never crosses array bounds
front = (front + 1) % CAPACITY;
// Decrease queue size
size--;
return data;
}
/**
* Checks if queue is full or not. It returns 1 if queue is full,
* overwise returns 0.
*/
int isFull()
{
return (size == CAPACITY);
}
/**
* Checks if queue is empty or not. It returns 1 if queue is empty,
* otherwise returns 0.
*/
int isEmpty()
{
return (size == 0);
}
/**
* Gets, front of the queue. If queue is empty return INT_MAX otherwise
* returns front of queue.
*/
int getFront()
{
return (isEmpty())
? INT_MIN
: queue[front];
}
/**
* Gets, rear of the queue. If queue is empty return INT_MAX otherwise
* returns rear of queue.
*/
int getRear()
{
return (isEmpty())
? INT_MIN
: queue[rear];
}-------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 2 Queue is empty. -------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 3 Queue is empty. -------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 1 Enter data to enqueue: 10 Element added to queue. -------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 1 Enter data to enqueue: 20 Element added to queue. -------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 1 Enter data to enqueue: 30 Element added to queue. -------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 3 Queue size => 3 -------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 4 Rear => 30 -------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 5 Front => 10 -------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 2 Data => 10 -------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 2 Data => 20 -------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 2 Data => 30 -------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 2 Queue is empty. -------------------------------------- QUEUE ARRAY IMPLEMENTATION PROGRAM -------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------- Select an option: 0 Exiting from app.