Queue array based implementation in C++

Question

I wrote my implementation to Queue array based. And I need a review for it to improve it and improve my coding skill. I also will put this implementation on my GitHub account. Thanks in advance.

//======================================================
// Author      : Omar_Hafez
// Created     : 29 July 2022 (Friday)  5:42:53 AM
//======================================================

#include <iostream>

enum InsertStatus { FailedQueueEmpty = -1, FailedQueueFull = -2, OK = 0 };

template <class T>
class Queue {

    private:
        int MAX_SIZE;
        T* array;
        int left = 0, right = 0, elementsCount = 0;

    public:
        Queue(int MAX_SIZE = 1000000)
            : MAX_SIZE(MAX_SIZE), array((T*)malloc(MAX_SIZE * sizeof(T))) {}

        bool empty() const { 
            return elementsCount == 0; 
        }

        bool full() const { 
            return elementsCount == MAX_SIZE; 
        }

        int size() const { return elementsCount; }

        InsertStatus push(T const& t) {
            if (full()) return FailedQueueFull;
            array[right] = t;
            right = (right+1)%MAX_SIZE;
            elementsCount++;
            return OK;
        }

        InsertStatus pop() {
            if (empty()) return FailedQueueEmpty;
            left = (left+1)%MAX_SIZE;
            elementsCount--;
            return OK;
        }

        T top() const { return array[left]; }

        void clear() {
            left = 0;
            right = 0;
            elementsCount = 0;
        }

        ~Queue() {
            delete(array);
            array = nullptr;
        }
};

Answer 1

Advice 1

private:
    int MAX_SIZE;
    T* array;
    int left = 0, right = 0, elementsCount = 0;

I would clean it a bit:

private:
    size_t max_capacity;
    size_t head_index;
    size_t _size;
    T* array;

The first idea is that you should favor size_t over int for indexing and counting. The second idea here is to denote the front value by array[head_index] and the next tail insertion point by array[(head_index + size) % max_capacity].

Advice 2

enum InsertStatus { FailedQueueEmpty = -1, FailedQueueFull = -2, OK = 0 };

With modern C++ you can use:

enum class InsertStatus { FailedQueueEmpty, FailedQueueFull, OK };

Advice 3

The method names push and pop are usually used in stacks. Since you are dealing with a FIFO queue, the more customary method names are enqueue and dequeue.

Alternative implementation

All in all, I had this in mind:

#ifndef COM_YOURCOMPANY_UTIL_ARRAY_QUEUE
#define COM_YOURCOMPANY_UTIL_ARRAY_QUEUE

#include <stdexcept>

namespace com::yourcompany::util {

template <class T>
class Queue {

private:
    size_t max_capacity;
    size_t head_index;
    size_t _size;
    T* array;

public:

    enum class OperationStatus {
        FailedQueueEmpty,
        FailedQueueFull,
        OK,
    };

    Queue(size_t max_capacity = 1_000_000)
        : max_capacity(max_capacity),
          head_index(0),
          _size(0),
          array(new T[max_capacity]) {}

    bool empty() const {
        return _size == 0;
    }

    bool full() const {
        return _size == max_capacity;
    }

    size_t size() const {
        return _size;
    }

    OperationStatus enqueue(T const& t) {
        if (full()) {
            return OperationStatus::FailedQueueFull;
        }

        array[(head_index + _size++) % max_capacity] = t;
        return OperationStatus::OK;
    }

    OperationStatus dequeue() {
        if (empty()) {
            return OperationStatus::FailedQueueEmpty;
        }

        head_index = (head_index + 1) % max_capacity;
        _size--;
        return OperationStatus::OK;
    }

    T top() const { 
        if (empty()) {
            throw std::runtime_error{"top() from empty queue."};
        }

        return array[head_index]; 
    }

    void clear() {
        head_index = 0;
        size = 0;
    }

    ~Queue() {
        delete[] array;
    }
};

}; // namespace com::yourcompany::util

#endif // COM_YOURCOMPANY_UTIL_ARRAY_QUEUE

Hope that helps.

Answer 2

• malloc and delete do not play well together. Prefer array = new T[MAX_SIZE] in the constructor.

• top happily returns something even if the queue is empty.

• enum InsertStatus is a misnomer. Why a removal operation (pop) returns insert status? A QueueOpStatus perhaps?

• clear is very optimistic. If T constructor allocates, you have a sure leak. clear must pop every element still in the queue. Ditto for ~Queue.