C++ Queue

Introduction

Queue is a data structure that follows the First In First Out (FIFO) principle.

Source: Freepik

Two common operations in queue are enqueue and dequeue.
Enqueue is to add an element to the end of the queue.
Dequeue is to remove an element from the front of the queue.
First In First Out Queue
Source: Masai School

Implementation with array

Queue can be implemented using array. The front of the queue is at index 0 and the rear of the queue is at index n-1.

Source: PrepInsta

To implement a queue using array, we need to keep track of the front and rear of the queue.
When we enqueue an element, we increment the rear index.
When we dequeue an element, we increment the front index.
We need to check if the queue is full or empty before enqueue or dequeue an element.

Pseudocode

Pseudocode for enqueue:

if rear == n-1
	print "Queue is full"
else
	rear = rear + 1
	arr[rear] = element

Pseudocode for dequeue:

if front == rear
	print "Queue is empty"
else
	front = front + 1
	element = arr[front]

Linear Queue

If linear queue is implemented, after dequeue operation, there will be empty spaces in the front.
The remaining elements will be shifted to the front.
This is inefficient.

Source: GeeksforGeeks

Pseudocode for dequeue operation in linear queue:

element = arr[front]
for i = 0 to rear-1
	arr[i] = arr[i+1]
rear = rear - 1

Circular Queue

To avoid the problem of queue being full but there are empty spaces in the front, we can use circular queue.
When the rear reaches the end of the array, we can set rear to 0.
When the front reaches the end of the array, we can set front to 0.

Source: Marx Tudor

Source: GeeksforGeeks

We can use the modulo operator to implement circular queue.

rear = (rear + 1) % n
front = (front + 1) % n

Pseudocode for enqueue operation in circular queue:

if (rear + 1) % n == front
	print "Queue is full"
else

	rear = (rear + 1) % n
	arr[rear] = element

Pseudocode for dequeue operation in circular queue:

if front == rear
	print "Queue is empty"
else
	front = (front + 1) % n
	element = arr[front]

Task

Create a queue with length 8. Implement enqueue and dequeue functions.
Sample output:

1. Enqueue
2. Dequeue
3. Exit
Enter your choice: 1
Enter element to enqueue: 10
10 is enqueued
1. Enqueue
2. Dequeue
3. Exit
Enter your choice: 1
Enter element to enqueue: 20
20 is enqueued
1. Enqueue
2. Dequeue
3. Exit
Enter your choice: 2
10 is dequeued
1. Enqueue
2. Dequeue
3. Exit
Enter your choice: 2
20 is dequeued
1. Enqueue
2. Dequeue
3. Exit
Enter your choice: 2
Queue is empty
1. Enqueue
2. Dequeue
3. Exit
Enter your choice: 3