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.rb 
queue = []
[10, 20, 30].each { |value| queue.push(value) }
removed = []
removed << queue.shift until queue.empty?
puts removed.join(" -> ")

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

  • The queue is a Ruby Array, starting as queue = [].
  • Enqueue uses queue.push(value) inside [10, 20, 30].each, so new values are appended at the back in that order.
  • Dequeue uses queue.shift, which removes and returns the front element while mutating the array.
  • removed << queue.shift until queue.empty? keeps shifting only while the queue has values, so this source never relies on shift returning nil from an empty array.
  • FIFO order is visible in the trace: [10, 20, 30] becomes [20, 30] after removing 10, then becomes empty after removing 20 and 30.
  • removed is another Ruby array that records the returned values as [10, 20, 30].
  • puts removed.join(" -> ") prints the deterministic output 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.