1
\$\begingroup\$

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

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you very much, I am glad you can see improvement in my programming. For the explicit comparison against nullptr, instead can I just my empty() function instead? So essentially, !empty() instead of first != nullptr. \$\endgroup\$ – Snorrlaxxx Jul 1 '18 at 21:48
  • \$\begingroup\$ !empty() — Even better! \$\endgroup\$ – JDługosz Jul 2 '18 at 19:03
  • \$\begingroup\$ for the do_unchecked_pop() could that code be applied for deleteTail() for a single linked list or no? \$\endgroup\$ – Snorrlaxxx Jul 3 '18 at 20:49
  • \$\begingroup\$ To delete a list, you do not need to use recursion — just use a while loop. \$\endgroup\$ – JDługosz Jul 5 '18 at 16:30
  • \$\begingroup\$ I meant deleting a tail not a list. Could we use unchecked_pop() to delete a tail in a single linked list? \$\endgroup\$ – Snorrlaxxx Jul 5 '18 at 23:30
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Are you saying to just change delete tmp to delete first? \$\endgroup\$ – Snorrlaxxx Jul 3 '18 at 20:46
  • \$\begingroup\$ Exactly, you want to delete the head of the queue not the second element \$\endgroup\$ – miscco Jul 4 '18 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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