Se io e @filippos intendiamo la stessa cosa, puoi ignorare la questione degli stack e usare direttamente una deque, che è già implementata nella stl.
Vediamo se riesco a spiegare rapidamente come funziona una minqueue (la maxqueue funziona in modo analogo).
L’obiettivo è quello di realizzare una struttura dati che, scorrendo lungo una lista (o qualsiasi altra struttura lineare) di valori, ci permetta di ottenere il minimo dell’intervallo corrente in un tempo decente.
Quello che possiamo fare è mantenere una coda di “possibili candidati”, ovvero tutti e solo i valori che possono essere minimi dell’intervallo corrente. Manteniamo quindi una deque di pair<indice, valore> che aggiorneremo come necessario, in particolare mantenendo tutti gli elementi inseriti in ordine.
Vediamo le singole operazioni:
-Inserimento. Prima di tutto eliminiamo dalla fine della coda tutti gli elementi che hanno valore maggiore dell’elemento corrente, e inseriamolo (ovviamente come coppia indice-valore). Questo ci garantisce l’ordinamento della deque, e inoltre siamo sicuri che nessuno degli elementi rimossi poteva essere il minimo perché erano tutti maggiori dell’elemento appena inserito.
-Avanzamento. Quando spostiamo la nostra “finestra” in avanti lungo l’array, dobbiamo avere un modo per eliminare gli elementi dell’array che escono dalla finestra. Per spostare la fine della finestra fino ad una posizione p, eliminiamo dalla testa della deque tutti gli elementi che hanno indice minore di p. È garantito che quelli da togliere siano tutti in testa perché li inseriamo sequenzialmente dalla fine della deque.
-Richiesta del minimo. Visto che abbiamo mantenuto l’invariante che gli elementi della deque sono in ordine debolmente crescente dalla testa verso la coda, per ottenere il minimo basta prendere il valore dell’elemento in testa alla coda.
EDIT. Quasi dimenticavo, non ho dimostrato la complessità di esecuzione. Brevemente, ogni elemento dell’array entra ed esce dalla minqueue al più una volta, quindi la complessità è O(N) su tutto l’array, che diventa O(1) ammortizzato per ogni elemento.
Spero di non aver sparato qualche stupidaggine, in caso correggetemi 
Dario