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.swift 
func render(_ values: [Int]) -> String {
    values.map(String.init).joined(separator: " -> ")
}

var stack: [Int] = []
for value in [10, 20, 30] { stack.append(value) }
var popped: [Int] = []
while !stack.isEmpty { popped.append(stack.removeLast()) }
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

  • var stack: [Int] = [] is a mutable Swift array used as stack storage, with the back of the array acting as the top.
  • The push loop for value in [10, 20, 30] { stack.append(value) } appends each Int in order, producing [10, 20, 30].
  • var popped: [Int] = [] records pop order separately from the remaining stack.
  • The loop guard while !stack.isEmpty prevents calling removeLast() on an empty array, so this source has no optional return or sentinel path.
  • popped.append(stack.removeLast()) removes from the array end, so 30 is recorded before 20 and 10.
  • The trace shows the stack moving from [] to [10, 20, 30], then the first pop producing popped = [30] and stack = [10, 20], and finally popped = [30, 20, 10] with stack = [].
  • render(_:) maps each Int to String and joins with " -> ", 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.