Monotonic Queue (Min Queue)
(data-structure/others/MonotonicMinQueue.hpp)

• View this file on GitHub
• Last update: 2025-12-17 00:38:44+09:00
• Include: #include "data-structure/others/MonotonicMinQueue.hpp"

概要

todo

計算量

todo

Required by

• Longest Common Substring (string/LongestCommonSubstring.hpp)

Verified with

• verify/LibraryChecker/string/LongestCommonSubstring.test.cpp

Code

template <class T>
class MonotonicMinQueue {
 private:
  queue<T> que;
  deque<T> deq;

 public:
  void push(const T& x) {
    que.push(x);
    while (deq.size() > 0 and deq.back() > x) deq.pop_back();
    deq.push_back(x);
  }

  void pop() {
    if (que.front() == deq.front()) deq.pop_front();
    que.pop();
  }

  const T& front() const {
    return que.front();
  }

  bool empty() const {
    return que.empty();
  }

  const T& minimum() const {
    return deq.front();
  }
};

#line 1 "data-structure/others/MonotonicMinQueue.hpp"
template <class T>
class MonotonicMinQueue {
 private:
  queue<T> que;
  deque<T> deq;

 public:
  void push(const T& x) {
    que.push(x);
    while (deq.size() > 0 and deq.back() > x) deq.pop_back();
    deq.push_back(x);
  }

  void pop() {
    if (que.front() == deq.front()) deq.pop_front();
    que.pop();
  }

  const T& front() const {
    return que.front();
  }

  bool empty() const {
    return que.empty();
  }

  const T& minimum() const {
    return deq.front();
  }
};

Back to top page