Lua - Arrays as Queue

The queue is a very important data structure that operates on the principle of First-In-First-Out (FIFO). It represents a collection of elements where the elements maintain the order in which they are entered into the collection.

A queue, has insertion and deletion of elements at opposite ends of the collection or queue. We can implement a queue as a Lua array easily.

Queue Implementation Methods

We'll implement following methods to implement queue.

• enqueue− inserts an element to the queue.

• dequeue− deletes an element from the queue.

• front− get the first element of the queue.

Let's create a Queue class in following steps:

Step 1: Create Queue

Queue = {}

-- create a new Queue instance
function Queue.new()
   return {
	   data = {},  -- Queue
	   front = 1,  -- front index
	   tail = 0,    -- tail index
   }
end

Step 2: enqueue function

Create a enqueue function, which takes two parameters, queue and an element to be inserted to the tail of the queue.

-- enqueue function to insert an element to the end of queue
function Queue.enqueue(queue, value) 
   -- increment the tail index
   queue.tail = queue.tail + 1
   -- add the element to the tail index
   queue.data[queue.tail] = value 
end

Step 3: dequeue() function

Create a dequeue function which takes queue as a parameter and return the front element after removing it from the queue

-- dequeue function to remove an element from the front of queue
function Queue.dequeue(queue) 
   -- if front > tail
   if queue.front > queue.tail then 
      error("Queue underflow") 
   end
   -- get the value from the front of the queue
   local value = queue.data[queue.front] 
   -- set entry as nil for garbage collection
   queue.data[queue.front] = nil 
   -- increment the front
   queue.front = queue.front + 1 
   -- return value
   return value 
end

Step 4: Test Queue Operations

Create the Queue class and add values using enqueue() method, then get a value from queue using dequeue() method.

-- create the stack
local myQueue = Queue.new() 

-- push values to the queue
Queue.enqueue(myQueue, 10) 
Queue.enqueue(myQueue, 20) 
Queue.enqueue(myQueue, 30) 

-- get the value from front of the queue
print(Queue.dequeue(myQueue))

Queue: Complete Example

Following is the complete example of queue implementation using array with use of enqueue() and dequeue() methods.

main.lua

Queue = {}

-- create a Queue
function Queue.new()
   return {
      data = {},  -- Queue
      front = 1,  -- front index
      tail = 0,   -- tail index
   }
end

-- enqueue function to insert an element to the end of queue
function Queue.enqueue(queue, value) 
   -- increment the tail index
   queue.tail = queue.tail + 1
   -- add the element to the tail index
   queue.data[queue.tail] = value 
end

-- dequeue function to remove an element from the front of queue
function Queue.dequeue(queue) 
   -- if front > tail
   if queue.front > queue.tail then 
      error("Queue underflow") 
   end
   -- get the value from the front of the queue
   local value = queue.data[queue.front] 
   -- set entry as nil for garbage collection
   queue.data[queue.front] = nil 
   -- increment the front
   queue.front = queue.front + 1 
   -- return value
   return value 
end

function Queue.isEmpty(queue) 
  return queue.front > queue.back 
end 

-- create the queue
local myQueue = Queue.new() 

-- push values to the queue
Queue.enqueue(myQueue, 10) 
Queue.enqueue(myQueue, 20) 
Queue.enqueue(myQueue, 30) 

-- get the value from front of the queue
print(Queue.dequeue(myQueue))

-- push more values to the queue
Queue.enqueue(myQueue, 40) 
Queue.enqueue(myQueue, 50)

-- get the value from front of the queue
print(Queue.dequeue(myQueue))

Output

When we run the above code, we will get the following output−

10
20