Queue
Queue is one of the simple data structures, usually used in more complex algorithms as temporary data storage. The queue is the linear FIFO data structure, all operations with the queue have O(1) complexity. Entries in the queue in a sequence can be modified by the enqueueing of entities at one end of the sequence and the removal of entities from the other end of the sequence.
There are 2 mandatory queue operations:
- enqueue - adds an element into the rear of the queue;
- dequeue - removes an element from the front of the queue;
Also might include additional, but not mandatory:
- rear - returns the last element in the queue;
- front - returns the first element in the queue;
- empty - checks if the queue is empty;
- full - checks if the queue is full (usually tables in Lua do not have adequate limits);
- toString - converts the queue to the string;
In Lua queue can be implemented just with a table out-of-box.
Warning
Adding nil to the queue means the end of the table and Lua iterators might work not as you expected. My general rule is never to add nil values inside any table or structure.
-- Create queue as table
local queue = {}
-- enqueue
queue[#queue + 1] = 'A'
queue[#queue + 1] = 'B'
queue[#queue + 1] = 'C'
-- front
print(queue[1]) --> "A"
-- rear
print(queue[#queue]) --> "C"
-- size
print(#queue) --> 3
-- dequeue
print(table.remove(queue, 1)) --> "A"
-- is empty
if queue[1] == nil then
print("Queue is empty")
else
print("Queue is not empty")
end
In the above example, there is a large drawback. On the enqueue indexes for the next elements after the first should be recalculated. This is how table.remove method works. In this case, the complexity will be O(n-1). Let’s assume there are one million records (106), every index will be recalculated 106-1 times. This is very inefficient.
Let’s implement a wrapper class for the queue with complexity O(1).
Queue class¶
Class implementation with OOP principles and annotations.
Queue.lua
---@class Queue
---@field private _first number
---@field private _last number
---@field private _size number
local Queue = {}
Queue.__index = Queue
---@return Queue
function Queue:new()
local t = {
_first = 0,
_last = -1,
_size = 0,
}
return setmetatable(t, self)
end
---@param v any
function Queue:enqueue(v)
local last = self._last + 1
self._last = last
self[last] = v
self._size = self._size + 1
end
---@return any
function Queue:dequeue()
if self:isEmpty() then
return nil
end
local first = self._first
local v = self[first]
self[first] = nil -- garbage collection removes it
self._first = self._first + 1
self._size = self._size - 1
return v
end
---@return boolean
function Queue:isEmpty()
return self._first > self._last
end
---@return any
function Queue:front()
return self[self._first]
end
---@return any
function Queue:rear()
return self[self._last]
end
---@return number
function Queue:size()
return self._size
end
---@params sep? string
---@return string
function Queue:toString(sep)
sep = sep or ","
local t = {}
for i = self._first, self._last do
t[#t + 1] = tostring(self[i])
end
return table.concat(t, sep)
end
return Queue
Usage of Queue class¶
local q = Queue:new()
print(q:isEmpty()) --> true
q:enqueue(11)
q:enqueue(22)
q:enqueue(33)
print(q:isEmpty()) --> false
print(q:toString()) --> "11,22,33"
print(q:size()) --> 3
print(q:front(), q:rear()) --> 11, 33
print(q:dequeue()) --> 11
print(q:dequeue()) --> 22
print(q:dequeue()) --> 33
print(q:dequeue()) --> nil
print(q:isEmpty()) --> false
References¶
Feedback
For feedback, please check the contacts section. Before writing, please specify where you came from and who you are. Sometimes spammers go insane. Thank you in advance for your understanding.