algorithm - Keep track on biggest element in FIFO queue -

this question has answer here:

• stack find-min/find-max more efficient o(n)? 4 answers

problem

• i have fixed length fifo queue of integer values.
• everytime push new value it, oldest 1 removed.
• queue must able tell, after every insertion & removal operation, biggest value in it.

question

is there algorithm better doing loop on queue elements every time?

after accept update

because of limited domain of integers in application, thinking sparse histogram, containing counts of given value in queue. every time value arrives increment value in histogram, , decrement when given value removed. max/min need first/last histogram index non 0 count.

in fact due specific structure of problem possible o(1) amortized operations, better using max-heap. application sliding window minimum algorithm. keep second queue contains decreasing subsequence of suffix maxima:

queue = new queue() mono = new queue() cnt = 0  def enqueue(x):  # o(1) amortized   while !mono.empty() , x >= mono.back()[1]:     mono.pop_back()   queue.push_back([x, cnt])   mono.push_back([x, cnt])   cnt++  def dequeue():   # o(1)    if mono.front()[0] == queue.front()[0]:     mono.pop_front()   return q.pop_front()  def max():  # o(1)   return mono.front()[1]