【PHP 实现数据结构】栈

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

什么是栈

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

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

代码实现

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

• 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;