Quick and dirty queues

queue.cpp

#include <cassert>
#include <iostream>

template <typename T>
class ListQueue {
 public:
  using size_t = unsigned long;

  ListQueue() : _head(nullptr), _tail(nullptr), _size(0) {
  }

  ~ListQueue() {
    while (_head) {
      auto next = _head->next;
      delete _head;
      _head = next;
    }
  }

  void enqueue(const T& element) {
    auto node = new Node{element, nullptr};
    if (_tail) {
      _tail->next = node;
    } else {
      _head = node;
    }
    _tail = node;
    ++_size;
  }

  const T& front() const noexcept {
    assert(_size > 0);
    return _head->element;
  }

  const T& back() const noexcept {
    assert(_size > 0);
    return _tail->element;
  }

  T dequeue() {
    assert(_size > 0);

    auto node    = _head;
    _head        = node->next;
    auto element = node->element;
    delete node;
    --_size;

    return element;
  }

  size_t size() const noexcept {
    return _size;
  }

  bool is_empty() const noexcept {
    return size() == 0;
  }

 private:
  struct Node {
    T element;
    Node* next;
  };

  Node* _head;
  Node* _tail;
  size_t _size;
};

template <typename T>
class ArrayQueue {
 public:
  using size_t = unsigned long;

  static constexpr size_t MINIMUM_CAPACITY = 8;
  static constexpr size_t GROWTH_FACTOR    = 2;
  static constexpr size_t SHRINK_THRESHOLD = 4;

  explicit ArrayQueue(size_t capacity = MINIMUM_CAPACITY)
  : _data(new T[capacity]), _size(0), _capacity(capacity) {
  }

  ~ArrayQueue() {
    delete[] _data;
  }

  void enqueue(const T& element) {
    if (_size == _capacity) {
      _reallocate(_size * GROWTH_FACTOR);
    }

    _data[_write] = element;
    _write        = _one_after(_write);
    ++_size;
  }

  const T& front() const noexcept {
    assert(_size > 0);
    return _data[_read];
  }

  const T& back() const noexcept {
    assert(_size > 0);
    return _data[_one_before(_write)];
  }

  T dequeue() {
    assert(_size > 0);

    auto element = _data[_read];
    _read        = _one_after(_read);

    if (--_size == _capacity / SHRINK_THRESHOLD) {
      _reallocate(_size * GROWTH_FACTOR);
    }

    return element;
  }

  size_t size() const noexcept {
    return _size;
  }

  bool is_empty() const noexcept {
    return size() == 0;
  }


 private:
  void _reallocate(size_t new_capacity) {
    if (new_capacity < MINIMUM_CAPACITY) {
      new_capacity = MINIMUM_CAPACITY;
    }
    if (new_capacity == _capacity) return;

    auto old = _data;
    _data    = new T[new_capacity];

    size_t new_index = 0;
    size_t last      = _one_before(_write);
    for (size_t i = _read; i != last; i = _one_after(i)) {
      _data[new_index++] = old[i];
    }

    _data[new_index] = old[last];

    delete[] old;

    _read     = 0;
    _write    = _size;
    _capacity = new_capacity;
  }

  size_t _one_after(size_t index) {
    return (index + 1) % _capacity;
  }

  size_t _one_before(size_t index) {
    return index ? index - 1 : _capacity - 1;
  }

  T* _data;

  size_t _read;
  size_t _write;

  size_t _size;
  size_t _capacity;
};

auto main() -> int {
  ArrayQueue<int> queue;

  for (int i = 0; i < 10; ++i) {
    queue.enqueue(i);
  }

  for (int i = 0; i < 10; ++i) {
    std::cout << queue.dequeue() << " " << queue.size() << std::endl;
  }
}