Class: Queue

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

Overview

Queue data structure Worst-Case Space Complexity: O(n)

Instance Method Summary collapse

Constructor Details

#initialize(size, data_set = []) ⇒ Queue

Returns a new instance of Queue.



358
359
360
361
362
363
364
365
 
# 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

Instance Method Details

#dequeue ⇒ Object 



377
378
379
380
381
382
383
384
385
386
387
 
# 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) ⇒ Object

Insertion, Worst-Case Time Complexity: O(1)



390
391
392
393
394
395
396
397
398
 
# 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 ⇒ Object 



404
405
406
 
# File 'lib/algorithm_selector.rb', line 404

def look
  @store[@head]
end

#search(target) ⇒ Object

Search, Worst-Case Time Complexity: O(n)



368
369
370
371
372
373
374
375
 
# 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 ⇒ Object 



400
401
402
 
# File 'lib/algorithm_selector.rb', line 400

def size
  @size
end