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.scala 
def render(values: Seq[Int]): String = values.mkString(" -> ")

var queue = scala.collection.mutable.Queue[Int]()
for (value <- List(10, 20, 30)) queue.enqueue(value)
var removed = List[Int]()
while (queue.nonEmpty) removed = removed :+ queue.dequeue()
println(render(removed))

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

  • var queue = scala.collection.mutable.Queue[Int]() creates the mutable Scala queue used by the replay.
  • The enqueue loop for (value <- List(10, 20, 30)) queue.enqueue(value) adds values at the back in input order.
  • var removed = List[Int]() starts as an immutable Scala list value, but the var binding is reassigned after each dequeue.
  • The loop guard while (queue.nonEmpty) prevents calling dequeue() on an empty queue, so this source has no Option return or sentinel path.
  • queue.dequeue() removes and returns the front value; removed = removed :+ queue.dequeue() appends that returned value to the end of the output list.
  • The trace shows queue moving from [] to [10, 20, 30], then the first dequeue producing removed = [10] and queue = [20, 30].
  • The remaining dequeues leave removed = [10, 20, 30] and queue = [].
  • render(values: Seq[Int]) uses mkString(" -> "), so println(render(removed)) writes 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.