Skip to content

Instantly share code, notes, and snippets.

@takei-yuya

takei-yuya/MinQueue.cpp Secret

Created Apr 28, 2020
Embed
What would you like to do?
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_;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.