2
\$\begingroup\$

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;
        }
};
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Setting variable values in the destructor is pointless, as the object won’t exist any more as soon as the destructor returns. All you need to do is delete the array. \$\endgroup\$ Jul 30, 2022 at 19:47
  • \$\begingroup\$ @CrisLuengo Point. Will fix. \$\endgroup\$
    – coderodde
    Jul 31, 2022 at 4:06
2
\$\begingroup\$
  • 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.

\$\endgroup\$
4
  • \$\begingroup\$ clear is to make all the elements in the queue zero (from the user side) and we leave deallocating the array for the ~Queue \$\endgroup\$
    – Omar_Hafez
    Jul 30, 2022 at 5:27
  • \$\begingroup\$ "top happily returns something even if the queue is empty" How to fix this issue? \$\endgroup\$
    – Omar_Hafez
    Jul 30, 2022 at 6:00
  • 1
    \$\begingroup\$ "do not play well together" is an understatement: it's in fact illegal to delete something that was not allocated using new, and it will crash on some platforms. \$\endgroup\$
    – G. Sliepen
    Jul 30, 2022 at 12:19
  • 1
    \$\begingroup\$ @Omar_Hafez: If T is anything but a plain old datatype (POD), then things here break down. You never call their constructors nor their destructors. Unless you ensure T is a POD, your code is broken. Using array new and array delete would solve the issue. \$\endgroup\$ Jul 30, 2022 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.