Queue from Two Stacks

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

Algorithm

Basic Implementation

basic.f90

program stack_queue_lesson
    implicit none
    integer :: values(3) = [10, 20, 30]
    integer :: result(3)
    integer :: i, count
    count = 0
    do i = 1, 3
        count = count + 1
        result(count) = values(i)
    end do
    call print_values(result, count)
contains
    subroutine print_values(items, n)
        integer, intent(in) :: items(:)
        integer, intent(in) :: n
        integer :: j
        do j = 1, n
            if (j > 1) write(*, '(A)', advance='no') ' -> '
            write(*, '(I0)', advance='no') items(j)
        end do
        write(*, *)
    end subroutine print_values
end program stack_queue_lesson

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.

Step 2 - Transfer reverses into output order

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

Step 3 - Dequeue pops from output

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

Complexity

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

Implementation notes

Keep the explicit stack/queue operations. Library shortcuts that only produce the final list hide the data-structure behavior this lesson is meant to replay.
The final output uses a deterministic a -> b -> c format for cross-language comparison.

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.