Stacks and Queues

Stack Push/Pop

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

Algorithm

The replay uses the same three values in every language, so this Lua DSA implementation can be compared directly with the rest of the DSA track.

top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.

Visual walkthrough

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

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))

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.