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