Class: MarsBase10::Stack

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

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Stack

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



22
23
24
25
26
 
# File 'lib/mars_base_10/stack.rb', line 22

def initialize
  self.head   = nil
  self.tail   = nil
  self.length = 0
end

Instance Attribute Details

#head ⇒ Object

Returns the value of attribute head.



18
19
20
 
# File 'lib/mars_base_10/stack.rb', line 18

def head
  @head
end

#length ⇒ Object

Returns the value of attribute length.



18
19
20
 
# File 'lib/mars_base_10/stack.rb', line 18

def length
  @length
end

#tail ⇒ Object

Returns the value of attribute tail.



18
19
20
 
# File 'lib/mars_base_10/stack.rb', line 18

def tail
  @tail
end

Instance Method Details

#clear ⇒ Object

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



30
31
32
33
34
 
# File 'lib/mars_base_10/stack.rb', line 30

def clear
  while peek
    pop
  end
end

#each ⇒ Object

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).



40
41
42
43
44
45
46
47
48
 
# 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 ⇒ Object

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



52
53
54
 
# File 'lib/mars_base_10/stack.rb', line 52

def peek
  self.head
end

#pop ⇒ Object

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



68
69
70
71
72
73
74
75
 
# 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 ⇒ Object

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



58
59
60
61
62
63
64
 
# File 'lib/mars_base_10/stack.rb', line 58

def print
  if self.length == 0
    puts "empty"
  else
    self.each { |node| puts node.data }
  end
end

#push(data) ⇒ Object

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



79
80
81
82
83
84
85
86
87
88
 
# 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