呜啦啦的碎碎念


眼中有世界,心中有天地


心有猛虎,细嗅蔷薇

【PHP 实现数据结构】栈

之前介绍过 “队列” 是一种特殊的线性表,这里再介绍另外一种特殊的线性表 “栈”

什么是栈

栈是一种后入先出的数据结构,它只能允许在列表的一端进行操作。允许操作的一端称为栈顶。

栈有两个基本操作,元素压入栈和元素弹出栈,操作示例图。

image.png

代码实现

我们来实现上述两个基本操作,和实际应用中常用的其他几个操作。

  • push 入栈
  • pop 出栈
  • peek 栈顶元素预览
  • length 栈存储的元素个数
  • clear 清空栈
<?php

/**
 * Class Stack
 */
class Stack
{
    protected $top = 0;

    protected $dataStore = [];

    /**
     * 入栈
     * @param $data
     */
    public function push($data)
    {
        $this->dataStore[$this->top++] = $data;
    }

    /**
     * 出栈
     * @return mixed
     */
    public function pop()
    {
        return $this->dataStore[--$this->top];
    }

    /**
     * 预览,查看栈顶元素,但是不弹出
     * @return mixed
     */
    public function peek()
    {
        return $this->dataStore[$this->top - 1];
    }

    /**
     * 栈长度
     * @return int
     */
    public function length() {
        return $this->top;
    }

    /**
     * 清空栈元素
     */
    public function clear() {
        $this->top = 0;
        $this->dataStore = [];
    }
}

示例

$stack = new Stack();
$stack->push(1);
$stack->push(2);
$stack->push(3);
echo "stack length:",$stack->length(),PHP_EOL;
$stack->pop();
$stack->pop();
$stack->push(4);
echo "stack top:",$stack->peek(),PHP_EOL;
$stack->clear();
echo "stack length:",$stack->length(),PHP_EOL;

image.png