利用PHP實現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)之棧（小白系列文章四）

yankeys 發(fā)布于2019-06-28 13:56 / 2000人閱讀

摘要：堆棧算法引子棧是計算機術(shù)語中比較重要的概念，實質(zhì)上棧就是一段內(nèi)存區(qū)域，但是棧滿足一定的特性，那就是只有一個口，具有先入后出的特性，這種特性在計算機中有很廣泛的運用。

/**
*    PHP堆棧算法
*    Created on 2017-4-27
*    Author     entner
*    Email     1185087164@qq.com
*/

引子

????棧是計算機術(shù)語中比較重要的概念，實質(zhì)上棧就是一段內(nèi)存區(qū)域，但是棧滿足一定的特性，那就是只有一個口，具有先入后出的特性，這種特性在計算機中有很廣泛的運用。其中幾個典型的運行如下：

計算機四則運算

樹的遞歸遍歷（所以樹和棧有緊密的聯(lián)系）

歷史記錄（文件流）

路徑追蹤

參看：棧的經(jīng)典運用

一、默寫棧結(jié)構(gòu)

默寫會讓你記憶更深刻，同時也會鍛煉抽象的邏輯思維，一邊看不懂，就多看幾遍，
再查一查相關(guān)資料，應(yīng)該問題不大，你甚至可以找張紙默寫一下。

/**
*    InitStack    初始化棧(單棧)
*    聲明一個類，構(gòu)造空數(shù)組、數(shù)組長度、棧頂指針3個屬性
    typedef int SElememtType    //構(gòu)造一個棧結(jié)構(gòu)數(shù)據(jù)類型實際可認為為整形
    typedef Struct{
        SElememtType data[MaxSize] //聲明棧空間
        int top                 //聲明棧頂指針
    }Stack;
*/

/**
*    Push    入棧(單棧)
*    實例化棧，并注入S，判斷，先后移棧頂指針，再新增棧頂元素
    
    Status Push(Stack *S, int e){
        //    判斷是否為滿棧    
        if(S->top == n-1){
            return error;    //滿棧
        }
        S->top =  S->top+1; //棧頂元素往后移動一位
        S->data[S->top] = e;//賦值給棧頂元素
        return ok;
    }
*/

/**
*    Pop    岀棧(單棧)
*    實例化棧，并注入S，判斷，先移除棧頂元素，再前移棧頂指針
    
    Status Pop(Stack *S, int e){
        if(S->top == -1){
            return error;    //空棧
        }
        e = S->data[S->top];
        unset(e)            //將棧頂元素移出（銷毀）
        S->top = S->top -1; //棧頂元素向前移動一位
    }
*/

/**
*    ClearStack    清空棧(單棧)
*    當棧存在且非空，遍歷棧頂元素并銷毀
    
    Status ClearStack(){
        if(S->top == -1){
            return error;    //空棧
        }
        for(S->top;S->top>1;S->top--){
            unset(S->data[S->top]);
        }
    }
*/

二、棧結(jié)構(gòu)基本實現(xiàn)

top == $this->MaxSize){
            return error;
        }
        /*    先后移棧頂指針后賦值    */
        $this->top = ++$this->top;
        $this->arr[$this->top] = $e;
        /*    輸出    */
        echo "棧頂指針現(xiàn)在所屬位置".$this->top."--";
        echo "$e 入棧成功"."
";
    }

/**
*TODO:岀棧操作
*/
    public function Pop(){
        /*    判斷：空棧則返回錯誤    */
        if($this->top == -1){
            return error;
        }
        /*    先移除棧元素針后前移棧頂指針    */
        $this->out = $this->arr[$this->top];
        $this->top = --$this->top;
        /*    輸出    */
        
        echo "棧頂指針現(xiàn)在所屬位置".$this->top."--";
        echo "$this->out  岀棧成功"."
";
        /*    銷毀移除元素    */
        unset($this->out);    
    }

/**
*TODO:程序結(jié)束時執(zhí)行
*/
    public function __destruct(){
        echo "over";
    }
}

    $stack = new Stack();
    $stack->Push("entner");//Push沒有加循環(huán)，可參看系列文章三-隊列
    $stack->Push("susan");
    $stack->Push("george");
    $stack->Pop();    //這里同樣可以使用循環(huán)操作
    $stack->Pop();
    $stack->Pop();

三、棧的應(yīng)用實現(xiàn)-遞歸-面包屑導(dǎo)航欄

【HTML-Web布局】

    目錄結(jié)構(gòu)如下：
   
        電腦---
                |
                |
                電腦配件---
                         |
                         |
                         顯示器
                         固態(tài)硬盤
                    
                網(wǎng)絡(luò)產(chǎn)品---
                         |
                         |
                         路由器
                         無線網(wǎng)卡
                         
                         
                         
                         
  



    
    



";        
    echo "".""."電腦配件".""."";
    echo         "".""."顯示器"."".""."
";            
    echo         "".""."固態(tài)硬盤"."".""."
";    
    echo "".""."網(wǎng)絡(luò)產(chǎn)品".""."";
    echo        "".""."路由器"."".""."
";
    echo        "".""."交換機"."".""."
";        
    echo "";
?>

【后臺邏輯執(zhí)行】

link();
        $res  = mysqli_query($conn,"select * from cat");

        $arr = array();//【注：這個$arr放在函數(shù)外面不可以，應(yīng)該是函數(shù)作用域限制】
        while($row = mysqli_fetch_array($res,MYSQLI_ASSOC)){
            /*    遍歷結(jié)果集放入數(shù)組        */
            $arr[] = $row;
        }
        while($cat_id>0){
            foreach($arr as $k=>$v){
                if($cat_id == $v["cat_id"]){
                $list[] = $v;
                $cat_id = $v["pid"];
                
                }
            }
            
        }
        return $list;
    }

    echo "";

    $list = array_reverse(mbx($cat_id));
    print_r($list);
    foreach($list as $k => $v){
        echo $v["Catname"].">";
    }
最后
如果您覺得這篇文章對您有幫助，請您為我點個贊吧:）畢竟敲字配上感冒還是有點...