🎓 A1Learner
🔍
0 of 52 lessons completed

Lua Queues and Stacks

A queue is a waiting line that removes items in the order they joined. A stack is a pile that removes the most recent item first.

A head index runs a queue

New items join at the end of the array. The head index moves forward as items leave, so no shifting is needed.

local queue = {}
local head = 1
queue[#queue + 1] = "first"
queue[#queue + 1] = "second"
queue[#queue + 1] = "third"
local a = queue[head]
queue[head] = nil
head = head + 1
local b = queue[head]
queue[head] = nil
head = head + 1
print(a)
print(b)
print(queue[head])

Push and pop run a stack

Push adds to the end of the array. Pop takes the last item back off the end.

local stack = {}
stack[#stack + 1] = 10
stack[#stack + 1] = 20
stack[#stack + 1] = 30
local top = stack[#stack]
stack[#stack] = nil
print(top)
top = stack[#stack]
stack[#stack] = nil
print(top)
print(#stack)

A queue walks breadth first

The queue holds nodes waiting to be visited. Each visited node adds its unvisited neighbours to the back of the queue.

local graph = {
  a = {"b", "c"},
  b = {"d"},
  c = {"d"},
  d = {},
}
local visited = {a = true}
local queue = {"a"}
local head = 1
local order = {}
while head <= #queue do
  local node = queue[head]
  head = head + 1
  order[#order + 1] = node
  for i = 1, #graph[node] do
    local next = graph[node][i]
    if not visited[next] then
      visited[next] = true
      queue[#queue + 1] = next
    end
  end
end
print(table.concat(order, ", "))

Example

local queue = {"wash", "dry", "fold"}
local head = 1
local done = {}
while head <= #queue do
  local job = queue[head]
  head = head + 1
  done[#done + 1] = job
end
print(table.concat(done, ", "))
local undone = done[#done]
done[#done] = nil
print(undone)
print(done[#done])

Key points

  • Queue: a queue removes items first in, first out.
  • Head index: a head index marks the next item to leave the queue, so old slots are skipped instead of shifted.
  • Stack: a stack removes items last in, first out.
  • Push: pushing adds an item to the top of a stack.
  • Pop: popping removes and returns the top item of a stack.
  • Breadth first: a breadth-first walk visits neighbours level by level, using a queue to hold what comes next.

In this example, three jobs wait in a queue and each one moves to a done stack as it finishes. The printed list shows the jobs in queue order. Popping the stack undoes fold, leaving dry on top.

Note

removing from the front of an array shifts every later item, so a head index is cheaper for long queues.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

After pushing wash, dry and fold onto a stack, which item does pop return first?