class MarsBase10::Stack

Attributes

head[RW]
length[RW]
tail[RW]

Public Class Methods

new() click to toggle source

Initialize an empty stack. Complexity: O(1).

# File lib/mars_base_10/stack.rb, line 22
def initialize
  self.head   = nil
  self.tail   = nil
  self.length = 0
end

Public Instance Methods

clear() click to toggle source

Pops all elements from the stack. Complexity O(n).

# File lib/mars_base_10/stack.rb, line 30
def clear
  while peek
    pop
  end
end
each() { |current| ... } click to toggle source

Enumerator (common ruby idiom). Loops over the stack (from head to tail) yielding one item at a time. Complexity: yield next element is O(1),

yield all elements is O(n).
# File lib/mars_base_10/stack.rb, line 40
def each
  return nil unless block_given?

  current = self.head
  while current
    yield current
    current = current.next
  end
end
peek() click to toggle source

Returns the element that’s at the top of the stack without removing it. Complexity O(1).

# File lib/mars_base_10/stack.rb, line 52
def peek
  self.head
end
pop() click to toggle source

Removes the element that’s at the top of the stack. Complexity O(1).

# File lib/mars_base_10/stack.rb, line 68
def pop
  return nil unless self.length > 0
  n = self.head
  self.head = self.head.next
  self.tail = nil if self.length == 1
  self.length -= 1
  n.data
end
print() click to toggle source

Prints the contents of the stack. Complexity: O(n).

push(data) click to toggle source

Inserts a new element into the stack. Complexity O(1).

# File lib/mars_base_10/stack.rb, line 79
def push data
  node = Node.new data
  if length == 0
    self.tail = node
  end

  node.next = self.head
  self.head = node
  self.length += 1
end