Shell脚本如何实现循环队列

本文目录导读：

1. 使用数组实现基本的循环队列
2. 使用函数封装的循环队列
3. 使用示例
4. 增强版：支持动态扩容
5. 性能测试
6. 使用建议

我来为您介绍在Shell脚本中实现循环队列的几种方法。

使用数组实现基本的循环队列

#!/bin/bash
# 循环队列实现
class CircularQueue() {
    # 初始化队列
    declare -a queue
    size=0
    capacity=10
    front=0
    rear=-1
    count=0
    # 入队操作
    enqueue() {
        local item=$1
        if [ $count -eq $capacity ]; then
            echo "队列已满，无法入队"
            return 1
        fi
        # 计算rear位置（循环）
        rear=$(( (rear + 1) % capacity ))
        queue[$rear]=$item
        count=$(( count + 1 ))
        echo "入队: $item"
    }
    # 出队操作
    dequeue() {
        if [ $count -eq 0 ]; then
            echo "队列为空，无法出队"
            return 1
        fi
        local item=${queue[$front]}
        front=$(( (front + 1) % capacity ))
        count=$(( count - 1 ))
        echo "出队: $item"
        return 0
    }
    # 查看队首元素
    peek() {
        if [ $count -eq 0 ]; then
            echo "队列为空"
            return 1
        fi
        echo "队首元素: ${queue[$front]}"
    }
    # 显示所有元素
    display() {
        if [ $count -eq 0 ]; then
            echo "队列为空"
            return
        fi
        echo "队列元素:"
        local i=$front
        local j=0
        while [ $j -lt $count ]; do
            echo "  [${queue[$i]}]"
            i=$(( (i + 1) % capacity ))
            j=$(( j + 1 ))
        done
    }
    # 获取队列大小
    getSize() {
        echo "队列大小: $count"
    }
    # 清空队列
    clear() {
        count=0
        front=0
        rear=-1
        echo "队列已清空"
    }
}

使用函数封装的循环队列

#!/bin/bash
# 全局变量
declare -a CIRCULAR_QUEUE
QUEUE_CAPACITY=10
QUEUE_FRONT=0
QUEUE_REAR=-1
QUEUE_COUNT=0
# 初始化队列
init_queue() {
    local capacity=${1:-10}
    QUEUE_CAPACITY=$capacity
    QUEUE_FRONT=0
    QUEUE_REAR=-1
    QUEUE_COUNT=0
    echo "队列初始化完成，容量: $QUEUE_CAPACITY"
}
# 判断队列是否为空
is_empty() {
    [ $QUEUE_COUNT -eq 0 ]
}
# 判断队列是否已满
is_full() {
    [ $QUEUE_COUNT -eq $QUEUE_CAPACITY ]
}
# 入队操作
enqueue() {
    local item=$1
    if is_full; then
        echo "错误: 队列已满"
        return 1
    fi
    QUEUE_REAR=$(( (QUEUE_REAR + 1) % QUEUE_CAPACITY ))
    CIRCULAR_QUEUE[$QUEUE_REAR]=$item
    QUEUE_COUNT=$(( QUEUE_COUNT + 1 ))
    echo "成功入队: $item"
}
# 出队操作
dequeue() {
    if is_empty; then
        echo "错误: 队列为空"
        return 1
    fi
    local item=${CIRCULAR_QUEUE[$QUEUE_FRONT]}
    unset CIRCULAR_QUEUE[$QUEUE_FRONT]
    QUEUE_FRONT=$(( (QUEUE_FRONT + 1) % QUEUE_CAPACITY ))
    QUEUE_COUNT=$(( QUEUE_COUNT - 1 ))
    echo "成功出队: $item"
}
# 打印队列
print_queue() {
    if is_empty; then
        echo "队列为空"
        return
    fi
    echo "当前队列 (共 $QUEUE_COUNT 个元素):"
    local idx=$QUEUE_FRONT
    local count=0
    while [ $count -lt $QUEUE_COUNT ]; do
        echo "  [$count]: ${CIRCULAR_QUEUE[$idx]}"
        idx=$(( (idx + 1) % QUEUE_CAPACITY ))
        count=$(( count + 1 ))
    done
}

