C Program to Implement Queue using Array
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle which means the elements added first in a queue will be removed first from the queue. In this article, we will learn how to implement a Queue using Array in C.
Implement Queue using Array in C
Approach:
- Define a structure consisting of an array and two pointers front and rear.
- Initialize the array with MAX_SIZE.
- Initialize both the front and rear pointers to -1.
- The insertion of elements will take place through the rear pointer and the deletion of elements will take place through the front pointer.
- Implement isFull, isEmpty, Enqueue, and Dequeue functions to manipulate the elements of the queue easily.
Representation of Queue in C
The queue will be represented as a structure of fixed size array which consists of two pointers front and rear. The fixed size array will store the elements of the queue and the front and rear pointers will help the users to manipulate the queue elements.
struct Queue {
int queue[MAX_SIZE];
int front;
int rear;
};
The user can define the maximum size of the array as per their requirements and a utility function can be used to initialize the front and the rear pointers to -1.
Basic Operations of Queue
Following are the basic operations of the Queue data structure which are required to manipulate the elements present inside the Queue.
Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
Enqueue | Inserts an element at the end of the queue using the rear pointer. | O(1) | O(1) |
Dequeue | Deletes an element from the front of the queue using the front pointer. | O(1) | O(1) |
IsEmpty | Checks if the queue is empty or not. If front ==-1 returns true. | O(1) | O(1) |
IsFull | Checks if the queue is full or not . If rear==MAX_SIZE-1 returns true. | O(1) | O(1) |
Now let’s see how we can implement the basic functions of queue in C:
1. Enqueue Function
The enqueue function will insert an element at the end of the queue using the rear pointer. Following is the algorithm for enqueue function:
Algorithm for Enqueue Function
1. Check if the queue is full
2. If the queue is empty, set front pointer to 0.
3. Increment rear pointer and add the element at the rear position in the queue array.
2. Dequeue Function
The dequeue function will delete an element from the front of the queue using the front pointer. Following is the algorithm for enqueue function:
Algorithm for Dequeue Function
- Check if the queue is empty.
- If not, store the data at the front position of the queue.
- If front pointer is equal to rear, reset both pointers to -1, indicating an empty queue.
- Otherwise, increment the front pointer to point to the next element.
3. IsEmpty Function
The isEmpty function returns true if the queue is empty otherwise it returns false. Following is the algorithm for the isEmpty function:
Algorithm for IsEmpty Function
- Check if front pointer is equal to -1
- Return true if front==-1 .
- Return false if front!=-1.
4. IsFull Function
The isFull function returns true if the queue is full otherwise it returns false.The queue is full when the rear pointer points to the last index of the array. Following is the algorithm for the isFull function:
Algorithm for IsFull Function
- Check if rear pointer is equal to MAX_SIZE – 1.
- Return true if rear==MAX_SIZE -1 .
- Return false if rear != MAX_SIZE-1.
C Program to Implement Queue using Array
The following program illustrates how we can implement the queue data structure using arrays in C:
// C Program to implement queue using arrays
#include <stdio.h>
// Define the maximum size for the queue
#define MAX_SIZE 100
// Define a structure for the queue
struct Queue {
int queue[MAX_SIZE];
int front;
int rear;
};
// Function to initialize the queue
void initializeQueue(struct Queue *q) {
q->front = -1;
q->rear = -1;
}
// Function to check if the queue is empty
int isEmpty(struct Queue *q) {
return (q->front == -1);
}
// Function to check if the queue is full
int isFull(struct Queue *q) {
return (q->rear == MAX_SIZE - 1);
}
// Function to insert an element into the queue
void enqueue(struct Queue *q, int data) {
if (isFull(q)) {
printf("Queue is full\n");
return;
}
if (isEmpty(q)) {
q->front = 0;
}
q->rear++;
q->queue[q->rear] = data;
printf("Enqueued %d in queue\n", data);
}
// Function to remove an element from the queue
int dequeue(struct Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return -1;
}
int data = q->queue[q->front];
// If the queue is empty reset the pointers
if (q->front == q->rear) {
q->front = -1;
q->rear = -1;
} else {
q->front++;
}
printf("Deleted element: %d\n", data);
return data;
}
// Function to display the elements of the queue
void display(struct Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return;
}
for (int i = q->front; i <= q->rear; i++) {
printf("%d ", q->queue[i]);
}
printf("\n");
}
int main() {
// Initialize a queue
struct Queue q;
initializeQueue(&q);
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
printf("Elements in the queue after enqueue operation: ");
display(&q);
dequeue(&q);
printf("Elements in the queue after dequeue operation: ");
display(&q);
return 0;
}
Output
Enqueued 1 in queue Enqueued 2 in queue Enqueued 3 in queue Elements in the queue after enqueue operation: 1 2 3 Deleted element: 1 Elements in the queue after dequeue operation: 2 3
Applications of Queue
The queue data structure has various applications in different domains of computer science. Some of the applications are:
- Queues are used in operating systems for process scheduling.
- In printing systems Queues are used to maintain First In First Out(FIFO) order.
- Queues are used in Graph data structures to perform Depth First Search(DFS).
- Queues are used in databases for transaction processing.
Conclusion
In the following article we have learned about the queue data structure and how we can implement it using arrays in C. We have learnt about the basic operations which are required in a queue data structure to manipulate the elements of the queue. We have also learned about the various applications of queue data structure in the computer science domain.
Related Articles
These are some articles that you may want to read to improve your understanding about queue: