MinQueue.cpp

template <typename T>
class MinQueue {
 public:
  void Push(const T& value) {
    queue_.push(value);
    while (min_queue_.size() > 0 && min_queue_.back() > value) min_queue_.pop_back();
    min_queue_.push_back(value);
  }

  void Pop() {
    if (queue_.front() == min_queue_.front()) min_queue_.pop_front();
    queue_.pop();
  }

  const T& Front() const { return queue_.front(); }
  const T& Min() const { return min_queue_.front(); }

 private:
  std::queue<T> queue_;
  std::deque<T> min_queue_;
};