Class: StackQueue

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initializeStackQueue

Returns a new instance of StackQueue.


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

def initialize
  @in, @out = [], []
end

Instance Attribute Details

#inObject (readonly)

Returns the value of attribute in


3
4
5
# File 'lib/stack_queue.rb', line 3

def in
  @in
end

#outObject (readonly)

Returns the value of attribute out


3
4
5
# File 'lib/stack_queue.rb', line 3

def out
  @out
end

Instance Method Details

#flip!Object

O(n)


23
24
25
26
27
# File 'lib/stack_queue.rb', line 23

def flip!
  @in.length.times do
    @out << @in.pop
  end
end

#push(val) ⇒ Object

O(1) ammortized


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

def push(val)
  @in << val
end

#shiftObject

WC: O(n)


14
15
16
17
18
19
20
# File 'lib/stack_queue.rb', line 14

def shift
  if @out.empty?
    flip!
  end

  @out.pop
end