-
Notifications
You must be signed in to change notification settings - Fork 0
/
stack.rb
118 lines (93 loc) · 1.83 KB
/
stack.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
# Algorithms, Part I, Week 2, Stacks and Queues
# Linked-list implementation of stack
class Stack
attr_accessor :first
def initialize
self.first = nil
end
def push(item)
oldfirst = first
self.first = Node.new
first.item = item
first.next = oldfirst
end
def pop
raise if is_empty?
item = first.item
self.first = first.next
item
end
def is_empty?
first.nil?
end
def each(&block)
current_node = first
while (current_node)
block.call(current_node)
current_node = current_node.next
end
end
private
# inner class
class Node
attr_accessor :item, :next
end
end
# Fixed-capacity array implementation of stack
class FixedCapacityStack
attr_accessor :stack, :idx
def initialize(capacity)
self.stack = Array.new(capacity)
self.idx = 0
end
def is_empty?
idx == 0
end
def push(item)
stack[idx] = item
self.idx += 1
end
def pop
raise if is_empty?
self.idx -= 1
item = stack[idx]
stack[idx] = nil
item
end
end
# Resizing array implementation of stack
class ResizingArray
attr_accessor :stack, :idx
def initialize
self.stack = Array.new(1)
self.idx = 0
end
def is_empty?
idx == 0
end
def push(item)
# double the size of array when full
resize(stack.length * 2) if idx == stack.length
stack[idx] = item
self.idx += 1
end
def pop
raise if is_empty?
self.idx -= 1
item = stack[idx]
stack[idx] = nil
# halve size of array when one-quater full
if idx > 0 && idx == (stack.length/4)
resize(stack.length / 2)
end
item
end
def resize(capacity)
copy = Array.new(capacity)
(0..capacity-1).each { |idx| copy[idx] = stack[idx] }
self.stack = copy
end
def each(&block)
stack.each { |item| block.call(item) }
end
end