Curso Noic de Informática - Estruturas de Dados 11

noic-ds11.cpp

// Curso Noic de Informática - Estruturas de Dados 11
// Minqueue - Complexidade O(1) amortizada

// A Minqueue pode facilmente ser adaptada para Maxqueue, respondendo
// o valor máximo na estrutura

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

struct MinQueue
{
	deque<pii> dq;
	int l, r;

	// inicialmente, dizemos que l = r = 1
	void init(void)
	{
		l = r = 1;
		dq.clear();
	}

	// adiciona v atrás da fila
	void push(int v)
	{
		while (!dq.empty() && v < dq.back().ff) dq.pop_back();

		dq.push({v, r}); // inserimos v com tempo r
		r++; // aumentamos o tempo r
	}

	// remove o elemento da frente da fila
	void pop(void)
	{
		if (!dq.empty() && dq.front().ss == l) dq.pop_front();

		l++; //aumentamos o tempo l
	}

	int getmin(void) {return dq.front().ff;} // retorna o valor mínimo da estrutura
};