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

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

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

棧和隊(duì)列

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

棧有什么特點(diǎn)

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

常見操作

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

push

pop

top

isEmpty

...

PHP實(shí)現(xiàn)

首先我們定義一個(gè)StackInterface。

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

來看基于數(shù)組的棧實(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強(qiáng)大的array結(jié)構(gòu)，我們輕而易舉的寫出來了棧的基本操作方法。果然世界上最好的語(yǔ)言名不虛傳。

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

可能機(jī)智的同學(xué)已經(jīng)猜到了，我之前已經(jīng)定義了一個(gè)棧接口，那棧的實(shí)現(xiàn)肯定不止只有上面一種哈。來看基于鏈表的實(shí)現(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");
        }
    }

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

請(qǐng)實(shí)現(xiàn)一個(gè)數(shù)學(xué)表達(dá)式檢查類，輸入一個(gè)下面表達(dá)式，預(yù)期結(jié)果為true。

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

下面的為false。

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

下面的也為false。

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

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

云服務(wù)器 GPU云服務(wù)器零基礎(chǔ)實(shí)戰(zhàn)機(jī)器學(xué)習(xí) 實(shí)戰(zhàn)php php實(shí)戰(zhàn) php 實(shí)戰(zhàn)經(jīng)典

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/28838.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

banana_pi

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

云計(jì)算廠商迎來升級(jí)拐點(diǎn)，邊緣計(jì)算布局或?qū)⒊蓻Q勝點(diǎn)

閱讀 3591·2021-11-24 10:19
【操作系統(tǒng)】—I/O設(shè)備的基本概念和分類

閱讀 3730·2021-09-30 09:47
開源一個(gè)代碼畫板工具

閱讀 1293·2019-08-30 15:56
XBlog： Vue+Express+Mongodb的全?？蓴U(kuò)展的完整博客系統(tǒng)

閱讀 790·2019-08-29 15:11
簡(jiǎn)單說一道JS閉包面試題

閱讀 905·2019-08-29 13:43
JavaScript的作用域和塊級(jí)作用域概念理解

閱讀 3570·2019-08-28 18:25
Web技術(shù)的前世今生（一）

閱讀 2160·2019-08-26 13:27
JavaScript設(shè)計(jì)模式系列五：適配器模式

閱讀 1439·2019-08-26 11:44

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

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

相關(guān)文章

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

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

數(shù)據(jù)結(jié)構(gòu)之棧（java版）

**學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列**

Python - 收藏集 - 掘金

發(fā)表評(píng)論

0條評(píng)論

banana_pi

男|高級(jí)講師

TA的文章

云計(jì)算廠商迎來升級(jí)拐點(diǎn)，邊緣計(jì)算布局或?qū)⒊蓻Q勝點(diǎn)

【操作系統(tǒng)】—I/O設(shè)備的基本概念和分類

開源一個(gè)代碼畫板工具

XBlog： Vue+Express+Mongodb的全?？蓴U(kuò)展的完整博客系統(tǒng)

簡(jiǎn)單說一道JS閉包面試題

JavaScript的作用域和塊級(jí)作用域概念理解

Web技術(shù)的前世今生（一）

JavaScript設(shè)計(jì)模式系列五：適配器模式

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

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

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！