Class: DSA::ArrayQueue

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

Overview

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(initial_capacity = 10) ⇒ ArrayQueue

Returns a new instance of ArrayQueue.



66
67
68
69
70
 
# 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

Instance Attribute Details

#length ⇒ Object (readonly)

Returns the value of attribute length.



64
65
66
 
# File 'lib/DSA/stack_and_queue.rb', line 64

def length
  @length
end

Instance Method Details

#dequeue ⇒ Object 



79
80
81
82
83
84
85
86
87
88
 
# 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? ⇒ Boolean

Returns:

  • (Boolean) 


94
95
96
 
# File 'lib/DSA/stack_and_queue.rb', line 94

def empty?
  @length == 0
end

#enqueue(e) ⇒ Object 



72
73
74
75
76
77
 
# 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 ⇒ Object 



90
91
92
 
# File 'lib/DSA/stack_and_queue.rb', line 90

def first
  @data[@front_index]
end