二 栈的简单实现
Posted inlinux shell bash 基础

二 栈的简单实现

浏览次数: 84

【动机】

偶尔，我们为了某种需要，临时修改分隔符，例如：

    motive(){
        local old_ifs="$IFS"
        
        IFS=":"
        read -p "请输入3个数据, 务必使用冒号分割 " x y z
        printf "您的输入结果是: x={%s},y={%s},z={%s}\n" $x $y $z

        # 其余操作 ...
        IFS="$old_ifs"     
    }
    clear
    motive

运行结果：

请输入3个数据, 务必使用冒号分割 one,two:three,four:five,six
您的输入结果是: x={one,two},y={three,four},z={five,six}

其中，IFS 的存储和恢复，可用，但不够优雅。我们希望如此：

        push IFS

        IFS=":"
        # 第一波操作......

        push IFS
        IFS=","
        # 第二波操作
        pop IFS

        pop IFS

【实施】

新建文件 stack.sh。使用数组模仿栈，考虑到栈是全局可用，所以该数组亦为全局

# 数组, 用来模拟栈数据结构
__Stacking__=()
  1. push 函数
push() {
    local v="$*"    
    if [[ "$v" =~ ^[a-zA-Z_][a-zA-Z0-9_]*$ && "${!v}" ]];then
        v=${!v}
    fi
    __Stacking__+=("$v")
}

push 函数完成数据入栈，优先将参数理解为变量名, 然后是字符串. 用法:

local ticker="hello,world and how are you"
push ticker    
push "--feh owo"

但如果已定义的变量值为空, 仍然被理解为字符串.

2. ise 函数，判断当前栈是否空

ise(){
    [ ${#__Stacking__[@]} -le 0 ] && return 0 || return 1
}

这里使用退出码标识成功与否， 简单返回 0 或 1，而不直接采用栈长度作为退出码, 原因在于理论上栈长度可以远超 255，而退出码不行

3. peek 函数， 提取当前栈顶的数据, 栈指针无变化, 栈空时, 返回空

peek() {
    if ! ise; then
        local v=${__Stacking__[-1]}
        if [ "$1" ]; then
            local v_name=$1 
            eval "$v_name=\"$v\""
        fi
    fi    
}

参数可选. 非空时为接收数据的变量名（即输出参数，见本连载基础之一）, 返回后该变量被赋值. 空则被忽略

4. etop 函数， 清空栈顶数据, 栈指针减 1

etop() {
    ! ise &&  unset __Stacking__[-1] || :
}

该函数无参数，无返回值， 仅仅作为 peek 后的堆栈平衡之用, 等效于无参数调用 下面的 pop 函数

5. pop 函数， 提取当前栈顶的数据, 栈指针减 1

pop() {
    peek $1
    ! ise &&  unset __Stacking__[-1] || :
}

该函数是在 peek 的基础上, 添加栈顶数据出栈(如果栈未空)，如果对栈顶值不感兴趣，只是为了平衡堆栈， 则 pop 即可, 等效于 etop

6. stack_status 函数， 打印栈状态。主要用于调试

stack_status(){
    local idx=0
    for idx in ${!__Stacking__[@]};do
         printf "[%s]=(%s) " $idx "${__Stacking__[idx]}"
    done
    # 去掉最后一个不必要的空格
    [ $idx -ne 0 ] && printf "\b" || :
}

【测试】

新建测试文件 test.sh

   # 根据实际文件位置修改路径
    source ./stack.sh
    way(){
        # 检查结果, (包括 ascii 码)
        # $1: hint
        _check(){
            local ascii value
            echo -e "\t$1) stack:<$(stack_status)>"
            for v_name in v1 v2 v3; do
                value=${!v_name}
                ascii=$(echo -n "$value" | od -A n -t u1)
                echo -e "\t\t $v_name=<$value>, length=<${#value}>"
                echo -e "\t\t ascii=<$ascii>"
                echo "---------------------"
            done 
        }

        local v1 v2 v3
        echo "注意 v1 的末尾换行符 ascii 码为 10"
        v1=$'hello\tworld\n'
        v2=
        v3=
        push v1     # 压入变量名
        push IFS    # 压入值 IFS, 默认为 $' \t\n'
        _check 1

        peek v2
        _check 2

        etop           # 平衡堆栈
        _check 3

        pop v3
        _check 4
    }
    clear
    way

结果如下：

注意 v1 的末尾换行符 ascii 码为 10
        1) stack:<[0]=(hello    world
) [1]=(
)>
                 v1=<hello      world
>, length=<12>
                 ascii=< 104 101 108 108 111   9 119 111 114 108 100  10>
---------------------
                 v2=<>, length=<0>
                 ascii=<>
---------------------
                 v3=<>, length=<0>
                 ascii=<>
---------------------
        2) stack:<[0]=(hello    world
) [1]=(
)>
                 v1=<hello      world
>, length=<12>
                 ascii=< 104 101 108 108 111   9 119 111 114 108 100  10>
---------------------
                 v2=<
>, length=<3>
                 ascii=<  32   9  10>
---------------------
                 v3=<>, length=<0>
                 ascii=<>
---------------------
        3) stack:<[0]=(hello    world
) >
                 v1=<hello      world
>, length=<12>
                 ascii=< 104 101 108 108 111   9 119 111 114 108 100  10>
---------------------
                 v2=<
>, length=<3>
                 ascii=<  32   9  10>
---------------------
                 v3=<>, length=<0>
                 ascii=<>
---------------------
        4) stack:<>
                 v1=<hello      world
>, length=<12>
                 ascii=< 104 101 108 108 111   9 119 111 114 108 100  10>
---------------------
                 v2=<
>, length=<3>
                 ascii=<  32   9  10>
---------------------
                 v3=<hello      world
>, length=<12>
                 ascii=< 104 101 108 108 111   9 119 111 114 108 100  10>
---------------------

正常。

注意，pop 和 peek 采用输出参数而不是返回值的方式获取栈顶值，主要原因有两点：

  1. echo / printf 返回的数据， 末尾的换行符（如果有）会被掐掉;
  2. local result=$(pop) 的调用形式，其实已经创建了子 shell，对于有些场景， 例如 bash 选项的压入弹出语意上会不够严谨，甚至会得到错误的结果，该问题在 bash 选项的专用堆栈函数 pusht / popt 介绍时还有论述 。

 

Tags: