Generic Queue data structure in C++

Question

I am a mathematician attempting to become proficient with C++. At the moment I am learning about data structures. I am now writing a queue data structure using linked list from scratch.

I have tested my class that I wrote and everything seems to be working fine but I want to see if there are any bugs or some areas of the code I could improve on.

Here is the class:

#ifndef Queue_h
#define Queue_h

template <class T>
class Queue {
private:
    struct Node {
        T data;
        Node* next = nullptr;
    };
    Node* first = nullptr;
    Node* last = nullptr;

    // Used for destructor to delete elements
    void do_unchecked_pop();

    // Use for debugging purposes and for overloading the << operator
    void show(std::ostream &str) const;

public:
    // Constructors
    Queue() = default;                                                        // empty constructor
    Queue(Queue const& value);                                                // copy constructor

    // Rule of 5
    Queue(Queue&& move) noexcept;                                             // move constuctor
    Queue& operator=(Queue&& move) noexcept;                                  // move assignment operator
    ~Queue();                                                                 // destructor

    // Overload operators
    Queue& operator=(Queue const& rhs);
    friend std::ostream& operator<<(std::ostream& str, Queue<T> const& data) {
        data.show(str);
        return str;
    }

    // Member functions
    bool empty() const {return first == nullptr;}
    int size() const;
    T& front() const;
    T& back() const;
    void push(const T& theData);
    void push(T&& theData);
    void pop();
    void swap(Queue& other) noexcept;


};

template <class T>
Queue<T>::Queue(Queue<T> const& value)  {
    try {
        for(auto loop = value.first; loop != nullptr; loop = loop->next)
            push(loop->data);
    }
    catch (...) {
        while(first != nullptr)
            do_unchecked_pop();
        throw;
    }
}

template <class T>
Queue<T>::Queue(Queue&& move) noexcept {
    move.swap(*this);
}

template <class T>
Queue<T>& Queue<T>::operator=(Queue<T> &&move) noexcept {
    move.swap(*this);
    return *this;
}

template <class T>
Queue<T>::~Queue() {
    while(first != nullptr) {
        do_unchecked_pop();
    }
}

template <class T>
int Queue<T>::size() const {
    int size = 0;
    for (auto current = first; current != nullptr; current = current->next)
        size++;
    return size;
}

template <class T>
T& Queue<T>::front() const {
    if(first == nullptr) {
        throw std::out_of_range("the Queue is empty!");
    }
    return first->data;
}

template <class T>
T& Queue<T>::back() const {
    return last->data;
}

template <class T>
void Queue<T>::push(const T& theData) {
    Node* newNode = new Node;
    newNode->data = theData;
    newNode->next = nullptr;

    if(first == nullptr) {
        first = last = newNode;
    }

    else {
        last->next = newNode;
        last = newNode;
    }
}

template <class T>
void Queue<T>::push(T&& theData) {
    Node* newNode = new Node;
    newNode->data = std::move(theData);
    newNode->next = nullptr;

    if(first == nullptr) {
        first = last = newNode;
    }

    else {
        last->next = newNode;
        last = newNode;
    }
}

template <class T>
void Queue<T>::pop() {
    if(first == nullptr) {
        throw std::invalid_argument("the Queue is empty!");
    }
    do_unchecked_pop();
}

template <class T>
void Queue<T>::do_unchecked_pop() {
    Node* tmp = first->next;
    delete tmp;
    first = tmp;
}

template <class T>
void Queue<T>::show(std::ostream &str) const {
    for(Node* loop = first; loop != nullptr; loop = loop->next) {
        str << loop->data << "\t";
    }
    str << "\n";
}

template <class T>
void Queue<T>::swap(Queue<T> &other) noexcept {
    using std::swap;
    swap(first, other.first);
    swap(last, other.last);
}

// Free function
template <typename T>
void swap(Queue<T>& a, Queue<T>& b) noexcept {
    a.swap(b);
}


#endif /* Queue_h */

Here is the main.cpp that tests the latter class:

#include <algorithm>
#include <cassert>
#include <iostream>
#include <ostream>
#include <iosfwd>
#include "Queue.h"

int main(int argc, const char * argv[]) {

      ///////////////////////////////////////////////////////////////////////////////////
    ///////////////////////////// Queue Using Linked List //////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////////////

    Queue<int> obj;
    obj.push(2);
    obj.push(4);
    obj.push(6);
    obj.push(8);
    obj.push(10);
    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Displaying Queue Contents---------------";
    std::cout<<"\n--------------------------------------------------\n";
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Pop Queue Element -------------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.pop();
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Get the size of Queue -------------------";
    std::cout<<"\n--------------------------------------------------\n";
    std::cout << obj.size() << std::endl;


    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Print top element --------------------";
    std::cout<<"\n--------------------------------------------------\n";
    std::cout << obj.front() << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Print last element --------------------";
    std::cout<<"\n--------------------------------------------------\n";
    std::cout << obj.back() << std::endl;

    return 0;
}

Answer 1

Just looking at the beginning of the class, I can see that you’ve learned a lot since your first version. Keep it up!

---

As I’ve said before, Don’t make explicit comparisons against nullptr. Use the contextual conversion to bool as a truth value.

---

    while(first != nullptr)
        do_unchecked_pop();

is repeated. You should have a single helper function to delete a whole list, if you are avoiding deep recursion. If your list is small you don’t need it at all as it should already take care of itself.

---

You have several loops of the form

for(auto loop = value.first; loop != nullptr; loop = loop->next)

you should provide proper iterators so you can just use a range-for

---

Prefer using \n over std::endl

The style in C++ is to put the * or & with the type, not the identifier. This is called out specifically near the beginning of Stroustrup’s first book, and is an intentional difference from C style.

Answer 2

There is a check missing in your back() function (If the queue is empty you have an error).

It would increase readability if you would use empty() instead of repeated top == nullptr checks. The intent is more obvious that way.

Your do_unchecked_pop is buggy

template <class T>
void Queue<T>::do_unchecked_pop() {
    Node* tmp = first->next;
    delete tmp;
    first = tmp;
}

You assign first to the deleted node. I think you would want to delete first here not tmp.

In you push() function there is no need to assign next to nullptr as it is already the default value. However, it would definitely improve readability if you would simply create a constructor for Node