实战PHP数据结构基础之栈

banana_pi 发布于2019-07-01 10:08 / 2697人阅读

摘要：栈和队列栈和队列和之前讲到的实战数据结构基础之双链表一样都是线性结构。来看基于数组的栈实现得益于强大的结构，我们轻而易举的写出来了栈的基本操作方法。专题系列基础数据结构专题系列目录地址主要使用语法总结基础的数据结构和算法。

栈和队列

栈和队列和之前讲到的实战PHP数据结构基础之双链表一样都是线性结构。

栈有什么特点

栈遵循后进先出的原则(LIFO)。这意味着栈只有一个出口用来压入元素和弹出元素，当我们执行压入或者弹出操作的时候要注意栈是否已满或者栈是否是空的。

常见操作

还是废话不多说，直接来看我们对栈执行的常用操作。

push

pop

top

isEmpty

...

PHP实现

首先我们定义一个StackInterface。

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

来看基于数组的栈实现

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结构，我们轻而易举的写出来了栈的基本操作方法。果然世界上最好的语言名不虚传。

那有同学说了，你说栈和之前的链表都是线性结构，那可不可以直接使用链表实现栈呢？这个问题非常犀利啊，答案是可以的。

可能机智的同学已经猜到了，我之前已经定义了一个栈接口，那栈的实现肯定不止只有上面一种哈。来看基于链表的实现。

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");
        }
    }

里面涉及到了之前的链表实现，不了解细节的同学可以去这里看看。有同学又问，那栈到底有什么用处？这个问题非常好，来看一个需求。

请实现一个数学表达式检查类，输入一个下面表达式，预期结果为true。

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

下面的为false。

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

下面的也为false。

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

自己想一下，再往下看实现。

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基础数据结构专题系列目录地址：https://github.com/... 主要使用PHP语法总结基础的数据结构和算法。还有我们日常PHP开发中容易忽略的基础知识和现代PHP开发中关于规范、部署、优化的一些实战性建议，同时还有对Javascript语言特点的深入研究。

GPU云服务器云服务器零基础实战机器学习实战php php实战 php 实战经典

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/28838.html

利用PHP实现常用的数据结构之栈（小白系列文章四）

摘要：堆栈算法引子栈是计算机术语中比较重要的概念，实质上栈就是一段内存区域，但是栈满足一定的特性，那就是只有一个口，具有先入后出的特性，这种特性在计算机中有很广泛的运用。 /** * PHP堆栈算法 * Created on 2017-4-27 * Author entner * Email 1185087164@qq.com */ 引子栈...

array_huang 2019-06-27 16:22 评论0 收藏0
利用PHP实现常用的数据结构之栈（小白系列文章四）

摘要：堆栈算法引子栈是计算机术语中比较重要的概念，实质上栈就是一段内存区域，但是栈满足一定的特性，那就是只有一个口，具有先入后出的特性，这种特性在计算机中有很广泛的运用。 /** * PHP堆栈算法 * Created on 2017-4-27 * Author entner * Email 1185087164@qq.com */ 引子栈...

yankeys 2019-06-28 13:56 评论0 收藏0
数据结构之栈（java版）

摘要：本文力求简洁，只包含基础的栈功能，不想将大片的代码展示出来，让读者兴趣索然，阅读起来也十分费力，如有需要可以自行添加相关功能比如包中的类包含的，等等函数能力有限，有误之处还请不吝赐教定义内部类用于存储栈元素指向下一个栈元素的泛型元素方法方法本文力求简洁，只包含基础的栈功能，不想将大片的代码展示出来，让读者兴趣索然，阅读起来也十分费力，如有需要可以自行添加相关功能比如java.util...

hizengzeng 2019-08-14 18:03 评论0 收藏0
学习数据结构与算法之栈与队列

摘要：于是翻出了机房里的这本学习数据结构与算法开始学习程序员的基础知识。这本书用了我最熟悉的来实现各种数据结构和算法，而且书很薄，可以说是一本不错的入门教程。队列在头部删除元素，尾部添加元素。本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构与算...

pingan8787 2019-08-20 18:37 评论0 收藏0
Python - 收藏集 - 掘金

摘要：首发于我的博客线程池进程池网络编程之同步异步阻塞非阻塞后端掘金本文为作者原创，转载请先与作者联系。在了解的数据结构时，容器可迭代对象迭代器使用进行并发编程篇二掘金我们今天继续深入学习。 Python 算法实战系列之栈 - 后端 - 掘金原文出处：安生栈(stack)又称之为堆栈是一个特殊的有序表，其插入和删除操作都在栈顶进行操作，并且按照先进后出，后进先出的规则进行运作。如...

546669204 2019-07-31 10:57 评论0 收藏0