數(shù)據(jù)結(jié)構(gòu)-PHP通過鏈表類對象實現(xiàn) "棧"

作者：愛因詩賢

來源：SegmentFault 思否社區(qū)

這篇文章是展示如何使用PHP語言實現(xiàn)的鏈表類(LinkedList)，然后通過鏈表來實現(xiàn)的?棧(Stack) 只能從棧頂添加元素，也只能從棧頂取出元素，是一種 Last In First Out(LIFO)，即?后進先出?的結(jié)構(gòu)。

1.output_stack_by_linked_list.php

這是一個調(diào)用和打印輸出結(jié)果的展示文件：

/** * 棧輸出相關(guān) */require 'StackByLinkedList.php';$stack = new StackByLinkedList();$stack->push('aa');$stack->push('bb');$stack->push('cc');$stack->push('dd');$stack->push('ee');$stack->push('ff');$stack->push('gg');$stack->push('hh');echo $stack->peek(); //查看棧頂元素，打印 hhecho "
";echo $stack->toString(); //打印棧數(shù)據(jù) hh->gg->ff->ee->dd->cc->bb->aa->nullecho "
";echo $stack->pop();  //出棧，打印 hhecho "
";echo $stack->toString(); //打印棧數(shù)據(jù) gg->ff->ee->dd->cc->bb->aa->null

2.StackByLinkedList 類

這是一個封裝好的?棧(Stack)?，通過實例化?鏈表類(LinkedList)?實現(xiàn)了入棧(push)和?出棧(pop)， 還有查看棧頂(peek):

require 'LinkedList.php';require 'Stack.php';class StackByLinkedList implements Stack{    //鏈表類對象，用于存放棧元素    protected $array = null;    /**     * 構(gòu)造函數(shù) 定義棧的容量     * ArrayStruct constructor.     * @param int $capacity     */    public function __construct() {        $this->array = new LinkedList();    }    /**     * 獲取棧大小     * @return int     */    public function getSize(): int {        return $this->array->getSize();    }    /**     * 判斷棧是否為空     * @return bool     */    public function isEmpty(): bool {        return $this->array->isEmpty();    }    /**     * 元素入棧     */    public function push($e): void {        $this->array->addFirst($e);    }    /**     * 出棧     * @return mixed     */    public function pop() {        return $this->array->removeFirst();    }    /**     * 查看棧頂元素     * @return mixed     */    public function peek() {        return $this->array->getFirst();    }    /**     * 將棧數(shù)組轉(zhuǎn)化為字符串     * @return string     */    public function toString(): string {        return $this->array->toString();    }}

Tips：這是一個Stack類，通過繼承 LinkedList 類實現(xiàn) Stack 的基本功能。

3.interface Stack

interface Stack{ /** * 獲取棧大小 * @return int */ public function getSize(): int; /** * 判斷棧是否為空 * @return bool */ public function isEmpty(): bool; /** * 元素入棧 */ public function push($e): void; /** * 出棧 * @return mixed */ public function pop(); /** * 查看棧頂元素 * @return mixed */ public function peek();}

4.LinkedList 類

這是封裝好的一個鏈表類，能實現(xiàn)鏈表的基本功能：

/** * 鏈表的實現(xiàn) * Class LinkedList */class LinkedList{    private $dummyHead;    private $size;    /**     * 初始化鏈表 null->null     * LinkedList constructor.     */    public function __construct() {        $this->dummyHead = new Node(null, null);        $this->size = 0;    }    /**     * 獲取鏈表大小     * @return int     */    public function getSize(): int {        return $this->size;    }    /**     * 判斷鏈表是否為空     * @return bool     */    public function isEmpty(): bool {        return $this->size == 0;    }    /**     * 在鏈表的第 index 位置添加元素     * @param int $index     * @param $e     */    public function add(int $index, $e): void {        if ($index < 0 || $index > $this->size) {            echo "索引范圍錯誤";            exit;        }        $prve = $this->dummyHead;        for ($i = 0; $i < $index; $i++) {            $prve = $prve->next;        }        //將上插入位置的上一個位置的 next 節(jié)點指向插入節(jié)點，插入節(jié)點的 next 節(jié)點信息指向原上節(jié)點的 next 節(jié)點        $prve->next = new Node($e, $prve->next);        $this->size++;    }    /**     * 向鏈表開頭添加元素     * @param $e     */    public function addFirst($e): void {        $this->add(0, $e);    }    /**     * 向鏈表末尾添加元素     * @param $e     */    public function addLast($e): void {        $this->add($this->size, $e);    }    /**     * 獲取鏈表第 index 位置元素     * @param $index     */    public function get($index) {        if ($index < 0 || $index > $this->size) {            echo "索引范圍錯誤";            exit;        }        $node = $this->dummyHead;        for ($i = 0; $i < $index + 1; $i++) {            $node = $node->next;        }        return $node->e;    }    /**     * 獲取鏈表第一個元素     * @return mixed     */    public function getFirst() {        return $this->get(0);    }    /**     * 獲取鏈表最后一個元素     * @return mixed     */    public function getLast() {        return $this->get($this->size - 1);    }    /**     * 修改鏈表中第 index 位置元素值     * @param $index     * @param $e     */    public function update($index, $e) {        if ($index < 0 || $index > $this->size) {            echo "索引范圍錯誤";            exit;        }        $node = $this->dummyHead;        for ($i = 0; $i < $index + 1; $i++) {            $node = $node->next;        }        $node->e = $e;    }    /**     * 判斷鏈表中是否存在某個元素     * @param $e     * @return bool     */    public function contains($e): bool {        for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {            if ($node->e == $e) {                return true;            }        }        return true;    }    /**     * 刪除鏈表中第 index 位置元素     * @param $index     */    public function remove($index) {        if ($index < 0 || $index > $this->size) {            echo "索引范圍錯誤";            exit;        }        if ($this->size == 0) {            echo "鏈表已經(jīng)是空";            exit;        }        $prve = $this->dummyHead;        for ($i = 0; $i < $index; $i++) {            $prve = $prve->next;        }        $node = $prve->next;        $prve->next = $node->next;        $this->size--;        return $node->e;    }    /**     * 刪除鏈表頭元素     */    public function removeFirst() {       return $this->remove(0);    }    /**     * 刪除鏈表末尾元素     */    public function removeLast() {       return $this->remove($this->size - 1);    }    /**     * 鏈表元素轉(zhuǎn)化為字符串顯示     * @return string     */    public function toString(): string {        $str = "";        for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {            $str .= $node->e . "->";        }        return $str . "null";    }}class Node{    public $e;//節(jié)點元素    public $next; //下個節(jié)點信息    /**     * 構(gòu)造函數(shù) 設(shè)置節(jié)點信息     * Node constructor.     * @param $e     * @param $next     */    public function __construct($e, $next) {        $this->e = $e;        $this->next = $next;