Stacks and Queues

Queue Enqueue/Dequeue

Enqueue values at the back and dequeue them from the front in first-in, first-out order.

Algorithm

Basic Implementation

basic.R 
render <- function(values) {
  paste(values, collapse = " -> ")
}

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

The queue keeps the oldest value at the front and adds new values at the back.

Step 1 - Enqueue 10, 20, 30

New values join at the back. The oldest value, 10, stays at the front.

Queue after three enqueues: front 10, then 20, then back 30.nextnext10front2030back

Step 2 - Dequeue removes 10

Removing from the front returns 10 and makes 20 the new front.

After one dequeue: removed is 10; front moves to 20.next10removed20front30back

Complexity

  • Time: O(1) per operation with a real queue
  • Space: O(n)

Implementation notes

  • queue <- c() starts an empty R vector used as the queue.
  • Enqueue uses queue <- c(queue, value) inside for (value in c(10, 20, 30)), appending each value at the back.
  • After those three appends, the trace shows queue = [10, 20, 30].
  • removed <- c() starts a second vector for the values returned by dequeue.
  • The loop runs while length(queue) > 0.
  • R vectors are 1-based, so the front value is queue[1].
  • Dequeue records that scalar with removed <- c(removed, queue[1]).
  • The line queue <- queue[-1] removes the first element by negative indexing, leaving the remaining vector as the new queue.

Replay steps

start:        queue [], removed []
enqueue all:  queue [10, 20, 30]
dequeue 10:   queue [20, 30], removed [10]
dequeue rest: queue [], removed [10, 20, 30]
  • render(removed) uses paste(values, collapse = " -> ").
  • cat(render(removed), "\n", sep = "") prints 10 -> 20 -> 30.
front The front is the oldest value still waiting in the queue.
FIFO A queue removes values in first-in, first-out order.