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.sh 
#!/usr/bin/env bash
set -euo pipefail

render() {
  local out=""
  for value in "$@"; do
    if [[ -n "$out" ]]; then out+=" -> "; fi
    out+="$value"
  done
  printf '%s\n' "$out"
}

queue=()
for value in 10 20 30; do
  queue+=("$value")
done

removed=()
while (( ${#queue[@]} > 0 )); do
  front=${queue[0]}
  removed+=("$front")
  queue=("${queue[@]:1}")
done

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

  • queue=() starts an empty Bash indexed array used as the queue.
  • queue+=("$value") appends each value at the back. The pinned values are 10, 20, and 30.
  • The front value is read with ${queue[0]} and saved as front.
  • removed+=("$front") records the dequeued values in FIFO order.
  • queue=("${queue[@]:1}") replaces the queue with a slice that skips the old front. This teaching version copies the remaining array, so front dequeue is O(n) in Bash even though a real queue can be O(1).
  • render() receives values through "$@", builds out, inserts the separator -> between values, and prints with printf.

Replay steps

enqueue: [] -> [10] -> [10, 20] -> [10, 20, 30]
dequeue: remove 10, remaining [20, 30]
finish:  removed [10, 20, 30], queue []
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.