Lua - Table as Queue

In Lua, Table is the only data structure which can be used to represent array, dictionary and other data structures. We can represent a Queue using Table vary easily.

The queue is a data structure which follows First-In-First-Out (FIFO) approach. It represents a collection of elements where the elements maintain the order in which they are entered into the collection.

For example, a queue of messages is used by web services to process requests. When a publisher publishes a message to the queue, it is appended to the tail end of the queue and when a subscriber reads from the queue, the first entry of queue is removed and returned to the subscriber. So whenever a message is added to queue's end, its size increases and when a message is read from the front of queue, size of queue decreases.

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.

• empty− returns true if queue is empty otherwise returns false.

Let's create a Queue class in following steps:

Step 1: Create Queue

Queue = {}
-- create a new queue
function Queue.new()
   queueTable = {
      -- data as empty table
      data = {},
      -- front index
      front = 1,
      -- end index
      tail = 0,
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
enqueue = function(self, value)
   -- increment the tail index
   self.tail = self.tail + 1
   -- add the element to the tail index
   self.data[self.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
dequeue = function(self)
   -- if queue is empty
   if self.front > self.tail then
      error("Queue is emtpty")
   end
   -- get the value from the front of the queue
   local value = self.data[self.front]
   -- set entry as nil for garbage collection
   self.data[self.front] = nil
   -- increment the front
   self.front = self.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 queue
local myQueue = Queue.new()

-- push values to the queue
myQueue:enqueue("A")
myQueue:enqueue("B")
myQueue:enqueue("C")

-- Queue ==  A <- B <- C
-- get the value from front of the queue
print(myQueue:dequeue()) -- A

Queue: Complete Example

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

main.lua

Queue = {}
-- create a new queue
function Queue.new()
   queueTable = {
      -- data as empty table
      data = {},
      -- front index
      front = 1,
      -- end index
      tail = 0,

      enqueue = function(self, value)
         -- increment the tail index
         self.tail = self.tail + 1
         -- add the element to the tail index
         self.data[self.tail] = value
      end,

      dequeue = function(self)
         -- if queue is empty
         if self.front > self.tail then
            error("Queue is emtpty")
         end
         -- get the value from the front of the queue
         local value = self.data[self.front]
         -- set entry as nil for garbage collection
         self.data[self.front] = nil
         -- increment the front
         self.front = self.front + 1
         -- return value
         return value
      end,

      -- check if queue is empty
      isEmpty = function(self)
         return self.front > self.tail
      end
   }

   -- return queue instance
   return queueTable
end


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

-- push values to the queue
myQueue:enqueue("A")
myQueue:enqueue("B")
myQueue:enqueue("C")

-- Queue ==  A <- B <- C
-- get the value from front of the queue
print(myQueue:dequeue()) -- A

-- push more values to the queue
myQueue:enqueue("D")
myQueue:enqueue("E")

-- Queue ==  B <- C <- D <- E
-- get the value from front of the queue
print(myQueue:dequeue())  -- B

Output

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

A
B