Stacks and Queues

Queue from Two Stacks

Implement queue behavior with an input stack and an output stack.

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 in_stack = {}
local out_stack = {}
for _, value in ipairs({10, 20, 30}) do table.insert(in_stack, value) end
while #in_stack > 0 do table.insert(out_stack, table.remove(in_stack)) end
local removed = {}
while #out_stack > 0 do table.insert(removed, table.remove(out_stack)) end
print(render(removed))

The two-stack queue keeps cheap enqueues in the input stack, then reverses that stack only when dequeue needs the output stack.

Step 1 - Enqueue pushes onto the input stack

After enqueueing 10, 20, 30, the newest input value is on top of the input stack.

After enqueues: input top is 30; output is empty.input stack top -> bottomoutput stack top -> bottomremoved30(empty)(empty)2010

Step 2 - Transfer reverses into output order

Moving every input value to the output stack turns 10 into the next pop.

After transfer: output top is 10, so dequeue returns the oldest value.input stackoutput stack top -> bottomremoved(empty)10(empty)2030

Step 3 - Dequeue pops from output

The output stack pops 10 first while 20 becomes the next front.

After one dequeue: removed is 10; output top is now 20.input stackoutput stack top -> bottomremoved(empty)201030

Complexity

  • Time: O(1) amortized per operation
  • Space: O(n)

Implementation notes

  • local in_stack = {} and local out_stack = {} start as two empty Lua tables, matching the trace state [] and [].
  • Enqueue iterates ipairs({10, 20, 30}) and uses table.insert(in_stack, value), so the input stack becomes [10, 20, 30].
  • In this source, the stack top is the end of the table.
  • The transfer loop runs while #in_stack > 0 and moves values with table.insert(out_stack, table.remove(in_stack)).
  • Bare table.remove(in_stack) pops the last value, so the transfer reverses the order into out_stack = [30, 20, 10] and leaves in_stack = [].
  • Dequeue then pops from the output stack with table.insert(removed, table.remove(out_stack)).
  • Popping the end of [30, 20, 10] returns 10 first, then 20, then 30.
  • The trace ends with removed = [10, 20, 30] and out_stack = [].
  • render(removed) uses ipairs and table.concat(parts, " -> "), so print(render(removed)) outputs 10 -> 20 -> 30.
input stack Enqueue pushes new values onto the input stack.
output stack When the output stack is empty, transferring all input values reverses them into dequeue order.