Class: StackQueue

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ StackQueue

Returns a new instance of StackQueue.



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

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

Instance Attribute Details

#in ⇒ Object (readonly)

Returns the value of attribute in.



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

def in
  @in
end

#out ⇒ Object (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

#shift ⇒ Object

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