Stacks and Queues in Lua

Lua gives you exactly one composite data type: the table. Everything interesting — arrays, dictionaries, objects, modules — is a table underneath. Stacks and queues are no exception. In this tutorial you’ll build both data structures from plain tables, understand the performance cost of the naïve queue approach, and implement a production-quality circular buffer that stays fast at any size.

Tables as sequential arrays

Before diving into stacks and queues, let’s recall how Lua arrays work. Lua arrays are sequences stored in tables with sequential integer keys starting at 1:

local fruits = { "apple", "banana", "cherry" }

print(fruits[1])  --> apple
print(#fruits)    --> 3

The # operator returns the number of elements in a sequential table. This is the foundation for everything that follows.

Stacks — last-in, first-out

A stack follows the LIFO (Last-In, First-Out) principle: the most recently added element is the next one removed. Think of a stack of plates — you add to the top and take from the top.

Basic operations

The table library gives you everything you need:

• Push: table.insert(t, value) — appends to the end, O(1)
• Pop: table.remove(t) — removes the last element, O(1)
• Peek: t[#t] — reads the top without removing it, O(1)
• Size: #t — returns element count, O(1)

A plain stack

Here’s how you use a stack with raw table operations:

local stack = {}

table.insert(stack, "first")
table.insert(stack, "second")
table.insert(stack, "third")

print(#stack)            --> 3
print(stack[#stack])     --> third  (peek)

local top = table.remove(stack)
print(top)               --> third
print(#stack)            --> 2

Helper functions

Repeating table.insert and table.remove gets old fast. Wrapping the logic in functions keeps your code clean:

local function push(stack, value)
    table.insert(stack, value)
end

local function pop(stack)
    if #stack == 0 then
        return nil, "stack is empty"
    end
    return table.remove(stack)
end

local function peek(stack)
    return stack[#stack]
end

local stack = {}
push(stack, 10)
push(stack, 20)
push(stack, 30)

print(peek(stack))   --> 30
print(pop(stack))   --> 30
print(pop(stack))   --> 20
print(pop(stack))   --> nil  (stack is empty)

Object-oriented stack

When you want encapsulation and a clear API, a metatable-based class works well:

local Stack = {}
Stack.__index = Stack

function Stack.new()
    return setmetatable({ _t = {} }, Stack)
end

function Stack:push(value)
    table.insert(self._t, value)
end

function Stack:pop()
    if #self._t == 0 then return nil end
    return table.remove(self._t)
end

function Stack:peek()
    return self._t[#self._t]
end

function Stack:size()
    return #self._t
end

function Stack:isEmpty()
    return #self._t == 0
end

local s = Stack.new()
s:push("a")
s:push("b")
s:push("c")

print(s:peek())    --> c
print(s:pop())     --> c
print(s:size())    --> 2
print(s:isEmpty()) --> false

Queues — first-in, first-out

A queue follows the FIFO (First-In, First-Out) principle: the earliest enqueued item is the first dequeued. Think of a line at a café — the first person in line is served first.

The naïve approach — and its trap

You can implement a queue using exactly the same functions as a stack, just pulling from a different end:

local queue = {}

table.insert(queue, "first")
table.insert(queue, "second")
table.insert(queue, "third")

-- dequeue from the front
local item = table.remove(queue, 1)
print(item)   --> first
print(#queue) --> 2

Here’s the problem: table.remove(t, 1) must shift every remaining element down by one position. That’s an O(n) operation. For a queue with 10 items, that’s 9 moves. For 10,000 items, that’s 9,999 moves — every single dequeue. In performance-critical code, this kills you.

The circular buffer — production-quality queues

The solution is to never move elements at all. Instead, keep a head pointer that advances through the array. The array grows at the tail and shrinks at the head, but no element ever moves:

local Queue = {}
Queue.__index = Queue

function Queue.new()
    return setmetatable({
        data   = {},
        head   = 0,
        tail   = -1,
        count  = 0,
    }, Queue)
end

function Queue:enqueue(value)
    self.tail = self.tail + 1
    if self.head == 0 then self.head = 1 end
    self.data[self.tail] = value
    self.count = self.count + 1
end

function Queue:dequeue()
    if self.count == 0 then return nil end
    local value = self.data[self.head]
    self.data[self.head] = nil  -- allow garbage collector to reclaim it
    self.head = self.head + 1
    self.count = self.count - 1
    return value
end

function Queue:peek()
    return self.data[self.head]
end

function Queue:size()
    return self.count
end

function Queue:isEmpty()
    return self.count == 0
end

local q = Queue.new()
q:enqueue("A")
q:enqueue("B")
q:enqueue("C")

print(q:dequeue()) --> A
print(q:dequeue()) --> B

q:enqueue("D")

print(q:dequeue()) --> C
print(q:dequeue()) --> D
print(q:isEmpty()) --> true

Both enqueue and dequeue are O(1). The array index only moves in one direction (up), and elements stay put. The memory cost is a few extra fields per queue and the nil’d slots that await garbage collection.

Iterating with ipairs()

When you need to walk through a stack or queue in order, use ipairs(). It iterates over sequential integer keys starting at 1 in guaranteed order:

local stack = { "alpha", "beta", "gamma" }

for i, v in ipairs(stack) do
    print(i, v)
end
-- 1  alpha
-- 2  beta
-- 3  gamma

Note that pairs() also iterates over tables but does not guarantee any particular order. For sequential data structures, always use ipairs().

When to use a stack VS a queue

The choice is dictated by the problem:

Scenario	Structure	Why
Undo / redo history	Stack	Most recent state is restored first
Depth-first search (DFS)	Stack	Explore as deep as possible before backtracking
Balancing delimiters	Stack	Match most recent opening with latest closing
Breadth-first search (BFS)	Queue	Process all nodes at depth N before depth N+1
Task / job scheduling	Queue	First submitted task is processed first
Event loop / message passing	Queue	Events processed in the order they arrived

The pattern is simple: if you need “most recent first,” reach for a stack. If you need “earliest first,” reach for a queue.

Practical example: balanced parentheses

Here’s a real use for a stack — checking whether a string of parentheses is balanced:

local function isBalanced(expr)
    local stack = {}
    local pairs = { [")"] = "(", ["]"] = "[", ["}"] = "{" }

    for i = 1, #expr do
        local ch = expr:sub(i, i)
        if pairs[ch] then
            -- closing bracket: pop and check
            local top = table.remove(stack)
            if top ~= pairs[ch] then
                return false
            end
        else
            -- opening bracket: push
            table.insert(stack, ch)
        end
    end

    return #stack == 0
end

print(isBalanced("(())"))      --> true
print(isBalanced("([{}])"))     --> true
print(isBalanced("(()"))        --> false
print(isBalanced("([)])"))      --> false

Every opening bracket gets pushed. Every closing bracket triggers a pop — if the popped value doesn’t match the expected opener, the string is unbalanced. At the end, an empty stack means success.

Practical example: breadth-first search

A queue is the natural tool for BFS. Here’s a simple graph traversal:

local Queue = {}
Queue.__index = Queue
function Queue.new() return setmetatable({data = {}, head = 0, tail = -1, count = 0}, Queue) end
function Queue:enqueue(v) self.tail = self.tail + 1; if self.head == 0 then self.head = 1 end; self.data[self.tail] = v; self.count = self.count + 1 end
function Queue:dequeue() if self.count == 0 then return nil end; local v = self.data[self.head]; self.data[self.head] = nil; self.head = self.head + 1; self.count = self.count - 1; return v end
function Queue:isEmpty() return self.count == 0 end

-- Simple graph as adjacency list
local graph = {
    A = { "B", "C" },
    B = { "D", "E" },
    C = { "F" },
    D = {},
    E = { "F" },
    F = {},
}

local function bfs(start)
    local q = Queue.new()
    q:enqueue(start)
    local visited = { [start] = true }
    local result = {}

    while not q:isEmpty() do
        local node = q:dequeue()
        table.insert(result, node)

        for _, neighbor in ipairs(graph[node]) do
            if not visited[neighbor] then
                visited[neighbor] = true
                q:enqueue(neighbor)
            end
        end
    end

    return result
end

print(table.concat(bfs("A"), " -> ")) --> A -> B -> C -> D -> E -> F

BFS visits nodes level by level: A, then B and C (A’s neighbors), then D, E, and F (B and C’s neighbors). The queue ensures no node at depth N+1 is visited before every node at depth N is processed.

Performance comparison

Operation	Stack	Naïve Queue	Circular Buffer Queue
Append / Enqueue	O(1)	O(1)	O(1)
Remove / Dequeue	O(1)	O(n)	O(1)
Peek	O(1)	O(1)	O(1)

The key takeaway: always append at the end (table.insert(t, x)). If you need FIFO behavior, never remove from index 1 on a plain table — use the circular buffer approach instead.

Summary

Stacks and queues are two of the most fundamental data structures in computer science, and in Lua they’re both built from the same material: tables.

• Stacks use LIFO ordering. table.insert pushes, table.remove pops — both O(1) at the end of the table. Perfect for DFS, undo systems, and delimiter checking.
• Queues use FIFO ordering. Appending at the end is O(1), but table.remove(t, 1) is O(n) because every remaining element has to shift. For anything beyond toy examples, implement a circular buffer with a head index that advances instead of shifting elements.
• Iteration over sequential tables uses ipairs() for guaranteed order.
• Helper functions or metatable classes keep your data structure APIs clean and self-documenting.

With these patterns in your toolkit, you’re well-equipped to model real-world problems in Lua — from parsing and expression evaluation to graph traversal and task scheduling.

See also

• Arrays and Lists in Lua — Master sequential table operations including slicing, searching, and sorting.
• Sets in Lua — Learn how to use tables as hash-based sets for fast membership testing.