Class: Stack

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

Overview

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

Instance Method Summary collapse

Constructor Details

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

Returns a new instance of Stack.



293
294
295
296
297
298
 
# File 'lib/algorithm_selector.rb', line 293

def initialize(size, data_set=[])
  @size = size
  @store = Array.new(@size)
  @top = -1
  data_set.each { |el| push(el) }
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


350
351
352
 
# File 'lib/algorithm_selector.rb', line 350

def empty?
  @top == -1
end

#full? ⇒ Boolean

Returns:

  • (Boolean) 


346
347
348
 
# File 'lib/algorithm_selector.rb', line 346

def full?
  @top == (@size - 1)
end

#look ⇒ Object 



342
343
344
 
# File 'lib/algorithm_selector.rb', line 342

def look
  @store[@top]
end

#pop ⇒ Object 



316
317
318
319
320
321
322
323
324
325
 
# File 'lib/algorithm_selector.rb', line 316

def pop
  if empty?
    nil
  else
    popped = @store[@top]
    @store[@top] = nil
    @top = @top.pred
    popped
  end
end

#push(el) ⇒ Object

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



328
329
330
331
332
333
334
335
336
 
# File 'lib/algorithm_selector.rb', line 328

def push(el)
  if full? or el.nil?
    nil
  else
    @top = @top.succ
    @store[@top] = el
    self
  end
end

#search(target) ⇒ Object

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



302
303
304
305
306
307
308
309
310
311
312
313
314
 
# File 'lib/algorithm_selector.rb', line 302

def search(target)
  found = false
  new_stack = Stack.new(@size)
  until empty? do
    new_stack.push(pop)
    if new_stack.look == target
      found = true
      break
    end
  end
  push(new_stack.pop) until new_stack.empty?
  found
end

#size ⇒ Object 



338
339
340
 
# File 'lib/algorithm_selector.rb', line 338

def size
  @size
end