本文目录导读：
我来为您介绍在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"
}
使用建议
- 选择合适的容量: 根据业务需求设置初始容量
- 考虑使用关联数组: 对于更大规模的数据，考虑使用关联数组
- 错误处理: 添加完善的错误检查和处理逻辑
- 性能优化: 对于频繁操作，考虑使用临时变量缓存计算结果
这个实现展示了Shell脚本中循环队列的核心概念，包括循环数组、队首队尾指针管理和元素计数等特性。
