搜尋

首頁 >後端開發 >php教程 >PHP主| PHP開發人員的數據結構：堆棧和隊列

PHP主| PHP開發人員的數據結構：堆棧和隊列

Christopher Nolan
Christopher Nolan原創
2025-02-23 11:35:39123瀏覽

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
    上一篇：有效地使用PHP流下一篇：暫無

    相關文章

    看更多