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 pathQueue.lua
More file actions
153 lines (122 loc) · 2.84 KB
/
Copy pathQueue.lua
File metadata and controls
153 lines (122 loc) · 2.84 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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
local queue = {}
queue.LinkedListQueue = {}
queue.LinkedListQueue.__index = queue.LinkedListQueue
queue.Node = {}
queue.Node.__index = queue.Node
function queue.Node.create(value)
local s = {}
setmetatable(s, queue.Node)
s.value = value
s.next = nil
return s
end
function queue.LinkedListQueue.create()
local s = {}
setmetatable(s, queue.LinkedListQueue)
s.first = nil
s.last = nil
s.N = 0
return s
end
function queue.create()
return queue.LinkedListQueue.create()
end
function queue.LinkedListQueue:enqueue(value)
local oldLast = self.last
self.last = queue.Node.create(value)
if oldLast ~= nil then
oldLast.next = self.last
end
if self.first == nil then
self.first = self.last
end
self.N = self.N + 1
end
function queue.LinkedListQueue:dequeue()
local oldFirst = self.first
if oldFirst == nil then
return nil
end
self.first = oldFirst.next
local value = oldFirst.value
if self.first == nil then
self.last = nil
end
self.N = self.N - 1
return value
end
function queue.LinkedListQueue:size()
return self.N
end
function queue.LinkedListQueue:isEmpty()
return self.N == 0
end
function queue.LinkedListQueue:enumerate()
local index = 0
local temp = {}
local x = self.first
while x ~= nil do
local value = x.value
temp[index] = value
index = index + 1
x = x.next
end
return temp
end
queue.ArrayQueue = {}
queue.ArrayQueue.__index = queue.ArrayQueue
function queue.ArrayQueue.create()
local s = {}
setmetatable(s, queue.ArrayQueue)
s.head = 0
s.tail = 0
s.a = { nil }
s.aLen = 0
return s
end
function queue.ArrayQueue:enqueue(value)
self.a[self.tail] = value
self.tail = self.tail + 1
if self.tail - self.head == self.aLen then
self:resize(self.aLen * 2)
end
end
function queue.ArrayQueue:size()
return self.tail - self.head
end
function queue.ArrayQueue:isEmpty()
return self.tail == self.head
end
function queue.ArrayQueue:dequeue(value)
if self.tail == self.head then
return nil
end
value = self.a[self.head]
self.head = self.head + 1
if self.tail - self.head == math.floor(self.aLen / 4) then
self:resize(math.floor(self.aLen / 2))
end
return value
end
function queue.ArrayQueue:resize(newSize)
local temp = {}
for i = 0,(newSize-1) do
if i < self.tail - self.head then
temp[i] = nil
else
temp[i] = self.a[i + self.head]
end
end
self.a = temp
self.aLen = newSize
self.tail = self.tail - self.head
self.head = 0
end
function queue.ArrayQueue:enumerate()
local temp = {}
for i = self.head,self.tail-1 do
temp[i - self.head] = self.a[i]
end
return temp
end
return queue