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.pl 
use strict;
use warnings;

sub render { return join(" -> ", @_); }

my @queue;
push @queue, $_ for (10, 20, 30);
my @removed;
push @removed, shift @queue while @queue;
print render(@removed), "\n";

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

  • my @queue declares the queue as a Perl array with the @ sigil.
  • The queue starts empty; the trace begins with [].
  • Enqueue uses push @queue, $_ for (10, 20, 30), appending each value to the back of the array.
  • After the enqueue step, the replayed queue is [10, 20, 30].
  • my @removed stores the values as they are dequeued.
  • Dequeue uses shift @queue, which removes and returns the front element of the Perl array.
  • push @removed, shift @queue while @queue repeats while the queue array is non-empty; in that condition, @queue is in scalar context and means length.
  • The first dequeue returns 10, leaving queue [20, 30] and removed [10].
  • The remaining dequeues return 20 and 30, leaving queue [] and removed [10, 20, 30].
  • render(@removed) receives the removed values as a list and joins them with " -> ".
  • print render(@removed), "\n" outputs 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.