搜索

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

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

Christopher Nolan
Christopher Nolan原创
2025-02-23 11:35:39129浏览

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) < $this->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><?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><?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><?php
</span></span><span><span>echo $myBooks->top(); // outputs 'A Feast for Crows'</span></span>
    您可以首先看到堆栈在最后一个。最后添加到堆栈中的任何内容都是第一个要删除的。如果您继续弹出物品直到堆栈为空，则将获得堆栈下流运行时异常。 
    <span><span><?php
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Feast for Crows'</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>
    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>

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

    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) < $this->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>
    为了以相反的顺序穿越堆栈，我们只需将迭代器模式设置为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>

    队列

    如果您曾经在超市结帐处遇到过一条线，那么您会知道排队的第一人是首先服务的。在计算机术语中，队列是另一种抽象数据类型，它首先在的基础上或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) < $this->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>
    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><?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>
    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>

    摘要

    在本文中，您已经看到了如何在编程中使用堆栈和队列抽象数据类型。这些数据结构是抽象的，因为它们是由可以自身执行的操作定义的，从而在其实现和基础数据之间创建了一个墙。 这些结构还受到此类操作的影响的约束：您只能从堆栈顶部添加或删除项目，并且只能从队列的前面删除项目，或在队列的后部添加项目。 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中文网其他相关文章！

    php sentinel less String Array Object NULL define if for while include continue using class Interface Property Collection pointer number function default this overflow table database Access Other
    声明：
    本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn
    上一篇：Using PHP Streams Effectively下一篇：PHP Master | Manage Complexity with the Facade Pattern

    相关文章

    查看更多