dequeue_list.h

#ifndef QUEUE_H
#define QUEUE_H
 
#ifdef __cplusplus
#include <iostream>
#include <memory>
#include <vector>
#endif

template <typename T> class dequeue_list {
  private:
    struct node {
        T val;
        std::shared_ptr<node> next;
        std::shared_ptr<node> prev;
        node(T key) : val(key), next(nullptr), prev(nullptr) {}
    };
 
    std::shared_ptr<node> root;
    std::shared_ptr<node> tail;
    size_t _size{0};
 
  public:
    inline explicit dequeue_list(std::vector<T> v = {}) noexcept : root(nullptr), tail(nullptr) {
        if (!v.empty()) {
            for (T& x : v) {
                this->push_back(x);
            }
        }
    }

    inline explicit dequeue_list(const dequeue_list& q)
        : root(q.root), tail(q.tail), _size(q._size) {}

    inline dequeue_list& operator=(const dequeue_list& q) {
        root = q.root;
        tail = q.tail;
        _size = q._size;
        return *this;
    }

    inline void clear() {
        root = nullptr;
        tail = nullptr;
        _size = 0;
    }

    inline size_t size() { return _size; }

    inline void push_back(T key) {
        std::shared_ptr<node> nn = std::make_shared<node>(key);
        if (!root) {
            root = nn;
            tail = nn;
            _size++;
            return;
        } else {
            tail->next = nn;
            nn->prev = tail;
            tail = nn;
            _size++;
        }
    }

    inline void push_front(T key) {
        std::shared_ptr<node> nn = std::make_shared<node>(key);
        if (!root) {
            root = nn;
            tail = nn;
            _size++;
            return;
        } else {
            root->prev = nn;
            nn->next = root;
            root = nn;
            _size++;
        }
    }

    inline T front() { return root->val; }

    inline T back() { return tail->val; }

    inline void pop_front() {
        root = root->next;
        root->prev = nullptr;
        _size--;
    }

    inline void pop_back() {
        tail = tail->prev;
        tail->next = nullptr;
        _size--;
    }
 
    class Iterator;

    inline Iterator begin() { return Iterator(root); }

    inline Iterator end() { return Iterator(nullptr); }
};

template <typename T> class dequeue_list<T>::Iterator {
  private:
    std::shared_ptr<node> curr_root;
 
  public:
    explicit Iterator(const std::shared_ptr<node>& q) noexcept : curr_root(q) {}

    Iterator& operator=(std::shared_ptr<node> current) {
        this->curr_root = current;
        return *(this);
    }

    Iterator& operator++() {
        if (curr_root) {
            curr_root = curr_root->next;
        }
        return *(this);
    }

    Iterator operator++(int) {
        Iterator it = *this;
        ++*(this);
        return it;
    }

    bool operator!=(const Iterator& it) { return curr_root != it.curr_root; }

    T operator*() { return curr_root->val; }
};
 
#endif