首页 > 编程语言 >PHP数据结构之栈

PHP数据结构之栈

时间:2024-07-08 10:19:19浏览次数:15  
标签:function PHP return 之栈 pop char push 数据结构 stack

本文由 ChatMoney团队出品

栈(Stack)是一种后进先出(Last In First Out, LIFO)的数据结构,它只允许在一端(称为栈顶)进行插入和删除操作。栈的应用非常广泛,例如在编程语言的函数调用中,每次函数调用都会将一个新的帧压入栈中,当函数返回时,该帧会被弹出。此外,栈还常用于解决某些算法问题,如括号匹配、深度优先搜索等。

栈的基本概念

  1. 栈的定义

栈是由一系列元素组成的集合,这些元素按照特定的顺序排列。栈的主要特点是只能在栈顶进行插入和删除操作。栈顶是最后一个被插入的元素所在的位置,而栈底则是第一个被插入的元素所在的位置。

  1. 栈的操作

栈主要有两种基本操作:

  • Push:向栈顶添加一个新元素。
  • Pop:从栈顶移除一个元素。

除了这两种基本操作外,还有一些辅助操作,如:

  • Top/Peek:查看栈顶元素但不移除它。
  • isEmpty:检查栈是否为空。
  • Size:获取栈中元素的个数。

PHP实现栈

在PHP中,我们可以使用数组来实现栈的功能。以下是一个简单的栈类实现:

class Stack {
    private $stack;

    public function __construct() {
        $this->stack = array();
    }

    // Push element onto stack
    public function push($item) {
        array_push($this->stack, $item);
    }

    // Pop element from stack
    public function pop() {
        if ($this->isEmpty()) {
            throw new UnderflowException("Stack is empty");
        }
        return array_pop($this->stack);
    }

    // Peek at the top item on the stack
    public function peek() {
        return $this->stack[count($this->stack) - 1];
    }

    // Check if the stack is empty
    public function isEmpty() {
        return empty($this->stack);
    }

    // Get the number of items in the stack
    public function size() {
        return count($this->stack);
    }
}

在这个实现中,我们使用了PHP的array_pusharray_pop函数来分别实现栈的Push和Pop操作。同时,我们还提供了peekisEmptysize方法来满足其他辅助操作的需求。

栈的应用实例

  1. 括号匹配

括号匹配是一个经典的使用栈解决的问题。我们可以使用栈来检查一个字符串中的括号是否正确匹配。以下是一个简单的示例:

function isValidParentheses($s) {
    $stack = new Stack();
    for ($i = 0; $i < strlen($s); $i++) {
        $char = $s[$i];
        if ($char == '(' || $char == '{' || $char == '[') {
            $stack->push($char);
        } else {
            if ($stack->isEmpty()) {
                return false;
            }
            $top = $stack->pop();
            if (($char == ')' && $top != '(') ||
                ($char == '}' && $top != '{') ||
                ($char == ']' && $top != '[')) {
                return false;
            }
        }
    }
    return $stack->isEmpty();
}

  1. 逆波兰表达式求值

逆波兰表达式(Reverse Polish Notation, RPN)是一种后缀表达式,它的运算符位于操作数之后。我们可以使用栈来求解逆波兰表达式的值。以下是一个示例:

function evalRPN($tokens) {
    $stack = new Stack();
    foreach ($tokens as $token) {
        if (is_numeric($token)) {
            $stack->push($token);
        } else {
            $b = $stack->pop();
            $a = $stack->pop();
            switch ($token) {
                case '+':
                    $stack->push($a + $b);
                    break;
                case '-':
                    $stack->push($a - $b);
                    break;
                case '*':
                    $stack->push($a * $b);
                    break;
                case '/':
                    $stack->push($a / $b);
                    break;
            }
        }
    }
    return $stack->pop();
}

总结

栈作为一种重要的数据结构,具有广泛的应用场景,如括号匹配、逆波兰表达式求值等。掌握栈的原理和实现方法,对于提高编程能力和解决实际问题是非常有帮助的。

关于我们

