Stacks and Queues

Queue Enqueue/Dequeue

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

Algorithm

The replay uses the same three values in every language, so this Bash DSA implementation can be compared directly with the rest of the DSA track.

front The front is the oldest value still waiting in the queue.
FIFO A queue removes values in first-in, first-out order.

Visual walkthrough

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

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[@]}"

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