minQueue.h

minQueue.h

//通过minStack.h来实现最小队列，使用两个minStack，来模拟minQueue
//当然可以直接实现minQueue，而非借助minStack
#ifndef MIN_QUEUE_H
#define MIN_QUEUE_H

#include "minStack.h"    //see https://gist.github.com/2213736
#include <functional>

//use two stack: new and old to simulate min_queue
template<typename T, typename Comparator=std::less<T> >
class MinQueue{
public:
	explicit MinQueue(Comparator c=Comparator());
	void Enqueue(const T& elem);
	void Dequeue();
	const T& Min() const;
	size_t Size() const;
	bool Empty() const;
private:
	void MoveIfNecessary();
	MinStack<T, Comparator> m_new, m_old;
	Comparator m_cmp;
};

template<typename T, typename Comparator>
MinQueue<T, Comparator>::MinQueue(Comparator c) : m_new(c), m_old(c), m_cmp(c){};

template<typename T, typename Comparator>
void MinQueue<T, Comparator>::Enqueue(const T &elem)
{
	m_new.Push(elem);
}

template<typename T, typename Comparator>
void MinQueue<T, Comparator>::Dequeue()
{
	MoveIfNecessary();
	m_old.Pop();
}

template<typename T, typename Comparator>
const T& MinQueue<T, Comparator>::Min()
{
	if (!m_new.Empty() && !m_old.Empty())
		return m_new.Min()<m_old.Min() ? m_new.Min() : m_old.Min();
	else if (!m_new.Empty())
		return m_new.Min();
	else
		return m_old.Min();
}

template<typename T, typename Comparator>
size_t MinQueue<T, Comparator>::Size() const
{
	return m_new.Size() + m_old.Size();
}

template<typename T, typename Comparator>
bool MinQueue<T, Comparator>::Empty() const
{
	return m_new.Empty() && m_old.Empty();
}

template<typename T, typename Comparator>
void MinQueue<T, Comparator>::MoveIfNecessary()
{
	if (!m_old.Empty())
		return ;

	while (!m_new.Empty())
	{
		m_old.Push(m_new.Top());
		m_new.Pop();
	}
}
#endif