This repository was archived by the owner on Sep 7, 2025. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathStack.lua
More file actions
135 lines (105 loc) · 2.34 KB
/
Copy pathStack.lua
File metadata and controls
135 lines (105 loc) · 2.34 KB
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
local stack = {}
stack.Node = {}
stack.Node.__index = stack.Node
function stack.Node.create(value)
local s = {}
setmetatable(s, stack.Node)
s.value = value
s.next = nil
return s
end
stack.LinkedListStack = {}
stack.LinkedListStack.__index = stack.LinkedListStack
function stack.LinkedListStack.create()
local s = {}
setmetatable(s, stack.LinkedListStack)
s.first = nil
s.N = 0
return s
end
function stack.create()
return stack.LinkedListStack.create()
end
function stack.LinkedListStack:push(value)
local oldFirst = self.first
self.first = stack.Node.create(value)
self.first.next = oldFirst
self.N = self.N + 1
end
function stack.LinkedListStack:pop()
local oldFirst = self.first
if oldFirst == nil then
return nil
end
local value = oldFirst.value
self.first = oldFirst.next
self.N = self.N - 1
return value
end
function stack.LinkedListStack:size()
return self.N
end
function stack.LinkedListStack:isEmpty()
return self.N == 0
end
function stack.LinkedListStack:enumerate()
local x = self.first
local index = 0
local temp = {}
while x ~= nil do
temp[index] = x.value
index = index + 1
x = x.next
end
return temp
end
stack.ArrayStack = {}
stack.ArrayStack.__index = stack.ArrayStack
function stack.ArrayStack.create()
local s = {}
setmetatable(s, stack.ArrayStack)
s.a = { nil }
s.N = 0
s.aLen = 1
return s
end
function stack.ArrayStack:push(value)
self.a[self.N] = value
self.N = self.N + 1
if self.N == self.aLen then
self:resize(self.aLen * 2)
end
end
function stack.ArrayStack:resize(newSize)
local temp = {}
for i = 0,(newSize-1) do
temp[i] = self.a[i]
end
self.a = temp
self.aLen = newSize
end
function stack.ArrayStack:pop()
if self.N == 0 then
return nil
end
local value = self.a[self.N-1]
self.N = self.N - 1
if self.N == math.floor(self.aLen / 4) then
self:resize(math.floor(self.aLen / 2))
end
return value
end
function stack.ArrayStack:size()
return self.N
end
function stack.ArrayStack:isEmpty()
return self.N == 0
end
function stack.ArrayStack:enumerate()
local temp = {}
for i = 0,(self.N-1) do
temp[i] = self.a[i]
end
return temp
end
return stack