Stacks and Queues

Stack Push/Pop

Push values onto a stack and pop them back in last-in, first-out order.

Algorithm

Basic Implementation

basic.lua 
local function render(values)
    local parts = {}
    for i, value in ipairs(values) do parts[i] = tostring(value) end
    return table.concat(parts, " -> ")
end

local stack = {}
for _, value in ipairs({10, 20, 30}) do table.insert(stack, value) end
local popped = {}
while #stack > 0 do table.insert(popped, table.remove(stack)) end
print(render(popped))

The same three values from the trace are shown as stack states. The top cell is the next value a pop removes.

Step 1 - Start empty

There is no top value yet.

Empty stack before any push.top of stack(empty)

Step 2 - Push 10, then 20, then 30

Each push places the new value above the previous top.

After push 10, push 20, push 30: 30 is on top.top -> bottom302010

Step 3 - Pop removes 30 first

The top cell leaves first, so the remaining stack starts with 20.

After one pop: popped is 30; 20 is now on top.top -> bottompopped203010

Complexity

  • Time: O(1) per push/pop
  • Space: O(n)

Implementation notes

  • local stack = {} starts as an empty Lua table, and the trace records [].
  • Pushes iterate ipairs({10, 20, 30}) and use table.insert(stack, value).
  • In this source, the stack top is the end of the table, so after the pushes the top value is 30 in [10, 20, 30].
  • The pop loop runs while #stack > 0.
  • Bare table.remove(stack) removes and returns the last table value.
  • Removed values are collected with table.insert(popped, table.remove(stack)).
  • The first pop returns 30, leaving stack = [10, 20] and popped = [30].
  • The remaining pops return 20 and then 10, ending with popped = [30, 20, 10] and stack = [].
  • render(popped) uses ipairs and table.concat(parts, " -> "), so print(render(popped)) outputs 30 -> 20 -> 10.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.