Shell脚本如何实现双端队列

本文目录导读：

1. 基于数组的双端队列实现
2. 基于文件的持久化双端队列
3. 更高效的环状缓冲区实现
4. 使用建议

在Shell脚本中实现双端队列（deque），可以使用数组或文件来模拟,以下是几种实现方式：

基于数组的双端队列实现

#!/bin/bash
# 双端队列类实现
declare -a deque=()
deque_left=0
deque_right=-1
# 在队首添加元素
deque_push_left() {
    local item="$1"
    # 将队列向右移动一个位置
    for ((i=deque_right+1; i>0; i--)); do
        deque[$i]="${deque[$((i-1))]}"
    done
    deque[0]="$item"
    ((deque_right++))
}
# 在队尾添加元素
deque_push_right() {
    local item="$1"
    ((deque_right++))
    deque[$deque_right]="$item"
}
# 从队首移除元素
deque_pop_left() {
    if [ $deque_left -gt $deque_right ]; then
        echo "Error: Deque is empty"
        return 1
    fi
    local item="${deque[$deque_left]}"
    ((deque_left++))
    echo "$item"
}
# 从队尾移除元素
deque_pop_right() {
    if [ $deque_left -gt $deque_right ]; then
        echo "Error: Deque is empty"
        return 1
    fi
    local item="${deque[$deque_right]}"
    ((deque_right--))
    echo "$item"
}
# 查看队首元素
deque_peek_left() {
    if [ $deque_left -gt $deque_right ]; then
        echo "Error: Deque is empty"
        return 1
    fi
    echo "${deque[$deque_left]}"
}
# 查看队尾元素
deque_peek_right() {
    if [ $deque_left -gt $deque_right ]; then
        echo "Error: Deque is empty"
        return 1
    fi
    echo "${deque[$deque_right]}"
}
# 检查是否为空
deque_is_empty() {
    [ $deque_left -gt $deque_right ]
    return $?
}
# 获取队列大小
deque_size() {
    echo $((deque_right - deque_left + 1))
}
# 清空队列
deque_clear() {
    deque_left=0
    deque_right=-1
}
# 示例用法
echo "=== 双端队列测试 ==="
deque_push_right "A"
deque_push_right "B"
deque_push_left "C"
deque_push_left "D"
echo "队列: ${deque[@]}"
echo "队首元素: $(deque_peek_left)"
echo "队尾元素: $(deque_peek_right)"
echo "队列大小: $(deque_size)"
echo "弹出队首: $(deque_pop_left)"
echo "弹出队尾: $(deque_pop_right)"
echo "弹出队首: $(deque_pop_left)"
echo "队列是否为空: $(deque_is_empty && echo '是' || echo '否')"
echo "剩余元素: ${deque[@]}"

基于文件的持久化双端队列

#!/bin/bash
# 使用文件实现持久化双端队列
DEQUE_FILE="/tmp/deque_$$.txt"
deque_init() {
    > "$DEQUE_FILE"  # 清空文件
}
deque_push_left() {
    local item="$1"
    # 临时文件存储
    local tmp_file=$(mktemp)
    echo "$item" > "$tmp_file"
    cat "$DEQUE_FILE" >> "$tmp_file"
    mv "$tmp_file" "$DEQUE_FILE"
}
deque_push_right() {
    local item="$1"
    echo "$item" >> "$DEQUE_FILE"
}
deque_pop_left() {
    if [ ! -s "$DEQUE_FILE" ]; then
        echo "Error: Deque is empty"
        return 1
    fi
    local item=$(head -n 1 "$DEQUE_FILE")
    # 移除第一行
    sed -i '1d' "$DEQUE_FILE"
    echo "$item"
}
deque_pop_right() {
    if [ ! -s "$DEQUE_FILE" ]; then
        echo "Error: Deque is empty"
        return 1
    fi
    local item=$(tail -n 1 "$DEQUE_FILE")
    # 移除最后一行
    sed -i '$d' "$DEQUE_FILE"
    echo "$item"
}
deque_peek_left() {
    if [ ! -s "$DEQUE_FILE" ]; then
        echo "Error: Deque is empty"
        return 1
    fi
    head -n 1 "$DEQUE_FILE"
}
deque_peek_right() {
    if [ ! -s "$DEQUE_FILE" ]; then
        echo "Error: Deque is empty"
        return 1
    fi
    tail -n 1 "$DEQUE_FILE"
}
deque_is_empty() {
    [ ! -s "$DEQUE_FILE" ]
}
deque_size() {
    wc -l < "$DEQUE_FILE"
}
deque_destroy() {
    rm -f "$DEQUE_FILE"
}
# 示例用法
echo "=== 文件持久化双端队列 ==="
deque_init
deque_push_right "Apple"
deque_push_right "Banana"
deque_push_left "Orange"
deque_push_left "Grape"
echo "队列元素:"
cat "$DEQUE_FILE"
echo "队首: $(deque_peek_left)"
echo "队尾: $(deque_peek_right)"
echo "大小: $(deque_size)"
echo "弹出队首: $(deque_pop_left)"
echo "弹出队尾: $(deque_pop_right)"
echo "剩余元素:"
cat "$DEQUE_FILE"
deque_destroy

更高效的环状缓冲区实现

#!/bin/bash
# 使用环状缓冲区实现高效双端队列
declare -A deque=()
DEQUE_CAPACITY=100
DEQUE_HEAD=0
DEQUE_TAIL=0
DEQUE_COUNT=0
deque_push_left() {
    local item="$1"
    if [ $DEQUE_COUNT -eq $DEQUE_CAPACITY ]; then
        echo "Error: Deque is full"
        return 1
    fi
    DEQUE_HEAD=$(( (DEQUE_HEAD - 1 + DEQUE_CAPACITY) % DEQUE_CAPACITY ))
    deque[$DEQUE_HEAD]="$item"
    ((DEQUE_COUNT++))
}
deque_push_right() {
    local item="$1"
    if [ $DEQUE_COUNT -eq $DEQUE_CAPACITY ]; then
        echo "Error: Deque is full"
        return 1
    fi
    deque[$DEQUE_TAIL]="$item"
    DEQUE_TAIL=$(( (DEQUE_TAIL + 1) % DEQUE_CAPACITY ))
    ((DEQUE_COUNT++))
}
deque_pop_left() {
    if [ $DEQUE_COUNT -eq 0 ]; then
        echo "Error: Deque is empty"
        return 1
    fi
    local item="${deque[$DEQUE_HEAD]}"
    unset deque[$DEQUE_HEAD]
    DEQUE_HEAD=$(( (DEQUE_HEAD + 1) % DEQUE_CAPACITY ))
    ((DEQUE_COUNT--))
    echo "$item"
}
deque_pop_right() {
    if [ $DEQUE_COUNT -eq 0 ]; then
        echo "Error: Deque is empty"
        return 1
    fi
    DEQUE_TAIL=$(( (DEQUE_TAIL - 1 + DEQUE_CAPACITY) % DEQUE_CAPACITY ))
    local item="${deque[$DEQUE_TAIL]}"
    unset deque[$DEQUE_TAIL]
    ((DEQUE_COUNT--))
    echo "$item"
}
deque_peek_left() {
    if [ $DEQUE_COUNT -eq 0 ]; then
        echo "Error: Deque is empty"
        return 1
    fi
    echo "${deque[$DEQUE_HEAD]}"
}
deque_peek_right() {
    if [ $DEQUE_COUNT -eq 0 ]; then
        echo "Error: Deque is empty"
        return 1
    fi
    local right_index=$(( (DEQUE_TAIL - 1 + DEQUE_CAPACITY) % DEQUE_CAPACITY ))
    echo "${deque[$right_index]}"
}
deque_is_empty() {
    [ $DEQUE_COUNT -eq 0 ]
}
deque_size() {
    echo "$DEQUE_COUNT"
}
# 示例用法
echo "=== 高效环状缓冲区实现 ==="
deque_push_right "X"
deque_push_right "Y"
deque_push_left "Z"
echo "队首: $(deque_peek_left)"
echo "队尾: $(deque_peek_right)"
echo "大小: $(deque_size)"
echo "弹出队首: $(deque_pop_left)"
echo "弹出队尾: $(deque_pop_right)"
echo "队列是否为空: $(deque_is_empty && echo '是' || echo '否')"

使用建议

1. 简单场景：使用基于数组的简单实现
2. 需要持久化：使用基于文件的实现
3. 性能要求高：使用环状缓冲区实现
4. 数据量大：考虑使用文件或数据库存储

这些实现提供了双端队列的核心操作（push_left/right, pop_left/right, peek_left/right, size, is_empty）,可以根据具体需求选择合适的实现方式。