本文由ChatMoney团队出品,ChatMoney专注于AI应用落地与变现,我们提供全套、持续更新的AI源码系统与可执行的变现方案,致力于帮助更多人利用AI来变现,欢迎进入ChatMoney获取更多AI变现方案!

标签:function,PHP,return,之栈,pop,char,push,数据结构,stack
From: https://www.cnblogs.com/ChatMoney/p/18289407

相关文章

  • (麒麟Linux+PHP8+KingBase)麒麟Linux系统安装PHP8及人大金仓KingBase应用
    一、PHP8安装1.1环境CPU内核:aarch64OS:麒麟V104.19.90-23.34.v2101.ky10Web中间件:东方通THS/V6php:8.2.0db:KingbaseESV8R61.2下载https://www.php.net/releases/下载地址:https://www.php.net/distributions/php-8.2.0.tar.gz1.3解压cd/optsudotar-z......
  • SSM-企业人事信息管理系统-98194(免费领源码)可做计算机毕业设计JAVA、PHP、爬虫、APP、
    企业人事信息管理系统的设计与实现摘 要由于数据库和数据仓库技术的快速发展,企业人事信息管理系统建设越来越向模块化、智能化、自我服务和管理科学化的方向发展。人事管理系统对处理对象和服务对象,自身的系统结构,处理能力,都将适应技术发展的要求发生重大的变化。企业人事......
  • PHP转Go系列 | ThinkPHP与Gin框架之API接口签名设计实践
    大家好,我是码农先森。回想起以前用模版渲染数据的岁月,那时都没有API接口开发的概念。PHP服务端和前端HTML、CSS、JS代码混合式开发,也不分前端、后端程序员,大家都是全干工程师。随着前后端分离、移动端开发的兴起,用后端渲染数据的开发方式效率低下,已经不能满足业务对需求快速......
  • 关于数据结构的学习心得
    介绍在备赛xcpc时,其实除了数据结构以外,绝大部分常用的大纲知识都学习了,但数据结构确实是练得最多的,本文主要介绍一下个人是如何学习数据结构的。数据结构概述数据结构大概是很多人比较抵触系统学习的东西,因为许多数据结构来说,光是板子就比其他领域的算法长很多。比如线段树,可......
  • 数据结构:二叉树的顺序结构及代码实现
    一:二叉树的顺序结构普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操......
  • 数据结构:二叉树的链式结构及代码实现
    一.二叉树的链式结构1.1前置说明在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成本,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头......
  • 数据结构小学期第七天
    今天继续学习Springboot的项目实战今天了解了一下,如何在自己登陆后,还能让界面知道是谁在进行操作,这个功能的实现需要JWT令牌的作用我们需要先引入一个JWT依赖1<!--java-JWT坐标-->2<dependency>3<groupId>com.auth0</groupId>4<artifa......
  • SpringBoot-校园疫情防控系统-93033(免费领源码+开发文档)可做计算机毕业设计JAVA、PHP
    springboot校园疫情防控系统摘 要信息化社会内需要与之针对性的信息获取途径,但是途径的扩展基本上为人们所努力的方向,由于站在的角度存在偏差,人们经常能够获得不同类型信息,这也是技术最为难以攻克的课题。针对校园疫情防控等问题,对校园疫情防控进行研究分析,然后开发设计出......
  • 基于Django+微信小程序的旅游资源信息管理系统(免费领源码+数据库)可做计算机毕业设计JA
    django广西-东盟旅游资源信息管理系统小程序摘 要在社会快速发展和人们生活水平提高的影响下,旅游产业蓬勃发展,旅游形式也变得多样化,使旅游资源信息的管理变得比过去更加困难。依照这一现实为基础,设计一个快捷而又方便的基于小程序的旅游资源信息管理系统是一项十分重要并且......
  • [数据结构]堆
    建堆的两种方式自上而下这种方式的思路是,每插入一个节点,就向上比较,判断是否需要与其父节点进行交换,分析这种方式的时间复杂度,假设树的高度为h,以下均考虑最坏情况,也就是每一个节点都调整到根第一层的1个节点不需要调整第二层的2个节点,每个节点向上调整1次,2*1,第三层的4个节点......