(data structure) Circular Queues modulescript

Resources Community Resources
, ,
1

Also known as a FIFO (first in first out data structure or a Ring Buffer)
This is a basic module which allows you to implement a circular queue to any framework or system.

FYI:
This module and implementation is based from the AQA A-Level 7517 Specification 4.2 about Data structures. If you are in the UK and learn OCR or Higher GCSE computer science, this would be familiar to you as well.

How it works (don't read if you are scared of words)

A queue is known as a FIFO (First In First Out) data strucure. For example in the real world (a shopping centre:)

  • First person enters the END of the queue and the first person at the START of the queue leaves after having purchased their items.

Circular Queues (in program 1337):

Instead of a long table of , the queue round robins with ordinal (index) values storing the front and rear of the queue.

  • When an object is added, the rear value moves 1 value up (or round robins) and awaits for the next object to be queued.
  • When an object is dequeued, the front value moves 1 value up (or also round robins) and awaits for the next object (if any) to be dequeued.

The way the front and rear index values are calculated is used using the equation:

head = ((head + 1) % length_of_array) + 1
tail = ((tail + 1) % length_of_array) + 1

A circular is fixed, meaning that a limited number of objects can be stored in the given array at a time. If it is full, then the object is disregarded (because there is no space!)

Now because this is a data structure (ADT), we can store anything into it. From a string value to Instances, or your predefined object or function.

This is an animation (from Wikipedia) showing how a circular queue works:
Circular_Buffer_Animation

Linear queues:

If the array do not round robin, it is classified as a linear queue, where either all stored values would need to individually shift 1 up the table or new entries would need to be added, wasting memory space with blanks and processing time. It functionally performs the same, but worse in terms of performance.

The Circular queue data structure can be implemented in a number of ways:

  • Event task scheduling
    • Making sure an event happens one-by-one e.g. From client-server communication
    • Making sure that the previous event has fully been processed to ready the next.
  • Management and processing of data
    • Rejects requests from a service, API or event from being called too many times e.g. from a client using an autoclicker or a sloppy exploiter
  • A VIP system
    • Players that have VIP role can have their requests or events completed first (example of a Priority queue)
  • Those awful “wait in line for 8 hours while giving playtime to the scum devs” games

Personally, I am using it for event handling, making sure that the previous event is processed correctly so I wouldn’t get broken gameplay or unexpected results.

Getting and using the Circular Queues modulescript:
There is no download, Just copy the code below. It is entirely written in luau so you can just paste it to a modulescript.

GET THE CODE 
-- luau implementation of a circular queue

-- luau first index is 1

-- getting the head/tail index:
-- head = (head + 1) % maxSize
-- tail = (tail - 1 + maxSize) % maxSize

local queues = {
	null = "null" -- mark empty spaces in the queue with a known value
}
queues.__index = queues


queues.new = function(maxEntries : number)
	local self = {}
	setmetatable(self,queues)
	self._maxentries = maxEntries
	self._queue = table.create(maxEntries,queues.null)
	self._head = 1
	self._tail = 1
	return self
end

function queues:currentQueue() -- get the cloned queue table with all current values
	return table.clone(self._queue)
end

function queues:enqueue(value) -- add a value or object to the end of the queue
	if self:isQueueFull() == false then
		self._queue[self._tail] = value
		self._tail = ((self._tail + 1) % self._maxentries) + 1
		print(self._tail)
	end
end

function queues:dequeue() -- retrieve and remove the value/object from the queue
	if self:isQueueEmpty() == false then
		local currentObject = self._queue[self._head]
		self._queue[self._head] = queues.null
		self._head = ((self._head + 1) % self._maxentries) + 1
		return currentObject
	end
end

function queues:peek() -- get the first value from the object
	local value = self._queue[self._head]
	if value ~= queues.null then
		return value
	end
end

function queues:isQueueFull() -- check if the queue is full (get current entries in queue == maxEntries)
	local count = self:getQueueLength()
	return count == self._maxentries or false
end

function queues:isQueueEmpty()
	local count = self:getQueueLength()
	return count == 0 or false
end

function queues:getQueueLength() -- get the amount of values currently in the queue
	local count = 0
	for _,value in self._queue do
		if value ~= queues.null then
			count += 1
		end
	end
	return count
end

return queues

From another script (local or server), require the module ready for you to use:
local queue = require(path.to.your.modulescript)
Create a queue object with 5 max entries:
local my_Queue = queue.new(5)
Add three strings to the queue:

my_Queue:enqueue("Life")
my_Queue:enqueue("Is")
my_Queue:enqueue("Roblox")

And finally, remove the first strings off the queue:

print(my_Queue:dequeue())
print(my_Queue:dequeue())
 >> Life
 >> Is

DONE!!!

Full description of functions:
Constructor or value Description
peek() : any (if any) Returns the value WITHOUT removing the value.
new(max_entries : number) : queues Create a new Queue object with the specified entries
isQueueFull() : boolean Returns TRUE if the queue is full
isQueueEmpty() : boolean returns TRUE if the queue is empty
getQueueLength() : number returns the amount of values waiting in the queue
enqueue(value : any) : nil Adds a value, object or function into the queue
dequeue() : any (if any) Removes the value from the queue and returns it
currentQueue() : table Returns the cloned table of the queue with all its stored values (no head or tail data)

What does this mean to ME??? - An average Roblox Developer
You probably don’t know it, but you are already using a queue system while developing on ROBLOX. For instance, ZIndex is an example of a Queue, where you can specify when GUI elements should be rendered first or last. Lower the number, It is rendered first.

4 Likes