Lua Deque Implementation

#1

Hi all,

I have been making lots of interesting procedural generation gizmos recently. Some of these need more advanced data structures than a simple Lua table access, such as a Queue… or in my case, a Deque. If you have never heard of a deque, it is short for “double-ended queue.” Insertions and deletions from the front and back of the table are completed in constant time O(1).

Here is my implementation for those who are interested:

----------------------------------------------------------------------
-- DEQUE
----------------------------------------------------------------------

local util = {}

util.deque = {}

function util.deque.new()
	return { front = 0, back = -1 }
end

function util.deque.is_empty(deque)
	return deque.front > deque.back
end

function util.deque.front(deque)
	return deque[deque.front]
end

function util.deque.back(deque)
	return deque[deque.back]
end

function util.deque.push_front(deque, value)
	deque.front = deque.front - 1
	deque[deque.front] = value
end

function util.deque.pop_front(deque)
	if deque.front <= deque.back then
		local result = deque[deque.front]
		deque[deque.front] = nil
		deque.front = deque.front + 1
		return result
	end
end

function util.deque.push_back(deque, value)
	deque.back = deque.back + 1
	deque[deque.back] = value
end

function util.deque.pop_back(deque)
	if deque.front <= deque.back then
		local result = deque[deque.back]
		deque[deque.back] = nil
		deque.back = deque.back - 1
		return result
	end
end

return util

Decided to post the code in case it helps someone in the future. Happy Defolding.

14 Likes

#2

Thank you for sharing!

1 Like

#3

This is awesome, thank you!

0 Likes

#4

Great, thanks! :wink:
Maybe to add here also some other data containers, here’s an interesting collection I was using many times:

2 Likes