使用示例

#!/bin/bash
source circular_queue.sh  # 导入上面的脚本
# 使用示例
main() {
    # 初始化容量为5的循环队列
    init_queue 5
    # 入队操作
    echo "=== 入队操作 ==="
    for i in {1..7}; do
        enqueue "item_$i"
    done
    print_queue
    echo -e "\n=== 出队操作 ==="
    for i in {1..3}; do
        dequeue
    done
    print_queue
    echo -e "\n=== 继续入队 ==="
    enqueue "new_item_1"
    enqueue "new_item_2"
    print_queue
    # 获取队首元素
    echo -e "\n队首元素: ${CIRCULAR_QUEUE[$QUEUE_FRONT]}"
    echo "队列状态: $QUEUE_COUNT/$QUEUE_CAPACITY"
}
main

增强版：支持动态扩容

#!/bin/bash
# 动态扩容的循环队列
declare -a DYNAMIC_QUEUE
DYNAMIC_CAPACITY=4
DYNAMIC_FRONT=0
DYNAMIC_REAR=-1
DYNAMIC_COUNT=0
# 扩容操作
resize() {
    local old_capacity=$DYNAMIC_CAPACITY
    local new_capacity=$(( old_capacity * 2 ))
    local new_queue=()
    # 复制元素到新数组
    local idx=$DYNAMIC_FRONT
    local count=0
    while [ $count -lt $DYNAMIC_COUNT ]; do
        new_queue[$count]=${DYNAMIC_QUEUE[$idx]}
        idx=$(( (idx + 1) % old_capacity ))
        count=$(( count + 1 ))
    done
    # 更新全局变量
    DYNAMIC_QUEUE=("${new_queue[@]}")
    DYNAMIC_CAPACITY=$new_capacity
    DYNAMIC_FRONT=0
    DYNAMIC_REAR=$(( DYNAMIC_COUNT - 1 ))
    echo "队列已扩容到: $new_capacity"
}
# 带自动扩容的入队
dynamic_enqueue() {
    local item=$1
    # 如果队列满了，自动扩容
    if [ $DYNAMIC_COUNT -eq $DYNAMIC_CAPACITY ]; then
        resize
    fi
    DYNAMIC_REAR=$(( (DYNAMIC_REAR + 1) % DYNAMIC_CAPACITY ))
    DYNAMIC_QUEUE[$DYNAMIC_REAR]=$item
    DYNAMIC_COUNT=$(( DYNAMIC_COUNT + 1 ))
    echo "入队: $item (容量: $DYNAMIC_CAPACITY)"
}

性能测试

#!/bin/bash
# 测试循环队列性能
test_performance() {
    init_queue 1000
    echo "=== 性能测试 ==="
    # 测试入队
    start_time=$(date +%s%N)
    for i in {1..1000}; do
        enqueue "data_$i"
    done
    end_time=$(date +%s%N)
    echo "1000次入队耗时: $(( (end_time - start_time) / 1000000 ))ms"
    # 测试出队
    start_time=$(date +%s%N)
    for i in {1..1000}; do
        dequeue
    done
    end_time=$(date +%s%N)
    echo "1000次出队耗时: $(( (end_time - start_time) / 1000000 ))ms"
}

使用建议

1. 选择合适的容量: 根据业务需求设置初始容量
2. 考虑使用关联数组: 对于更大规模的数据，考虑使用关联数组
3. 错误处理: 添加完善的错误检查和处理逻辑
4. 性能优化: 对于频繁操作，考虑使用临时变量缓存计算结果

这个实现展示了Shell脚本中循环队列的核心概念，包括循环数组、队首队尾指针管理和元素计数等特性。