Deque or double-ended queue

May 09, 2024

Deque is very similar to queue, but with one significant difference: elements can be added or removed from both sides. In other meaning deque and queue are very similar and usually serve the same purposes.

Usually, deque implements 4 methods:

pushFront - adds an element into the front of the queue;
popFront - removes an element from the front of the queue;
pushEnd - adds an element to the end of the queue;
popEnd - removes an element from the end of the queue;

Figure 01: Deque illustration

Implementation of the deque using table is very simple in Lua.

-- create deque as empty table
local deque = {}

-- push front
table.insert(deque, 1, "B")
table.insert(deque, 1, "A")

-- push back
table.insert(deque, "C")
table.insert(deque, "D")

--pop front
print(table.remove(deque, 1)) --> "A"

--pop back
print(table.remove(deque)) --> "D"

-- traverse
for i, v in ipairs(deque) do
    print(i, v)
end
-- Output:
-- 1    "B"
-- 2    "C"

But it also has the same disadvantage as queue does. If we remove or add a new element to the front, 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 (10⁶), every index will be recalculated 10⁶-1 times. This is very inefficient. Let’s implement a wrapper class for the queue with complexity O(1).

Deque class¶

Class implementation with OOP principles and annotations.

Deque.lua

---@class Deque
---@field private _first number
---@field private _last number
local Deque = {}
Deque.__index = Deque

---@return Deque
function Deque:new()
    local t = {
        _first = 0,
        _last = -1,
    }
    return setmetatable(t, self)
end

---@param v any
function Deque:pushFront(v)
    local first = self._first - 1
    self._first = first
    self[first] = v
end
--
---@return any
function Deque:popFront()
    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
    return v
end

---@param v any
function Deque:pushBack(v)
    local last = self._last + 1
    self._last = last
    self[last] = v
end
--
---@return any
function Deque:popBack()
    if self:isEmpty() then
        return nil
    end
    local last = self._last
    local v = self[last]
    self[last] = nil -- garbage collection removes it
    self._last = self._last - 1
    return v
end

---@return boolean
function Deque:isEmpty()
    return self._first > self._last
end

---@return any
function Deque:front()
    return self[self._first]
end

---@return any
function Deque:rear()
    return self[self._last]
end

---@params sep? string
---@return string
function Deque:toString(sep)
    sep = sep or ","
    local t = {}
    for i = self._first, self._last do
        t[#t + 1] = self[i]
    end
    return table.concat(t, sep)
end

return Deque

Usage of Deque class¶

local dq = Deque:new()
dq:pushFront("C")
dq:pushFront("B")
dq:pushFront("A")
dq:pushBack("D")
dq:pushBack("E")
dq:pushBack("F")

print(dq:front(), dq:rear()) --> "A"    "F"
print(dq:popFront()) --> "A"
print(dq:popBack()) --> "F""
print(dq:toString()) --> "B,C,D,E""

References¶

Wikipedia: Double-ended queue

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.