1def assert_equal(x, y)
 2  raise [x, y].inspect unless x == y
 3end
 4
 5class MaxStack
 6  def initialize
 7    @items = []
 8    @maxes = []
 9  end
10
11  def push(value)
12    if @maxes.empty? || value > @maxes[-1]
13      @maxes.push(value)
14    end
15    @items.push(value)
16  end
17
18  def pop
19    result = @items.pop
20    @maxes.pop if result == @maxes[-1]
21    result
22  end
23
24  # time: O(1)
25  # space: O(1)
26  def max
27    @maxes[-1]
28  end
29end
30
31stack = MaxStack.new
32stack.push(1)
33stack.push(2)
34stack.push(3)
35stack.push(2)
36
37assert_equal 3, stack.max
38
39stack.pop
40stack.pop
41assert_equal 2, stack.max
42
43puts 'Yay!'