C++ Program to Implement Queue Using Arrays

1. Introduction

A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means the first element added to the queue is the first to be removed. In this post, we'll implement a basic queue using arrays in C++.

2. Program Overview

Our queue implementation will provide the following operations:

1. enqueue: Adds an item to the rear of the queue.

2. dequeue: Removes the front item from the queue.

3. front: Returns the front item from the queue without removing it.

4. rear: Returns the rear item from the queue.

5. isEmpty: Checks if the queue is empty.

6. isFull: Checks if the queue is full.

3. Code Program

#include <iostream>
#define SIZE 1000

class Queue {
    int front, rear;
public:
    int arr[SIZE];

    Queue() { front = -1; rear = -1; }
    bool enqueue(int x);
    int dequeue();
    int getFront();
    int getRear();
    bool isEmpty();
    bool isFull();
};

bool Queue::enqueue(int x) {
    if (isFull()) {
        std::cout << "Queue Overflow";
        return false;
    }
    if (isEmpty()) {
        front = rear = 0;
    } else {
        rear = (rear + 1) % SIZE;
    }
    arr[rear] = x;
    return true;
}

int Queue::dequeue() {
    if (isEmpty()) {
        std::cout << "Queue Underflow";
        return -1;
    }
    int item = arr[front];
    if (front == rear) {
        front = rear = -1;
    } else {
        front = (front + 1) % SIZE;
    }
    return item;
}

int Queue::getFront() {
    if (isEmpty()) return -1;
    return arr[front];
}

int Queue::getRear() {
    if (isEmpty()) return -1;
    return arr[rear];
}

bool Queue::isEmpty() {
    return (front == -1);
}

bool Queue::isFull() {
    return ((rear + 1) % SIZE == front);
}

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    std::cout << "Front element is " << q.getFront() << std::endl;
    std::cout << "Dequeued element from queue is " << q.dequeue() << std::endl;
    return 0;
}

Output:

Front element is 10
Dequeued element from queue is 10

4. Step By Step Explanation

The Queue class encapsulates all the necessary functions for basic queue operations. An array arr of size SIZE is used to store queue elements, while front and rear integers track the frontmost and rearmost elements in the queue.

1. The enqueue function adds an element to the rear of the queue.

2. The dequeue function removes and returns the frontmost element.

3. The getFront and getRear functions return the frontmost and rearmost elements, respectively, without removing them.

4. The isEmpty function checks if the queue is empty.

5. The isFull function checks if the queue is full.

In the main function, we demonstrate the use of these methods by enqueuing three elements to the queue, displaying the front element, and then dequeuing one element.