Implement queue data structure using array

Implement queue data structure using array

Queues in computer programming have same properties which queues in real life has. First there is only one end where one can enter in queue from and other where one can exit from.  Second, the person who entered first will exit first.Queue data structure can be implemented by two ways in programs, using linked list or using arrays as underlying data structure. In this post we will focus on implementing queue using array. Refer implement queue using linked list , to understand more how to implement queues using linked list.

In queues, the end where person enters from is called as rear of queue and where person goes out is called as front of queue. The principle in which person who entered first leaves first is called as First In First Out (FIFO). It is exactly opposite of stack which is a LIFO data structure like stack data structure.

queue data structure

Operations on queue data structure

Queue data structure has following basic operations:
1. Enqueue()
Enqueue operation adds new element at rear of queue.

1. Check whether queue is FULL. We will see how this differs in different implementations.

2. If it is not full, then put new value at the end of the existing queue.

2. Dequeue()
Dequeue operation removes element from front of queue.

1. Check if queue is EMPTY. Again differs based on implementation.
2. If it is EMPTY, return with warning or error.
3. If it is not empty, take out the first element in queue.

3. isEmpty() :
Checks if there is at least one element present in queue or not at that point of time. This is most tricky part to implement in queue using arrays.

Queue data structure using array implementation

Ideally queue should not have any limit on number of elements that can be added to it. But array inherently have limit on size which is allocated at the time of declaration and which is static. When queue is implemented using arrays, take care that we have enough space available on underlying array, or else reallocate/resize the array. Some programming languages implicitly allow resizing of arrays, in however, languages like c, you have to do lot of effort to put existing elements in new array

#include <stdio.h>

#define true 1
#define false 0
#define MAX_SIZE 10

typedef struct node {
	int front;
	int rear;
	int items[MAX_SIZE];
}Queue;
/* This function initializes the queue */
void initializeQueue(Queue *q){
	q->front = -1;
	q->rear = -1;
}

/* Check if queue is empty or not */
int isEmpty(Queue *q){
	if(q->front == -1 && q->rear == -1)
		return true;

	return false;
}

/* Checks if queue is full */
int isFull(Queue *q){
	if(q->rear == MAX_SIZE-1)
		return true;

	return false;
}
/* Enqueue a particular element in queue */
void enqueue(Queue *q, int elem){
	if(isFull(q)){
		return;
	}
	if(isEmpty(q)) {
		q->front = 0;
		q->rear = 0;
	}
	else{
		q->rear += 1 ;
	}
	
	q->items[q->rear] = elem;

	return;
}

/* Dequeue a particular element from queue */
int dequeue(Queue *q){

	if(isEmpty(q)){
		printf("\n Queue is empty");
		return -1;
	}
	else if(q->front == q->rear){
		/* Last element in queue */
		int currentItem = q->items[q->front];
		q->rear = -1;
		q->front = -1;
		return currentItem;
	}
	else{
		return q->items[q->front++];
	}
}
int main(void) {
	
	Queue q;
	initializeQueue(&q);
	
	enqueue(&q, 1);
	enqueue(&q, 2);
	enqueue(&q, 3);
	
	printf("\nDequeued element : %d", dequeue(&q));
	printf("\nDequeued element : %d", dequeue(&q));
	printf("\nDequeued element : %d", dequeue(&q));
	printf("\nDequeued element : %d", dequeue(&q));

	return 0;
}

This implementation has limitation that is queue drifts towards end of the array as enqueue() and dequeue() operations are performed. We might end up saying queue full when there is only one element present in queue.

We can fix it by making rear pointing to first element once all slots in array are filled, that is wrapping around. We need to now come up with the full and empty condition of such a queue.

We can easily wrap around as rear = rear +1 % MAX_SIZE.
Queue is full when rear +1 = front but we see closely, same condition is true in case queue is empty.

So, initialize back and front appropriately. We start with front as 0 and rear as MAX_SIZE -1. Also, keep a counter in order to check if the queue is full or not.

#include <stdio.h>
#define true 1
#define false 0
#define MAX_SIZE 10

/* Queue data structure. */
typedef struct queue{
	int front;
	int rear;
	int count;  // To keep track current no of elements 
	int items[MAX_SIZE];
}Queue ;

/* This function initializes the queue */
void initializeQueue(Queue *q){
	q->front = -1;
	q->rear = MAX_SIZE-1;
	q->count = 0;
}

/* Checks if queue is empty */
int isEmpty(Queue *q){
	if(!q->count)
		return true;
	
	return false;
}

/* Checks if queue is full */
int isFull(Queue *q){
	if(q->count == MAX_SIZE)
		return true;

	return false;
}
void enqueue(Queue *q, int elem){
	if(isFull(q)){
		return;
	}
	/* Wrap around */
	q->rear = (q->rear + 1) % MAX_SIZE ;
	
	q->items[q->rear] = elem;
	/* Increment the counter */
	q->count++;
	
	return;
}

int dequeue(Queue *q){

	if(isEmpty(q)){
		printf("\n Queue is empty");
		return -1;
	}
	/* Wrap around the front */
	q->front  = (q->front + 1)%MAX_SIZE;
	int currentItem = q->items[q->front];
	
	/* Decrement the count */
	q->count--;

	return currentItem;

}
int main(void) {
	Queue q;
	initializeQueue(&q);
 
	enqueue(&q, 1);
	enqueue(&q, 2);
	enqueue(&q, 3);
 
	printf("\nDequeued element : %d", dequeue(&q));
	printf("\nDequeued element : %d", dequeue(&q));
	printf("\nDequeued element : %d", dequeue(&q));
	printf("\nDequeued element : %d", dequeue(&q));
	
	return 0;
}

Application of Queues are plenty. Like OS uses queues at multiple places like scheduler, waiting queues on semaphore, sending data from one process to another etc.

In next few posts we would problems which can be solved efficiently using queue data structure. Before that we would like to see linked list base implementation of queue in next post.