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.f90 
program stack_queue_lesson
    implicit none
    integer :: values(3) = [10, 20, 30]
    integer :: result(3)
    integer :: i, count
    count = 0
    do i = 3, 1, -1
        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 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

  • 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.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.