C++ Queue 구현하기

in Dev. Log on Algorithm, Data Structure

Don’t reinvent the wheel; use libraries.

From <The C++ Programming Language> by Bjarne Stroustrup

들어가기에 앞서

앞으로 게시될 일련의 게시물들은 STL을 쓰지 못하는 특정 상황을 위해 STL과 비슷하게 동작하는 container, data structure, algorithm 등을 구현한 것 들입니다.
STL 상의 모든 함수들을 구현하지는 못하였지만(특히 iterator 관련…) 사용하는데 큰 지장은 없을 것 입니다.

STL을 사용할 수 있는 상황이라면 꼭 STL을 사용하도록 합시다. 나보다 똑똑한 사람들이 나보다 더 많은 시간을 들여서 작성하고 최적화한 코드입니다.

구현된 STL-like 자료 구조들은 Github Repo에서도 확인 하실 수 있습니다.

혹시나 있을 버그는 댓글 혹은 이메일로 제보해 주시면 수정하도록 하겠습니다.

Documents

FunctionDescription
push(T& val)Inserts a new element at the end of the queue.
pop()Removes the oldest element in the queue whose value can be retrieved by calling member front()
front()Returns a reference to the oldest element in the queue.
back()Returns a reference to the newest element in the queue.
size()Returns the number of elements in the queue.
empty()Returns whether the queue is empty: i.e. whether its size is zero.
swap(queue& x)Exchanges the contents of the container adaptor (*this) by those of x.

잡담

자주 사용하는 queue 입니다.
Unbounded circular queue로 구현하여 일반적으로 웹에서 보이는 최대 크기가 고정되어 있는 구현보다 낫습니다.
내부적으로 size가 capacity에 도달하면 increaseCapacity() 함수를 사용하여 capacity를 증가시킵니다.

구현

#include <cstddef>
#include <utility>

template <typename T>
class Queue {
private:
  static constexpr size_t DEFAULT_CAP = 4;
  T* arr;
  size_t head;
  size_t tail;
  size_t m_size;
  size_t m_capacity;

  void increaseCapacity() {
    size_t prev_cap = m_capacity;
    if (m_capacity < DEFAULT_CAP)
      m_capacity = DEFAULT_CAP;
    else
      m_capacity *= 2;
    T *t_arr = new T[m_capacity];
    for (size_t i = 0; i < m_size; i++)
      t_arr[i] = arr[(head + i) % prev_cap];
    head = 0;
    tail = m_size;
    delete[] arr;
    arr = t_arr;
  }

public:
  Queue() : arr{new T[DEFAULT_CAP]}, head(0), tail(0), m_size(0), m_capacity(DEFAULT_CAP) {}
  Queue(const Queue& q) : arr(new T[q.m_capacity]), head(q.head), tail(q.tail), m_size(q.m_size), m_capacity(q.m_capacity) {
    for (size_t i = 0; i < m_size; i++)
      arr[i] = q[i];
  }
  Queue(Queue&& q) : arr(std::move(q.arr)), head(std::move(q.head)), tail(std::move(q.tail)), m_size(std::move(q.m_size)), m_capacity(std::move(q.m_capacity)) {
    q.arr = nullptr;
    q.head = 0;
    q.tail = 0;
    q.m_size = 0;
    q.m_capacity = 0;
  }

  ~Queue() { delete[] arr; }

  Queue& operator=(const Queue& other) {
    if (this != &other) {
      if (m_capacity < other.m_capacity) {
        delete[] arr;
        m_capacity = other.m_capacity;
        arr = new T[m_capacity];
      }
      head = other.head;
      tail = other.tail;
      m_size = other.m_size;
      for (size_t i = 0; i < m_size; i++)
        arr[i] = other.arr[i];
    }
    return *this;
  }
  Queue& operator=(Queue&& other) {
    swap(arr, other.arr);
    swap(m_size, other.m_size);
    swap(m_capacity, other.m_capacity);
    other.m_size = 0;
    return *this;
  }

  bool empty() const { return m_size == 0; }
  size_t size() const { return m_size; }

  T& front() { return arr[head]; }
  const T& front() const { return arr[head]; }

  T& back() {
    return arr[(head + m_size - 1) % m_capacity]; }
  const T& back() const { return arr[(head + m_size - 1) % m_capacity]; }

  void push(const T& val) {
    if(m_size >= m_capacity)
      increaseCapacity();
    arr[tail] = val;
    tail = (tail + 1) % m_capacity;
    m_size++;
  }

  void push(T&& val) {
    if(m_size >= m_capacity)
      increaseCapacity();
    arr[tail] = std::move(val);
    tail = (tail + 1) % m_capacity;
    m_size++;
  }

  void pop() {
    if (m_size > 0) {
      head = (head + 1) % m_capacity;
      m_size--;
    }
  }

  void swap(Queue& other) {
    std::swap(arr, other.arr);
    std::swap(head, other.head);
    std::swap(tail, other.tail);
    std::swap(m_size, other.m_size);
    std::swap(m_capacity, other.m_capacity);
  }
};