札记之PHP栈的实现

定义：栈是一个有序线性链表，只能在表的一端（称为栈顶，top）执行插入和删除。

特征

• 入栈（push): 在栈中插入一个元素。
• 出栈（pop): 从栈中删除一个元素。
• 下溢（underflow): 对一个空栈执行出栈操作。
• 溢出（overflow): 对一个满栈执行入栈操作。

图示

实现方式

用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈;

支持动态扩容的顺序栈

interface StackInterface
{
    public function push(string $item);
    public function pop();
    public function top();
    public function isEmpty();
}

class ArrStack implements StackInterface
{
    private $stack;
    private $limit;
    public function __construct(int $limit = 20)
    {
        $this->limit = $limit;
        $this->stack = [];
    }

    public function __get($val)
    {
        return $this->$val;
    }

    public function push(string $data = null)
    {
        if (count($this->stack) < $this->limit) {
            array_push($this->stack, $data);
        } else {
            throw new \OverflowException('stack is overflow');
        }
    }

    public function pop()
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('stack is empty');
        } else {
            return array_pop($this->stack);
        }
    }

    public function isEmpty()
    {
        return empty($this->stack);
    }

    public function top()
    {
        return end($this->stack);
    }
}

$stack = new ArrStack(5);
$stack->push(1);
$stack->push(2);
$stack->push(3);
$stack->push(4);
$stack->push(5);
print_r($stack->top());
$stack->pop();
print_r($stack->top());

结果：

54

基于链表的实现方法[链式栈]

通过在链表的表头插入元素的方式实现push操作，删除链表的表头结点（栈顶结点）实现pop操作

require 'linkedList.php';
interface StackInterface
{
    public function push(string $item);
    public function pop();
    public function top();
    public function isEmpty();
}

class LinkedListStack implements StackInterface
{
    private $stack;
    private $limit;
    public function __construct(int $limit)
    {
        $this->limit = $limit;
        $this->stack = new LinkedList();
    }
    public function top()
    {
        return $this->stack->getNthNode($this->stack->getSize() - 1)->data;
    }
    public function isEmpty()
    {
        return $this->stack->getSize() === 0;
    }
    public function pop()
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('stack is empty');
        } else {
            $lastItem = $this->top();
            $this->stack->deleteLast();
            return $lastItem;
        }
    }
    public function push(string $item)
    {
        if ($this->stack->getSize() < $this->limit) {
            $this->stack->insert($item);
        } else {
            throw new \OverflowException('stack is overflow');
        }
    }
}

$listStack = new LinkedListStack(3);
$listStack->push(1);
$listStack->push(2);
$listStack->top();