queue.cc

#include <stack>
#include <deque>
#include <queue>
#include <vector>
#include <mutex>
#include <iostream>
#include <condition_variable>

template <typename T>
class QueueUsingStack
{
public:
  void push(const T& val);
  void pop();
  bool empty();

private:
  std::stack<T> spush;
  std::stack<T> spop;
};

template <typename T>
void QueueUsingStack<T>::push(const T& val)
{
  spush.push(val);
}

template <typename T>
void QueueUsingStack<T>::pop()
{
  if (spop.empty()) {
    while (!spush.empty()) {
      spop.push(spush.top());
      spush.pop();
    }
  }
  spop.pop();
}

template <typename T>
bool QueueUsingStack<T>::empty()
{
  return (spush.empty() && spop.empty());
}

template <typename T>
class QueueUsingDeque
{
public:
  void push(const T& val) { deque.emplace_back(val); }
  void pop() { deque.pop_front(); }
  T& front() { return deque.front(); }
  bool empty() { return (deque.empty()); }

private:
  std::deque<T> deque;
};

template <typename T>
class QueueUsingCircularArray
{
public:
  QueueUsingCircularArray(int sz) : sz_(sz) { vec_.resize(sz); }

  void push(const T& val)
  {
    if (full_) {
      throw "queue full";
    }
    vec_[write_idx_] = val;
    if (++write_idx_ == sz_) {
      write_idx_ = 0;
    }
    if (write_idx_ == read_idx_) {
      full_ = true;
    }
  }

  void pop()
  {
    if (empty()) {
      throw "queue empty";
    }
    if (++read_idx_ == sz_) {
      read_idx_ = 0;
    }
    full_ = false;
  }

  T& top()
  {
    if (empty()) {
      throw "queue empty";
    }
    return vec_[read_idx_];
  }

  bool empty() const { return (!full_ && read_idx_ == write_idx_); }

private:
  int sz_;
  std::vector<T> vec_;
  int read_idx_ = 0;
  int write_idx_ = 0;
  bool full_ = false;
};

template class QueueUsingCircularArray<int>;

template <typename T>
class ThreadSafeQueue1
{
public:
  T wait_pop()
  {
    std::unique_lock<std::mutex> lock(mutex_);
    cond_.wait(lock, [this] { return !queue_.empty(); });
    T val = std::move(queue_.front());
    queue_.pop();
    return val;
  }

  T pop()
  {
    std::lock_guard<std::mutex> lock(mutex_);
    if (queue_.empty()) {
      throw "queue empty";
    }
    T val = std::move(queue_.front());
    queue_.pop();
    return val;
  }

  void push(T val)
  {
    std::lock_guard<std::mutex> lock(mutex_);
    queue_.push(std::move(val));
    cond_.notify_one();
  }

  bool empty() const
  {
    std::lock_guard<std::mutex> lock(mutex_);
    return queue_.empty();
  }

private:
  std::queue<T> queue_;
  mutable std::mutex mutex_;
  std::condition_variable cond_;
};

template class ThreadSafeQueue1<int>;

template <typename T>
class ThreadSafeQueue2
{
public:
  ThreadSafeQueue2() : head(new Node), tail(head.get()) {}

  T wait_pop()
  {
    std::unique_lock<std::mutex> lock(head_mutex_);
    cond_.wait(lock, [this] { return head.get() != getTail(); });

    T val = std::move(head->val_);
    head = std::move(head->next);
    return val;
  }

  T pop()
  {
    std::lock_guard<std::mutex> lock(head_mutex_);
    if (head.get() == getTail()) {
      throw "queue empty";
    }

    T val = std::move(head->val_);
    head = std::move(head->next);
    return val;
  }

  void push(T val)
  {
    Node* node = new Node;
    std::unique_lock<std::mutex> lock(tail_mutex_);
    tail->val_ = std::move(val);
    tail->next = std::unique_ptr<Node>(node);
    tail = tail->next.get();
    lock.unlock();

    cond_.notify_one();
  }

  bool empty()
  {
    std::lock_guard<std::mutex> lock(head_mutex_);
    return (head.get() == getTail());
  }

private:
  struct Node
  {
    T val_;
    std::unique_ptr<Node> next;
  };
  std::unique_ptr<Node> head;
  Node* tail;
  std::mutex head_mutex_;
  std::mutex tail_mutex_;
  std::condition_variable cond_;

  Node* getTail()
  {
    std::lock_guard<std::mutex> tail_lock(tail_mutex_);
    return tail;
  }
};

template class ThreadSafeQueue2<int>;

int main()
{
  ThreadSafeQueue2<int> q;
  q.push(1);
  q.push(2);
  std::cout << q.pop() << "\n";
  std::cout << q.pop() << "\n";
}