Linked List Queue + Stack algorithms

queue.cpp

#pragma once

template <typename T>
class Queue {
    // Internal structure: singly linked list, with head + tail pointers
    struct Node {
        T       value;
        Node*   next = nullptr;

        Node (const T& value, Node* next) : value(value), next(next) {}
        Node (const T&) = delete;
        Node& operator= (const Node&) = delete;
    };
    Node* head = nullptr;
    Node* tail = nullptr;
    size_t count = 0;       // cache our queue size / element count, set in push() / pop() only
public:
    // Queue is empty if it has no node elements / head & tail are null
    bool empty () const { 
        assert((head == nullptr) == (tail == nullptr));     // assert head null <=> tail null
        return head == nullptr;
    }

    size_t size () const { 
        assert((count == 0) == empty());
        return count; 
    }

    // Overload operator bool so we can implicitly check if our queue is true-ish (not empty) or not
    operator bool () const { return !empty(); }

    // Front of the queue is value at head, can access iff not empty()
    T&       front ()       { assert(!empty()); return head->value; }
    const T& front () const { assert(!empty()); return head->value; }

    // Back of the queue is value at tail, can access iff not empty()
    T&       back ()       { assert(!empty()); return tail->value; }
    const T& back () const { assert(!empty()); return tail->value; }

    // To insert an element, we add a new node to the back of the queue
    void push (const T& value) {
        // Note: we setup the queue so we can iterate backwards from the front of the list
        // And we have two cases: queue empty, or queue not empty
        if (!empty()) {
            // head not null, so can just assign to tail / tail->next to continue valid list
            tail = tail->next = new Node(value, nullptr);
        } else {
            // head + tail both null, so we need to assign to both to create a valid queue structure
            head = tail = new Node(value, nullptr);
        }
        ++count;
    }

    // To pop an element, we remove it from the front of the queue (valid iff not empty())
    void pop () {
        assert(!empty());
        Node* next = head->next;
        delete head;
        head = next;
        if (!head) {
            tail = nullptr;
        }
        --count;
    }

    // To clear the queue, we just call pop() until the queue is empty
    void clear () {
        while (!empty()) {
            pop();
        }
    }

    // We have one other useful operation: non-destructively iterating over the list.
    // For this we'll use a function closure; this is less general than an iterator, but is
    // much simpler to implement.
    template <typename F>
    void iterate (const F& fcn) const {
        // Very straightforward: we just iterate forwards from the front of the list
        for (Node* node = head; node != nullptr; node = node->next) {
            fcn(node->value);
        }
    }

    //
    // Now, using the above we can implement everything else: constructors, assignment operator, etc.
    //

    // Default constructor does nothing (already defined default values: head = tail = nullptr)
    Queue () {}

    // To copy-construct a queue, we'll use the assignment operator
    Queue (const Queue<T>& other) { *this = other; }

    // Which we'll define as follows:
    Queue& operator= (const Queue<T>& other) {
        // Very simple: just iterate over each element of the other queue (from front to back),
        // and push each value to copy them in order.
        other.iterate([this](const T& value) {
            push(value);
        });
        return *this;
    }

    // Similarly, if we wanted to construct from a std::initializer_list, the process is quite similar
    //  ie. so you can write    Queue<int> myQueue { 1, 2, 3, 4, 5 }; 
    Queue (const std::initializer_list<T>& values) {
        for (const auto& value : values) {
            push(value);
        }
    }

    // We could also define move constructors (a c++11 thing), where we basically swap the internal
    // structure of our queue instead of always copying (this is a useful compiler optimization,
    // but is not strictly necessary).
    Queue (Queue<T>&& other) { *this = std::move(other); }
    Queue<T>& operator= (Queue<T>&& other) {
        std::swap(head, other.head);
        std::swap(tail, other.tail);
        std::swap(count, other.count);
        return *this;
    }

    // Finally, our destructor just calls clear() to free all memory
    ~Queue () {
        clear();
    }

    // Lastly, if you _did_ want to implement a proper iterator, that would look something like this:
private:
    template <typename V>
    class Iterator {
        Node* node = nullptr;
        Iterator (Node* node) : node(node) {}
    public:
        Iterator (const Iterator&) = default;
        Iterator& operator= (const Iterator&) = default;

        operator bool () const { return node != nullptr; }
        bool operator== (const Iterator<V>& other) const { return node == other.node; }
        bool operator!= (const Iterator<V>& other) const { return node != other.node; }
        
        Iterator& operator++ () { if (node) node = node->next; return *this; }
        
        V&   operator*  () const { assert(*this); return node->value; }
        V*   operator-> () const { assert(*this); return &node->value; }

        operator Iterator<const V> () const { return Iterator<const V>(node); }
    };
public:
    typedef Iterator<T>         iterator;
    typedef Iterator<const T>   const_iterator;

    iterator begin () { return iterator(head);    }
    iterator end   () { return iterator(nullptr); }

    const_iterator begin () const { return const_iterator(head);    }
    const_iterator end   () const { return const_iterator(nullptr); }

    const_iterator cbegin () const { return begin(); }
    const_iterator cend   () const { return end();   }

    // The neat thing about this is we can now iterate over our queue using a range-based for loop
    //
    // Note:
    //   for (auto& value : queue) {
    //      std::cout << value << '\n';
    //   }
    // is syntax sugar for
    //   for (auto it = queue.begin(), end = queue.end(); it != end; ++it) {
    //      std::cout << *it << '\n';
    //   }
    //
    // and
    //   for (const auto& value : queue) {
    //      std::cout << value << '\n';
    //   }
    // is syntax sugar for
    //   for (auto it = queue.cbegin(), end = queue.cend(); it != end; ++it) {
    //      std::cout << *it << '\n';
    //   }
    //

    // Also, the implementation of our assignment operator becomes even simpler:
    /*
    Queue<T>& operator= (const Queue<T>& other) {
        for (const auto& value : other) {
            push(value);
        }
        return *this;
    }
    */
};