Class: MinMaxQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/min_max_queue.rb

Instance Method Summary collapse

Constructor Details

#initializeMinMaxQueue

Returns a new instance of MinMaxQueue.


4
5
6
# File 'lib/min_max_queue.rb', line 4

def initialize
  @in, @out = MinMaxStack.new, MinMaxStack.new
end

Instance Method Details

#flip!Object


36
37
38
# File 'lib/min_max_queue.rb', line 36

def flip!
  @in.length.times { @out.push(@in.pop) }
end

#maxObject

O(1)


21
22
23
24
25
26
# File 'lib/min_max_queue.rb', line 21

def max
  return @in.max if @out.length == 0
  return @out.max if @in.length == 0

  @in.max > @out.max ? @in.max : @out.max
end

#minObject

O(1)


29
30
31
32
33
34
# File 'lib/min_max_queue.rb', line 29

def min
  return @in.min if @out.length == 0
  return @out.min if @in.length == 0

  @in.min < @out.min ? @in.min : @out.min
end

#push(val) ⇒ Object

O(1)


9
10
11
# File 'lib/min_max_queue.rb', line 9

def push(val)
  @in.push(val)
end

#shiftObject

O(1) amortized


14
15
16
17
18
# File 'lib/min_max_queue.rb', line 14

def shift
  flip! if @out.length == 0

  @out.pop
end