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.R 
render <- function(values) {
  paste(values, collapse = " -> ")
}

stack <- c()
for (value in c(10, 20, 30)) stack <- c(stack, value)
popped <- c()
while (length(stack) > 0) {
  popped <- c(popped, stack[length(stack)])
  stack <- stack[-length(stack)]
}
cat(render(popped), "\n", sep = "")

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

  • stack <- c() starts as an empty R vector, and the lesson uses the right end of that vector as the stack top.
  • The pinned push loop appends 10, 20, and 30 with stack <- c(stack, value), so the trace moves from [] to [10, 20, 30].
  • Pop reads the top scalar with stack[length(stack)], then removes that slot with stack <- stack[-length(stack)].
  • Each removed value is appended to popped with popped <- c(popped, ...), so the replay records [30] first and finishes with [30, 20, 10].

Replay steps

start:   stack [], popped []
push:    stack [10, 20, 30]
pop 30:  stack [10, 20], popped [30]
pop all: stack [], popped [30, 20, 10]
  • render(popped) uses paste(values, collapse = " -> "), and cat(render(popped), "\n", sep = "") prints 30 -> 20 -> 10.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.