Implement a Simple Queue using Bash Array

In this article, I’ll share with you a simple queue implemented using Bash array.

Bash Queue (FIFO Data Structure)

In one of my recent tasks, I was implementing an iterative BFS in Bash (before I decided to just use the Find command).

As you’re aware, BFS makes use of a queue to help it remember what to look at next.

And a queue is just a FIFO (First In First Out) data structure.

In essence, a queue supports the following operations:-

1. Pop the first element (First out)
2. Append new element to the end
3. Report number of elements in queue

And here’s the cheat sheet that shows how to do these things with a Bash array:-

# Declare an array called queue with four initial elements in it
queue=( elem1 elem2 elem3 elem4 )

# Append new items to the end
queue+=("elem5")
## Pop the first element (two steps)
# Retrieve the first element, store it in variable "item"
item=${queue[0]}

# Remove the first element from queue
queue=("${queue[@]:1}")

# Report number of elements
echo ${#queue[@]}

Example

The following code does a breadth-first scan on all the files and directories under the current directory.

start_path=$(pwd)
queue=( $start_path )

while [ ${#queue[@]} -gt 0 ]
do
        echo "Queue length: ${#queue[@]}"

        # Pop the first element (a path)
        path=${queue[0]}
        queue=("${queue[@]:1}")

        cd $path

        echo "Scanning $path"

        # Add sub directories to queue
        # ls -d $PWD/* returns the full paths to files in current directory
        for file in $(ls -d $PWD/*)
        do
                # If it's a directory
                if [ -d $file ]
                then
                        # Add to queue
                        queue+=($file)
                fi
        done
done

# Return to starting point
cd $start_path