Queue Implementation in CPP

1. Introduction

A Queue is a linear data structure that follows the First In First Out (FIFO) principle. This means that the first element added to the queue will be the first element to be removed. Elements are inserted at one end (rear) and removed from the other end (front). 

Some real-world examples of a Queue data structure include waiting in line at a checkout counter, where the person who arrived first gets served first.

2. Implementation Steps

1. Define the maximum size of the queue.

2. Initialize the queue with a structure or class containing an array to store elements, and variables to keep track of the front and rear indices.

3. Implement the enqueue operation to add elements to the end of the queue.

4. Implement the dequeue operation to remove the front element from the queue.

5. Implement the front operation to view the front element without removing it.

6. Implement utility functions like isEmpty and isFull to check the status of the queue.

3. Implementation in C++ Programming

#include <iostream>
using namespace std;
#define MAX 1000  // Define the maximum size of the queue
class Queue {
private:
    int arr[MAX];
    int front, rear;
public:
    Queue() {
        front = -1;
        rear = -1;
    }  // Constructor to initialize queue
    bool enqueue(int x) {
        if ((rear + 1) % MAX == front) {
            cout << "Queue Overflow";
            return false;
        } else {
            rear = (rear + 1) % MAX;
            arr[rear] = x;
            if (front == -1) {
                front = rear;
            }
            return true;
        }
    }
    int dequeue() {
        if (front == -1) {
            cout << "Queue Underflow";
            return 0;
        } else {
            int x = arr[front];
            if (front == rear) {
                front = -1;
                rear = -1;
            } else {
                front = (front + 1) % MAX;
            }
            return x;
        }
    }
    int getFront() {
        if (front == -1) {
            cout << "Queue is Empty";
            return 0;
        } else {
            return arr[front];
        }
    }
    bool isEmpty() {
        return (front == -1);
    }
};
// Client code to test the queue implementation
int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    cout << q.dequeue() << " Dequeued from queue\n";
    cout << "Front element is " << q.getFront() << endl;
    return 0;
}

Output:

10 Dequeued from queue
Front element is 20

Explanation:

1. The Queue class contains an array arr to store queue elements, and variables front and rear to keep track of the front and end of the queue.

2. The enqueue function checks if there is space in the queue. If there's room, it inserts the element at the rear of the queue. Otherwise, it indicates a "Queue Overflow" error.

3. The dequeue function checks if the queue is empty. If not, it removes the front element and updates the front index. Otherwise, it indicates a "Queue Underflow" error.

4. The getFront function returns the front element without dequeueing it.

5. The isEmpty function checks if the queue is empty by examining the value of front.

6. In the client code, we add a few elements to the queue and then dequeue an element. The program also demonstrates checking the frontmost element using the getFront function.