class DSA::ArrayQueue
Typically, array is not a good idea to implement a queue, as it requires linear time to shift other elements after dequeue We can try to avoid the shifting by keep track of the index of the front queue element and make the array circular
Attributes
length[R]
Public Class Methods
new(initial_capacity = 10)
click to toggle source
# File lib/DSA/stack_and_queue.rb, line 66 def initialize(initial_capacity = 10) @data = Array.new initial_capacity @front_index = 0 @length = 0 end
Public Instance Methods
dequeue()
click to toggle source
# File lib/DSA/stack_and_queue.rb, line 79 def dequeue shrink if @length - 1 < capacity / 2 and capacity / 2 >= 10 return nil if @length == 0 next_front = (@front_index + 1 ) % capacity value = @data[@front_index] @data[@front_index] = nil @front_index = next_front @length -= 1 value end
empty?()
click to toggle source
# File lib/DSA/stack_and_queue.rb, line 94 def empty? @length == 0 end
enqueue(e)
click to toggle source
# File lib/DSA/stack_and_queue.rb, line 72 def enqueue(e) grow if @length+1 == capacity @length += 1 index = (@front_index + @length - 1 ) % capacity @data[index] = e end
first()
click to toggle source
# File lib/DSA/stack_and_queue.rb, line 90 def first @data[@front_index] end
Private Instance Methods
capacity()
click to toggle source
# File lib/DSA/stack_and_queue.rb, line 99 def capacity @data.length end
copy_to(new_data)
click to toggle source
# File lib/DSA/stack_and_queue.rb, line 113 def copy_to(new_data) (0..@length-1).each do |i| old_index = (@front_index + i) % capacity new_data[i] = @data[old_index] end @data = new_data @front_index = 0 end
grow()
click to toggle source
# File lib/DSA/stack_and_queue.rb, line 103 def grow new_data = Array.new capacity * 2 copy_to new_data end
shrink()
click to toggle source
# File lib/DSA/stack_and_queue.rb, line 108 def shrink new_data = Array.new capacity / 2 copy_to new_data end