Deque Implementation

Resources Community Resources
#1

Although deque data structures may not have many applications in game development, I recently needed one for a project and decided to implement it. Since I couldn’t find any existing implementations, I created one and am sharing it here for others who might find it useful.

Example Usage
The module is fairly easy to use, and you should be able to integrate it by looking at the source code. Here’s an example to get you started:

local deque = require(game.ReplicatedStorage.Deque)
local myDeque = deque.New()

myDeque:PushFront("data1") --[data1]
myDeque:PushFront("data2") --[data2, data1]
myDeque:PushRear("data3") --[data2, data1, data3]
myDeque:PopFront() --[data1, data3]

Here is the link to the model.

Code 
local deque = {}
local dequeMetatable = {}

dequeMetatable.__index = dequeMetatable

local function newNode(v)
	return { Value = v, Next = nil, Prev = nil }
end

deque.New = function()
	local contents = {
		Front = nil,
		Rear = nil,
		Size = 0
	}
	setmetatable(contents, dequeMetatable)

	return contents
end

function dequeMetatable:IsEmpty()
	return self.Size == 0
end

function dequeMetatable:Clear()
	self.Front = nil
	self.Rear = nil
	self.Size = 0
end

function dequeMetatable:GetSize()
	return self.Size
end

function dequeMetatable:PeekFront()
	return self.Front and self.Front.Value
end

function dequeMetatable:PeekRear()
	return self.Rear and self.Rear.Value
end

function dequeMetatable:PushFront(v: any)
	local node = newNode(v)
	local front = self.Front
	
	if front then
		node.Prev = front
		self.Front.Next = node
		self.Front = node
	else
		self.Front = node
		self.Rear = node
	end
	self.Size += 1
end

function dequeMetatable:PushRear(v: any)
	local node = newNode(v)
	local rear = self.Rear

	if rear then
		node.Next = rear
		self.Rear.Prev = node
		self.Rear = node
	else
		self.Front = node
		self.Rear = node
	end
	self.Size += 1
end

function dequeMetatable:PopFront()
	local front = self.Front

	if front then
		if front.Prev then
			front.Prev.Next = nil
			self.Front = front.Prev
		else
			self.Front = nil
			self.Rear = nil
		end
		self.Size -= 1
		return front.Value
	else
		return nil
	end

end

function dequeMetatable:PopRear()
	local rear = self.Rear

	if rear then
		if rear.Next then
			rear.Next.Prev = nil
			self.Rear = rear.Next
		else
			self.Front = nil
			self.Rear = nil
		end
		self.Size -= 1
		return rear.Value
	else
		return nil
	end
end

function dequeMetatable:IterateFront(func: (any) -> (any))
	local front = self.Front
	while front do
		func(front)
		front = front.Prev
	end
end

function dequeMetatable:IterateRear(func: (any) -> (any))
	local rear = self.Rear
	while rear do
		func(rear)
		rear = rear.Next
	end
end

return deque
3 Likes