class Stack
Stack
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 293 def initialize(size, data_set=[]) @size = size @store = Array.new(@size) @top = -1 data_set.each { |el| push(el) } end
Public Instance Methods
empty?()
click to toggle source
# File lib/algorithm_selector.rb, line 350 def empty? @top == -1 end
full?()
click to toggle source
# File lib/algorithm_selector.rb, line 346 def full? @top == (@size - 1) end
look()
click to toggle source
# File lib/algorithm_selector.rb, line 342 def look @store[@top] end
pop()
click to toggle source
# 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)
click to toggle source
Insertion, Worst-Case Time Complexity: O(1)
# 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)
click to toggle source
Search, Average-Case Time Complexity: O(n) Search, Worst-Case Time Complexity: O(n)
# 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()
click to toggle source
# File lib/algorithm_selector.rb, line 338 def size @size end