搜索
首页后端开发php教程PHP主| PHP开发人员的数据结构:堆栈和队列

PHP主| PHP开发人员的数据结构:堆栈和队列

数据结构,或抽象数据类型 (ADT)是一个模型,该模型由可以自身执行的操作集合来定义,并且受这些操作影响的约束限制。它在对基础数据和如何完成之间可以做的事情之间创建了一个墙。 我们大多数人都熟悉正常日常用法中的堆栈和队列,但是超市队列和自动售货机与数据结构有什么关系?让我们找出答案。在本文中,我将向您介绍两种基本的抽象数据类型 - 堆栈和队列 - 它们起源于日常用法。

钥匙要点

  • 抽象数据类型(ADT)是由可以在其上执行的一组操作来定义的。堆栈和队列是日常用法中起源的基本ADT。在计算机科学中,堆栈是一个顺序集合,其中最后放置的对象是第一个删除(lifo),而队列则以先入为先的,首先为基础(FIFO)进行操作。
  • >可以使用数组实现堆栈,因为它们已经提供了推动和弹出操作。定义堆栈的基本操作包括init(创建堆栈),按下(在顶部添加一个项目),pop(删除最后一个项目),顶部(查看顶部的项目而不删除它)和Isempty(返回堆栈是否不包含项目)。
  • > PHP中的SPL扩展提供了一组标准数据结构,包括Splstack类。以双关联列表实现的Splstack类提供了实现可遍历堆栈的能力。将其实现的阅读清单类可以穿越堆栈前向(自上而下)和向后(自下而上)。
  • 排队的另一种抽象数据类型是以先入为先的(FIFO)为基础的。定义队列的基本操作包括init(创建队列),构建(将项目添加到末端),decqueue(从前面删除项目)和Isempty(返回队列是否不再包含项目)。 PHP中的Splqueue类(也使用双关联列表都实现)允许实现队列。
  • stacks
  • 通常,堆栈是一堆通常以层次排列的物体 - 例如,桌子上的一堆书籍或学校自助餐厅中的一堆托盘。在计算机科学的说法中,堆栈是一个具有特定属性的顺序集合,因为将其放在堆栈上的最后一个对象将是第一个对象。此属性通常称为

在第一个或lifo中的最后一次。糖果,芯片和香烟自动售货机以相同的原则运行;首先将加载在机架中的最后一个物品被分配。 从抽象的术语中,堆栈是一个线性列表,其中所有添加(“推”)和(“ pop”)列表中的所有添加列表都仅限于一端 - 定义为“ top”(堆栈的“ top”) )。定义堆栈的基本操作是:

init - 创建堆栈。
  • >推 - 在堆栈顶部添加一个项目。
  • pop - 删除添加到堆栈顶部的最后一项。>
  • >顶部 - 查看堆栈顶部的项目而不删除它。
  • >
  • isempty - 返回堆栈是否不包含项目。>
  • 堆栈也可以实现以具有最大容量。如果堆栈已满,并且没有足够的插槽来接受新实体,则据说它是
  • 溢出 - 因此,“堆栈溢出”短语。同样,如果在空堆栈上尝试了POP操作,则会发生“堆栈下流”。 知道我们的堆栈是由LIFO属性和许多基本操作(尤其是Push and Pop)定义的,因此我们可以使用数组轻松实现堆栈,因为数组已经提供了推动和弹出操作。 这是我们简单的堆栈的样子: 在此示例中,我使用了array_unshift()和array_shift(),而不是array_push()和array_pop(),以便堆栈的第一个元素始终是顶部。您可以使用array_push()和array_pop()维持语义一致性,在这种情况下,堆栈的第n个元素成为顶部。这两种方式都没有任何区别,因为抽象数据类型的全部目的是从其实际实施中抽象对数据进行操纵。 让我们在堆栈中添加一些项目: 从堆栈中删除一些项目:
    <span><span><?php </span></span><span><span>class ReadingList
    </span></span><span><span>{
    </span></span><span>    <span>protected $stack;
    </span></span><span>    <span>protected $limit;
    </span></span><span>    
    </span><span>    <span>public function __construct($limit = 10) {
    </span></span><span>        <span>// initialize the stack
    </span></span><span>        <span>$this->stack = array();
    </span></span><span>        <span>// stack can only contain this many items
    </span></span><span>        <span>$this->limit = $limit;
    </span></span><span>    <span>}
    </span></span><span>
    </span><span>    <span>public function push($item) {
    </span></span><span>        <span>// trap for stack overflow
    </span></span><span>        <span>if (count($this->stack) limit) {
    </span></span><span>            <span>// prepend item to the start of the array
    </span></span><span>            <span>array_unshift($this->stack, $item);
    </span></span><span>        <span>} else {
    </span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
    </span></span><span>        <span>}
    </span></span><span>    <span>}
    </span></span><span>
    </span><span>    <span>public function pop() {
    </span></span><span>        <span>if ($this->isEmpty()) {
    </span></span><span>            <span>// trap for stack underflow
    </span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
    </span></span><span>	  <span>} else {
    </span></span><span>            <span>// pop item from the start of the array
    </span></span><span>            <span>return array_shift($this->stack);
    </span></span><span>        <span>}
    </span></span><span>    <span>}
    </span></span><span>
    </span><span>    <span>public function top() {
    </span></span><span>        <span>return current($this->stack);
    </span></span><span>    <span>}
    </span></span><span>
    </span><span>    <span>public function isEmpty() {
    </span></span><span>        <span>return empty($this->stack);
    </span></span><span>    <span>}
    </span></span><span><span>}</span></span></span>
    让我们看看堆栈顶部是什么:
    <span><span><?php </span></span><span><span>$myBooks = new ReadingList();
    </span></span><span>
    </span><span><span>$myBooks->push('A Dream of Spring');
    </span></span><span><span>$myBooks->push('The Winds of Winter');
    </span></span><span><span>$myBooks->push('A Dance with Dragons');
    </span></span><span><span>$myBooks->push('A Feast for Crows');
    </span></span><span><span>$myBooks->push('A Storm of Swords'); 
    </span></span><span><span>$myBooks->push('A Clash of Kings');
    </span></span><span><span>$myBooks->push('A Game of Thrones');</span></span></span>
    如果我们删除它怎么办?
    <span><span><?php </span></span><span><span>echo $myBooks->pop(); // outputs 'A Game of Thrones'
    </span></span><span><span>echo $myBooks->pop(); // outputs 'A Clash of Kings'
    </span></span><span><span>echo $myBooks->pop(); // outputs 'A Storm of Swords'</span></span></span>
    如果我们添加新项目?
    <span><span><?php </span></span><span><span>echo $myBooks->top(); // outputs 'A Feast for Crows'</span></span></span>
    您可以首先看到堆栈在最后一个。最后添加到堆栈中的任何内容都是第一个要删除的。如果您继续弹出物品直到堆栈为空,则将获得堆栈下流运行时异常。
    <span><span><?php </span></span><span><span>echo $myBooks->pop(); // outputs 'A Feast for Crows'</span></span></span>
    哦,您好…PHP提供了一个堆栈跟踪,显示了程序执行呼叫堆栈事先,并且要截至例外!
    <span><span><?php </span></span><span><span>$myBooks->push('The Armageddon Rag');
    </span></span><span><span>echo $myBooks->pop(); // outputs 'The Armageddon Rag'</span></span></span>
    splstack
    PHP Fatal error:  Uncaught exception 'RuntimeException' with message 'Stack is empty!' in /home/ignatius/Data Structures/code/array_stack.php:33
    Stack trace:
    #0 /home/ignatius/Data Structures/code/example.php(31): ReadingList->pop()
    #1 /home/ignatius/Data Structures/code/array_stack.php(54): include('/home/ignatius/...')
    #2 {main}
      thrown in /home/ignatius/Data Structures/code/array_stack.php on line 33
    SPL扩展提供了一组标准数据结构,包括Splstack类(PHP5> = 5.3.0)。 我们可以使用以下内容来实现相同的对象,尽管更简短,但使用以下方式:

    Splstack类实现了比我们最初定义的多种方法。这是因为Splstack被实现为双关联列表,该列表提供了实现可遍历堆栈的能力。 链接列表是另一种抽象数据类型本身,是用于表示特定序列的对象(节点)的线性集合,其中集合中的每个节点都保持一个指向集合中的下一个节点的指针。以最简单的形式,一个链接列表看起来像这样:

    <span><span><?php </span></span><span><span>class ReadingList extends SplStack
    </span></span><span><span>{
    </span></span><span><span>}</span></span></span>

    在双关联列表中,每个节点都有两个指示,每个指向集合中的下一个和上一个节点。这种类型的数据结构允许在两个方向上遍历遍历。

    PHP主| PHP开发人员的数据结构:堆栈和队列

    用十字(x)标记的节点表示空位或前哨节点,该节点指定了遍历路径的末端(即路径终端)。 由于ReadingList是作为splstack实现的,因此我们可以将堆栈前进(自上而下)向后(自下而上)。 Splstack的默认遍历模式是Lifo:
    <span><span><?php </span></span><span><span>class ReadingList
    </span></span><span><span>{
    </span></span><span>    <span>protected $stack;
    </span></span><span>    <span>protected $limit;
    </span></span><span>    
    </span><span>    <span>public function __construct($limit = 10) {
    </span></span><span>        <span>// initialize the stack
    </span></span><span>        <span>$this->stack = array();
    </span></span><span>        <span>// stack can only contain this many items
    </span></span><span>        <span>$this->limit = $limit;
    </span></span><span>    <span>}
    </span></span><span>
    </span><span>    <span>public function push($item) {
    </span></span><span>        <span>// trap for stack overflow
    </span></span><span>        <span>if (count($this->stack) limit) {
    </span></span><span>            <span>// prepend item to the start of the array
    </span></span><span>            <span>array_unshift($this->stack, $item);
    </span></span><span>        <span>} else {
    </span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
    </span></span><span>        <span>}
    </span></span><span>    <span>}
    </span></span><span>
    </span><span>    <span>public function pop() {
    </span></span><span>        <span>if ($this->isEmpty()) {
    </span></span><span>            <span>// trap for stack underflow
    </span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
    </span></span><span>	  <span>} else {
    </span></span><span>            <span>// pop item from the start of the array
    </span></span><span>            <span>return array_shift($this->stack);
    </span></span><span>        <span>}
    </span></span><span>    <span>}
    </span></span><span>
    </span><span>    <span>public function top() {
    </span></span><span>        <span>return current($this->stack);
    </span></span><span>    <span>}
    </span></span><span>
    </span><span>    <span>public function isEmpty() {
    </span></span><span>        <span>return empty($this->stack);
    </span></span><span>    <span>}
    </span></span><span><span>}</span></span></span>
    为了以相反的顺序穿越堆栈,我们只需将迭代器模式设置为FIFO(首先,首先):
    <span><span><?php </span></span><span><span>$myBooks = new ReadingList();
    </span></span><span>
    </span><span><span>$myBooks->push('A Dream of Spring');
    </span></span><span><span>$myBooks->push('The Winds of Winter');
    </span></span><span><span>$myBooks->push('A Dance with Dragons');
    </span></span><span><span>$myBooks->push('A Feast for Crows');
    </span></span><span><span>$myBooks->push('A Storm of Swords'); 
    </span></span><span><span>$myBooks->push('A Clash of Kings');
    </span></span><span><span>$myBooks->push('A Game of Thrones');</span></span></span>

    队列

    如果您曾经在超市结帐处遇到过一条线,那么您会知道排队的第一人是首先服务的。在计算机术语中,队列是另一种抽象数据类型,它首先在的基础上或FIFO上以的方式运行。库存也以FIFO进行管理,特别是如果此类物品具有易腐烂性质。 定义队列的基本操作是:
    • init - 创建队列。
    • 候选 - 在队列的“端”(尾巴)中添加一个项目。
    • Dequeue - 从队列的“正面”(头)中删除项目。
    • isempty - 返回队列是否不包含任何项目。
    • >
    由于还使用双关联列表实现了Splqueue,因此在此上下文中,Top和Pop的语义含义被逆转。让我们重新定义我们的阅读清单课作为队列:
    <span><span><?php </span></span><span><span>class ReadingList
    </span></span><span><span>{
    </span></span><span>    <span>protected $stack;
    </span></span><span>    <span>protected $limit;
    </span></span><span>    
    </span><span>    <span>public function __construct($limit = 10) {
    </span></span><span>        <span>// initialize the stack
    </span></span><span>        <span>$this->stack = array();
    </span></span><span>        <span>// stack can only contain this many items
    </span></span><span>        <span>$this->limit = $limit;
    </span></span><span>    <span>}
    </span></span><span>
    </span><span>    <span>public function push($item) {
    </span></span><span>        <span>// trap for stack overflow
    </span></span><span>        <span>if (count($this->stack) limit) {
    </span></span><span>            <span>// prepend item to the start of the array
    </span></span><span>            <span>array_unshift($this->stack, $item);
    </span></span><span>        <span>} else {
    </span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
    </span></span><span>        <span>}
    </span></span><span>    <span>}
    </span></span><span>
    </span><span>    <span>public function pop() {
    </span></span><span>        <span>if ($this->isEmpty()) {
    </span></span><span>            <span>// trap for stack underflow
    </span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
    </span></span><span>	  <span>} else {
    </span></span><span>            <span>// pop item from the start of the array
    </span></span><span>            <span>return array_shift($this->stack);
    </span></span><span>        <span>}
    </span></span><span>    <span>}
    </span></span><span>
    </span><span>    <span>public function top() {
    </span></span><span>        <span>return current($this->stack);
    </span></span><span>    <span>}
    </span></span><span>
    </span><span>    <span>public function isEmpty() {
    </span></span><span>        <span>return empty($this->stack);
    </span></span><span>    <span>}
    </span></span><span><span>}</span></span></span>
    spldoublylinkedlist 还实现了ArrayAccess接口,因此您还可以将项目添加到Splequeue和Splstack中,作为数组元素:
    <span><span><?php </span></span><span><span>$myBooks = new ReadingList();
    </span></span><span>
    </span><span><span>$myBooks->push('A Dream of Spring');
    </span></span><span><span>$myBooks->push('The Winds of Winter');
    </span></span><span><span>$myBooks->push('A Dance with Dragons');
    </span></span><span><span>$myBooks->push('A Feast for Crows');
    </span></span><span><span>$myBooks->push('A Storm of Swords'); 
    </span></span><span><span>$myBooks->push('A Clash of Kings');
    </span></span><span><span>$myBooks->push('A Game of Thrones');</span></span></span>
    从队列的前面删除项目:
    <span><span><?php </span></span><span><span>echo $myBooks->pop(); // outputs 'A Game of Thrones'
    </span></span><span><span>echo $myBooks->pop(); // outputs 'A Clash of Kings'
    </span></span><span><span>echo $myBooks->pop(); // outputs 'A Storm of Swords'</span></span></span>
    Enqueue()是推动()的别名,但请注意,Dequeue()不是POP()的别名; POP()在队列的上下文中具有不同的含义和功能。如果我们在此处使用了pop(),它将从队列的末端(尾巴)删除违反FIFO规则的项目。 同样,要查看队列的前面(头),我们必须使用bottol()而不是top():
    <span><span><?php </span></span><span><span>echo $myBooks->top(); // outputs 'A Feast for Crows'</span></span></span>

    摘要

    在本文中,您已经看到了如何在编程中使用堆栈和队列抽象数据类型。这些数据结构是抽象的,因为它们是由可以自身执行的操作定义的,从而在其实现和基础数据之间创建了一个墙。 这些结构还受到此类操作的影响的约束:您只能从堆栈顶部添加或删除项目,并且只能从队列的前面删除项目,或在队列的后部添加项目。 Alexandre Dulaunoy的图像通过Flickr 经常询问有关PHP数据结构的问题(常见问题解答)

    > PHP中的数据结构的不同类型?阵列是PHP中最常见和通用的数据结构。他们可以容纳任何类型的数据,包括其他数组,并且可以索引或关联。 PHP中的对象是类的实例,可以具有属性和方法。资源是包含对外部资源的参考的特殊变量,例如数据库连接。

    >

    >我如何在PHP?

    中实现堆栈?最后,首先)原理。在PHP中,您可以使用Splstack类实现堆栈。您可以使用push()方法将元素推到堆栈上,然后使用pop()方法将弹出元素从堆栈中。

    > php?

    中的数组和对象之间有什么区别PHP中的数组和对象都是数据结构的类型,但是它们具有一些关键差异。数组是值的简单列表,而对象是类的实例,可以具有属性和方法。数组可以索引或关联,而对象始终使用字符串键。阵列更具通用性,更易于使用,而对象则提供了更多的结构和封装。>

    >我如何使用数据结构来提高我的PHP代码的性能? 使用正确的数据结构可以显着提高您的PHP代码的性能。例如,如果您需要存储大量元素并经常搜索特定元素,则使用哈希表或集合比使用数组要快得多。同样,如果您需要在两端经常添加和删除元素,那么使用deque比使用数组更有效。

    >

    >

    >如何在php?

    >中实现队列FIFO(首先,首先)原则。在PHP中,您可以使用Splqueue类实现队列。您可以使用eNqueue()方法将元素加入队列,并使用Dequeue()方法。 🎜>堆栈和队列都是数据结构的两种类型,但是它们在添加和删除元素的方式上具有关键区别。一个堆栈遵循LIFO(最后,首先)原理,这意味着添加的最后一个元素是第一个要删除的元素。另一方面,队列遵循FIFO(首先,首先)原理,这意味着添加的第一个元素是要删除的第一个元素。

    >我如何在PHP中使用Splheap类? PHP中的SPLHEAP类是实现堆的数据结构。堆是一种二进制树,每个父节点小于或等于其子节点。您可以使用splheap类创建一个小蜂巢或最大蜂座,并在堆中添加,删除和访问元素。

    >在PHP中使用数据结构有什么好处? >

    使用PHP中的数据结构可以提供多种好处。它们可以帮助您以更高效和合乎逻辑的方式组织数据,这可以使您的代码易于理解和维护。它们还可以提高您的代码性能,尤其是在处理大量数据或复杂操作时。

    >

    >如何在PHP中实现二进制树?每个节点最多有两个孩子的数据结构,称为左子女和右子女。在PHP中,您可以使用具有该属性的属性和左右子女的属性实现二进制树。然后,您可以使用方法来添加,删除和搜索树中的节点。>

    以上是PHP主| PHP开发人员的数据结构:堆栈和队列的详细内容。更多信息请关注PHP中文网其他相关文章!

    声明
    本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
    如何检查PHP会话是否已经开始?如何检查PHP会话是否已经开始?Apr 30, 2025 am 12:20 AM

    在PHP中,可以使用session_status()或session_id()来检查会话是否已启动。1)使用session_status()函数,如果返回PHP_SESSION_ACTIVE,则会话已启动。2)使用session_id()函数,如果返回非空字符串,则会话已启动。这两种方法都能有效地检查会话状态,选择使用哪种方法取决于PHP版本和个人偏好。

    描述一个场景,其中使用会话在Web应用程序中至关重要。描述一个场景,其中使用会话在Web应用程序中至关重要。Apr 30, 2025 am 12:16 AM

    sessionsarevitalinwebapplications,尤其是在commercePlatform之前。

    如何管理PHP中的并发会话访问?如何管理PHP中的并发会话访问?Apr 30, 2025 am 12:11 AM

    在PHP中管理并发会话访问可以通过以下方法:1.使用数据库存储会话数据,2.采用Redis或Memcached,3.实施会话锁定策略。这些方法有助于确保数据一致性和提高并发性能。

    使用PHP会话的局限性是什么?使用PHP会话的局限性是什么?Apr 30, 2025 am 12:04 AM

    PHPsessionshaveseverallimitations:1)Storageconstraintscanleadtoperformanceissues;2)Securityvulnerabilitieslikesessionfixationattacksexist;3)Scalabilityischallengingduetoserver-specificstorage;4)Sessionexpirationmanagementcanbeproblematic;5)Datapersis

    解释负载平衡如何影响会话管理以及如何解决。解释负载平衡如何影响会话管理以及如何解决。Apr 29, 2025 am 12:42 AM

    负载均衡会影响会话管理,但可以通过会话复制、会话粘性和集中式会话存储解决。1.会话复制在服务器间复制会话数据。2.会话粘性将用户请求定向到同一服务器。3.集中式会话存储使用独立服务器如Redis存储会话数据,确保数据共享。

    说明会话锁定的概念。说明会话锁定的概念。Apr 29, 2025 am 12:39 AM

    Sessionlockingisatechniqueusedtoensureauser'ssessionremainsexclusivetooneuseratatime.Itiscrucialforpreventingdatacorruptionandsecuritybreachesinmulti-userapplications.Sessionlockingisimplementedusingserver-sidelockingmechanisms,suchasReentrantLockinJ

    有其他PHP会议的选择吗?有其他PHP会议的选择吗?Apr 29, 2025 am 12:36 AM

    PHP会话的替代方案包括Cookies、Token-basedAuthentication、Database-basedSessions和Redis/Memcached。1.Cookies通过在客户端存储数据来管理会话,简单但安全性低。2.Token-basedAuthentication使用令牌验证用户,安全性高但需额外逻辑。3.Database-basedSessions将数据存储在数据库中,扩展性好但可能影响性能。4.Redis/Memcached使用分布式缓存提高性能和扩展性,但需额外配

    在PHP的上下文中定义'会话劫持”一词。在PHP的上下文中定义'会话劫持”一词。Apr 29, 2025 am 12:33 AM

    Sessionhijacking是指攻击者通过获取用户的sessionID来冒充用户。防范方法包括:1)使用HTTPS加密通信;2)验证sessionID的来源;3)使用安全的sessionID生成算法;4)定期更新sessionID。

    See all articles

    热AI工具

    Undresser.AI Undress

    Undresser.AI Undress

    人工智能驱动的应用程序,用于创建逼真的裸体照片

    AI Clothes Remover

    AI Clothes Remover

    用于从照片中去除衣服的在线人工智能工具。

    Undress AI Tool

    Undress AI Tool

    免费脱衣服图片

    Clothoff.io

    Clothoff.io

    AI脱衣机

    Video Face Swap

    Video Face Swap

    使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

    热工具

    SublimeText3 Linux新版

    SublimeText3 Linux新版

    SublimeText3 Linux最新版

    螳螂BT

    螳螂BT

    Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

    安全考试浏览器

    安全考试浏览器

    Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

    适用于 Eclipse 的 SAP NetWeaver 服务器适配器

    适用于 Eclipse 的 SAP NetWeaver 服务器适配器

    将Eclipse与SAP NetWeaver应用服务器集成。

    禅工作室 13.0.1

    禅工作室 13.0.1

    功能强大的PHP集成开发环境