class Queue
Queue
data structure Worst-Case Space Complexity: O(n)
Public Class Methods
new(size, data_set=[])
click to toggle source
# File lib/algorithm_selector.rb, line 358 def initialize(size, data_set=[]) @size = size @store = Array.new(@size) @head, @tail = -1, 0 # initialize Queue with data_set if given data_set.each { |el| enqueue(el) } end
Public Instance Methods
dequeue()
click to toggle source
# File lib/algorithm_selector.rb, line 377 def dequeue if empty? nil else @tail = @tail.succ dequeued = @store[@head] @store.unshift(nil) @store.pop dequeued end end
enqueue(el)
click to toggle source
Insertion, Worst-Case Time Complexity: O(1)
# File lib/algorithm_selector.rb, line 390 def enqueue(el) if full? or el.nil? nil else @tail = @tail.pred @store[@tail] = el self end end
look()
click to toggle source
# File lib/algorithm_selector.rb, line 404 def look @store[@head] end
search(target)
click to toggle source
Search, Worst-Case Time Complexity: O(n)
# File lib/algorithm_selector.rb, line 368 def search(target) found = false @size.times do found = true if look == target enqueue(dequeue) end found end
size()
click to toggle source
# File lib/algorithm_selector.rb, line 400 def size @size end
Private Instance Methods
empty?()
click to toggle source
# File lib/algorithm_selector.rb, line 410 def empty? @head == -1 and @tail == 0 end
full?()
click to toggle source
# File lib/algorithm_selector.rb, line 414 def full? @tail.abs == (@size) end