6
\$\begingroup\$

In an effort to brush up my algorithms and data structure skills I have a done a queue implementation without using built in data structures, i.e. using only arrays. Any comments on this code regarding issues, bad/ good practices and good style would be greatly appreciated.

#include <stdexcept>
#include <cassert>
#include <string>
#include <iostream>

class QueueError : public std::runtime_error {
    public:
        QueueError(std::string str) : std::runtime_error(str) {};
};

class Queue {
    struct LLNode {
        int val;
        LLNode* next;
    };
    private:
        LLNode** queue = 0;
        int limit;
        int currSize = 0;
        LLNode* first;
        LLNode* last;
        void swap(const Queue& that);
        void destroy();
    public:
        Queue(int size);
        void enqueue(int val);
        int dequeue();
        virtual ~Queue();
        Queue& operator=(const Queue& that);
        Queue(const Queue& that);
        int size();

};

Queue::Queue(int size) {
    if (size <= 0) throw QueueError("Queue size cannot be negative or 0");
    this->limit = size;
    const int l = this->limit;
    queue = new LLNode*[l];
    // make it circular
    for (int i = 0;i < l; ++i) {
        queue[i] = new LLNode();
        if ((i - 1) >= 0) {
            queue[i-1]->next = queue[i];
        }
    }
    queue[l-1]->next = queue[0];
    first = 0;
    last = 0;
}

void Queue::enqueue(int val) {
    if (currSize == limit) {
        throw QueueError(std::string("Queue size cannot exceed limit of queue."));
    }
    ++currSize;
    if (last != 0) {
        last = last->next;
    } else {
        first = last = queue[0];
    }
    last->val = val;
}

int Queue::dequeue() {
    if (currSize == 0) {
        throw QueueError(std::string("Queue size is 0. Queue cannot be dequeued"));
    }
    currSize--;
    int returnVal = first->val;
    if (currSize != 0) {
        first = first->next;
    } else {
        first = last = 0;
    }
    return returnVal;
}

int Queue::size() {
    return currSize;
}

void Queue::destroy() {
    if (queue == 0) return;
    const int l = this->limit;
    for (int i = 0;i < l; ++i) {
        delete queue[i];
    }
    delete[] queue;
}

Queue::~Queue() {
    destroy();
}

void Queue::swap(const Queue& that) {
    this->limit = that.limit;
    const int l = this->limit;
    LLNode** tmpQueue = new LLNode*[l];
    // make it circular
    for (int i = 0;i < l; ++i) {
        tmpQueue[i] = new LLNode();
        tmpQueue[i]->val = that.queue[i]->val;
        if ((i - 1) >= 0) {
            tmpQueue[i-1]->next = tmpQueue[i];
        }
    }
    tmpQueue[l-1]->next = tmpQueue[0];
    destroy();
    queue = tmpQueue;
    first = that.first;
    last = that.last;
    currSize = that.currSize;
}

Queue::Queue(const Queue& that) {
    swap(that);
}

Queue& Queue::operator=(const Queue& that) {
    if (this != &that) {
        Queue tmp(that);
        swap(tmp);
    }
    return *this;
}



int main() {
    const int qSize = 200;
    const int addVal = 100;
    Queue queue(qSize);
    for (int i = 0; i < qSize; ++i) {
        queue.enqueue(i + addVal);
        //std::cout << i + addVal << " ";
    }
        std::cout << std::endl;
    assert(queue.size() == qSize);
    // make a copy
    Queue queueCopy = queue;

    // check if exception is thrown
    bool exThrown = false;
    try {
        queue.enqueue(100);
    } catch (QueueError &e) {
        exThrown = true;
    }
    assert(exThrown);

    for (int i = 0; i < qSize; ++i) {
        int val = queue.dequeue();
        //std::cout << val << " ";
        assert(val == (i + addVal));
    }

    exThrown = false;
    try {
        queue.dequeue();
    } catch (QueueError &e) {
        exThrown = true;
    }
    assert(exThrown);

    // can I enqueue again?
    queue.enqueue(addVal);
    assert(queue.dequeue() == addVal);

    // check Copy
    for (int i = 0; i < qSize; ++i) {
        int val = queueCopy.dequeue();
        assert(val == (i + addVal));
    }
    std::cout << "All queue tests run successfully" << std::endl;
}
\$\endgroup\$

