實戰(zhàn)PHP數(shù)據(jù)結(jié)構(gòu)基礎之棧

banana_pi 發(fā)布于2019-07-01 10:08 / 2692人閱讀

摘要：棧和隊列棧和隊列和之前講到的實戰(zhàn)數(shù)據(jù)結(jié)構(gòu)基礎之雙鏈表一樣都是線性結(jié)構(gòu)。來看基于數(shù)組的棧實現(xiàn)得益于強大的結(jié)構(gòu)，我們輕而易舉的寫出來了棧的基本操作方法。專題系列基礎數(shù)據(jù)結(jié)構(gòu)專題系列目錄地址主要使用語法總結(jié)基礎的數(shù)據(jù)結(jié)構(gòu)和算法。

棧和隊列

棧和隊列和之前講到的實戰(zhàn)PHP數(shù)據(jù)結(jié)構(gòu)基礎之雙鏈表一樣都是線性結(jié)構(gòu)。

棧有什么特點

棧遵循后進先出的原則(LIFO)。這意味著棧只有一個出口用來壓入元素和彈出元素，當我們執(zhí)行壓入或者彈出操作的時候要注意棧是否已滿或者棧是否是空的。

常見操作

還是廢話不多說，直接來看我們對棧執(zhí)行的常用操作。

push

pop

top

isEmpty

...

PHP實現(xiàn)

首先我們定義一個StackInterface。

interface StackInterface
{
    public function push(string $item);
    public function pop();
    public function top();
    public function isEmpty();
}

來看基于數(shù)組的棧實現(xiàn)

class ArrStack implements StackInterface
{
    private $stack;
    private $limit;

    public function __construct(int $limit = 20)
    {
        $this->limit = $limit;
        $this->stack = [];
    }

    public function __get($val)
    {
        return $this->$val;
    }

    public function push(string $data = null)
    {
        if (count($this->stack) < $this->limit) {
            array_push($this->stack, $data);
        } else {
            throw new OverflowException("stack is overflow");
        }
    }

    public function pop()
    {
        if ($this->isEmpty()) {
            throw new UnderflowException("stack is empty");
        } else {
            return array_pop($this->stack);
        }
    }

    public function isEmpty()
    {
        return empty($this->stack);
    }

    public function top()
    {
        return end($this->stack);
    }

得益于PHP強大的array結(jié)構(gòu)，我們輕而易舉的寫出來了棧的基本操作方法。果然世界上最好的語言名不虛傳。

那有同學說了，你說棧和之前的鏈表都是線性結(jié)構(gòu)，那可不可以直接使用鏈表實現(xiàn)棧呢？這個問題非常犀利啊，答案是可以的。

可能機智的同學已經(jīng)猜到了，我之前已經(jīng)定義了一個棧接口，那棧的實現(xiàn)肯定不止只有上面一種哈。來看基于鏈表的實現(xiàn)。

class LinkedListStack implements StackInterface
{
    private $stack;
    private $limit;

    public function __construct(int $limit)
    {
        $this->limit = $limit;
        $this->stack = new LinkedList();
    }

    public function top()
    {
        return $this->stack->getNthNode($this->stack->getSize() - 1)->data;
    }

    public function isEmpty()
    {
        return $this->stack->getSize() === 0;
    }

    public function pop()
    {
        if ($this->isEmpty()) {
            throw new UnderflowException("stack is empty");
        } else {
            $lastItem = $this->top();
            $this->stack->deleteLast();

            return $lastItem;
        }
    }

    public function push(string $item)
    {
        if ($this->stack->getSize() < $this->limit) {
            $this->stack->insert($item);
        } else {
            throw new OverflowException("stack is overflow");
        }
    }

里面涉及到了之前的鏈表實現(xiàn)，不了解細節(jié)的同學可以去這里看看。有同學又問，那棧到底有什么用處？這個問題非常好，來看一個需求。

請實現(xiàn)一個數(shù)學表達式檢查類，輸入一個下面表達式，預期結(jié)果為true。

"8 * (9 -2) + { (4 * 5) / ( 2 * 2) }

下面的為false。

"5 * 8 * 9 / ( 3 * 2 ) )"

下面的也為false。

"[{ (2 * 7) + ( 15 - 3) ]"

自己想一下，再往下看實現(xiàn)。

class ExpressionChecker
{
    //$expressions[] = "8 * (9 -2) + { (4 * 5) / ( 2 * 2) }";
    //$expressions[] = "5 * 8 * 9 / ( 3 * 2 ) )";
    //$expressions[] = "[{ (2 * 7) + ( 15 - 3) ]";

