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:
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.
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.
data
is required element dequeued from queue.
Program to implement queue using array
-------------------------------------- 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.