2 Answers 2

6
\$\begingroup\$

First thing I would change is the ordering of fields in the class declaration. I find it better to place public fields first, since this is what users of the class are interested on, most of the time. Then place protected fields in the sequence, since these are externally accessible via inheritance, so their encapsulation is less strong. Lastly place private fields that are only important to the class maintainer.


Unnecessary virtual destructor: Don't make a destructor virtual unless you intend to extend the class. In this case, I don't see why anyone would want to extend a queue implementation. Any use or extension of the queue can be done with composition, which is generally preferred over inheritance.


Default initialize all fields, not just some. Do it either in the declaration or in the constructor.

LLNode** queue = nullptr;
LLNode* first  = nullptr;
LLNode* last   = nullptr;
int limit      = 0;
int currSize   = 0;

Also notice the use of nullptr for the pointers. This is the standard since C++11.


Methods that don't mutate member state should be const. size() is an example:

int size() const;

Instead of returning the removed element in int dequeue(), perhaps provide a int front() const method that returns the element without removing. Then make dequeue() void. This is the interface of std::queue, so it would be a good idea to somewhat follow the convention people are most used to.


You don't need that explicit string cast when throwing the exceptions:

throw QueueError(std::string("Queue size is 0. Queue cannot be dequeued"));

All that is doing is creating an extra copy of the string. Some compilers might not be smart enough to optimize that out. It should be just:

throw QueueError("Queue size is 0. Queue cannot be dequeued");

If you separate your code into header file and .cpp implementation, make sure to only leave the necessary includes in the header file. You don't have to include <cassert> and <iostream> in the header, just in the .cpp. Being careful with your includes will help you keeping compile times under control.

\$\endgroup\$
6
  • \$\begingroup\$ +1, but I think your first point is just personal preference. Listing private then public is perfectly fine in my eyes. \$\endgroup\$
    – Yuushi
    Nov 2, 2014 at 5:40
  • 1
    \$\begingroup\$ The reason why pop_back & co do not return the value is not style or convention but exception safety. Supposedly it is not possible to make T pop_back(); exception safe, but I couldn't go into detail on that. \$\endgroup\$
    – nwp
    Nov 2, 2014 at 9:35
  • \$\begingroup\$ @Yuushi - Yes, you could say so. But I did give a reason for that preference. So it wasn't just randomly picked ;) \$\endgroup\$
    – glampert
    Nov 2, 2014 at 12:57
  • \$\begingroup\$ @nwp - Well, yes, it makes sense. The constructor of T can throw. When removing from the container, a temp copy inside pop() would be almost certain. Which could affect the validity of the container if an exception happens in mid removal. \$\endgroup\$
    – glampert
    Nov 2, 2014 at 13:00
  • 1
    \$\begingroup\$ @dev_nut - Yes the first point is mainly from personal experience and preference. That ordering seems more reader-friendly to me for the reasons I mentioned. My main reason to advocate against the virtual destrutor is the YAGNI principle. I also recommend reading this and this threads. \$\endgroup\$
    – glampert
    Nov 2, 2014 at 16:22
5
\$\begingroup\$
  1. It's quite strange that you have this indirection via LLNode - you effectively have a linked list and an array at the same time. This seems like double work. I would get rid of LLNode and just go via the index into the array. This gets rid of a whole lot of code (or get rid of the array and use a linked list instead).

    Queues are a natural fit for linked lists as you typically only access the head and tail and don't need random access. Although most standard library queue implementations I know of are array based probably due to better performance (cache locality)

  2. It shouldn't be too hard to template the item type so you can have a queue of any type rather than just int.

\$\endgroup\$
1
  • \$\begingroup\$ I guess I had mixed ideas and made a little mess here. I initially was trying to just use an array, and thought I can't do that, I need a linked list. I see I'm wrong here. Thanks for pointing this out. \$\endgroup\$
    – dev_nut
    Nov 1, 2014 at 21:40

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.