    public function check(string $expression): bool
    {
        $stack = new SplStack();

        foreach (str_split($expression) as $item) {
            switch ($item) {
                case "{":
                case "[":
                case "(":
                    $stack->push($item);
                    break;

                case "}":
                case "]":
                case ")":
                    if ($stack->isEmpty()) return false;

                    $last = $stack->pop();

                    if (
                        $item == "{" && $last != "}" ||
                        $item == "(" && $last != ")" ||
                        $item == "[" && $last != "]"
                    )
                        return false;

                    break;
            }
        }

        if ($stack->isEmpty()) {
            return true;
        }

        return false;
    }
}

專題系列

PHP基礎數(shù)據(jù)結(jié)構(gòu)專題系列目錄地址：https://github.com/... 主要使用PHP語法總結(jié)基礎的數(shù)據(jù)結(jié)構(gòu)和算法。還有我們?nèi)粘HP開發(fā)中容易忽略的基礎知識和現(xiàn)代PHP開發(fā)中關于規(guī)范、部署、優(yōu)化的一些實戰(zhàn)性建議，同時還有對Javascript語言特點的深入研究。

云服務器 GPU云服務器零基礎實戰(zhàn)機器學習實戰(zhàn)php php實戰(zhàn) php 實戰(zhàn)經(jīng)典

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/28838.html

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

摘要：堆棧算法引子棧是計算機術(shù)語中比較重要的概念，實質(zhì)上棧就是一段內(nèi)存區(qū)域，但是棧滿足一定的特性，那就是只有一個口，具有先入后出的特性，這種特性在計算機中有很廣泛的運用。 /** * PHP堆棧算法 * Created on 2017-4-27 * Author entner * Email 1185087164@qq.com */ 引子 ????棧...

array_huang 2019-06-27 16:22 評論0 收藏0
利用PHP實現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)之棧（小白系列文章四）

摘要：堆棧算法引子棧是計算機術(shù)語中比較重要的概念，實質(zhì)上棧就是一段內(nèi)存區(qū)域，但是棧滿足一定的特性，那就是只有一個口，具有先入后出的特性，這種特性在計算機中有很廣泛的運用。 /** * PHP堆棧算法 * Created on 2017-4-27 * Author entner * Email 1185087164@qq.com */ 引子 ????棧...

yankeys 2019-06-28 13:56 評論0 收藏0
數(shù)據(jù)結(jié)構(gòu)之棧（java版）

摘要：本文力求簡潔，只包含基礎的棧功能，不想將大片的代碼展示出來，讓讀者興趣索然，閱讀起來也十分費力，如有需要可以自行添加相關功能比如包中的類包含的，等等函數(shù)能力有限，有誤之處還請不吝賜教定義內(nèi)部類用于存儲棧元素指向下一個棧元素的泛型元素方法方法本文力求簡潔，只包含基礎的棧功能，不想將大片的代碼展示出來，讓讀者興趣索然，閱讀起來也十分費力，如有需要可以自行添加相關功能比如java.util...

hizengzeng 2019-08-14 18:03 評論0 收藏0
學習數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊列

摘要：于是翻出了機房里的這本學習數(shù)據(jù)結(jié)構(gòu)與算法開始學習程序員的基礎知識。這本書用了我最熟悉的來實現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)和算法，而且書很薄，可以說是一本不錯的入門教程。隊列在頭部刪除元素，尾部添加元素。本系列所有文章：第一篇文章：學習數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊列第二篇文章：學習數(shù)據(jù)結(jié)構(gòu)與算法之鏈表第三篇文章：學習數(shù)據(jù)結(jié)構(gòu)與算法之集合第四篇文章：學習數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表第五篇文章：學習數(shù)據(jù)結(jié)構(gòu)與算...

pingan8787 2019-08-20 18:37 評論0 收藏0
Python - 收藏集 - 掘金

摘要：首發(fā)于我的博客線程池進程池網(wǎng)絡編程之同步異步阻塞非阻塞后端掘金本文為作者原創(chuàng)，轉(zhuǎn)載請先與作者聯(lián)系。在了解的數(shù)據(jù)結(jié)構(gòu)時，容器可迭代對象迭代器使用進行并發(fā)編程篇二掘金我們今天繼續(xù)深入學習。 Python 算法實戰(zhàn)系列之棧 - 后端 - 掘金原文出處：安生??? 棧(stack)又稱之為堆棧是一個特殊的有序表，其插入和刪除操作都在棧頂進行操作，并且按照先進后出，后進先出的規(guī)則進行運作。如...

546669204 2019-07-31 10:57 評論0 收藏0