【栈】后进先出，先进后出，这就是典型的“栈”结构。
任何数据结构都是对特定应用场景的抽象，数组和链表虽然使用起来更加灵活，但却暴露了几乎所有的操作，难免会引发错误操作的风险。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。
栈主要包含两个操作，入栈和出栈。
实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
对于出栈操作来说，我们不会涉及内存的重新申请和数据的搬移，所以出栈的时间复杂度仍然是O(1)。但是，对于入栈操作来说，情况就不一样了。当栈中有空闲空间时，入栈操作的时间复杂度为 O(1)。但当空间不够时，就需要重新申请内存和数据搬移，所以时间复杂度就变成了O(n)。
<?php
class StackOnLinkedList
{
/**
* 头指针
*
* @var SingleLinkedListNode
*/
public $head; /**
* 栈长度
*
* @var
*/
public $length; /**
*
* StackOnLinkedList constructor.
*/
public function __construct()
{
$this->head = new SingleLinkedListNode();
$this->length = ;
} /**
* 出栈
*
* @return bool
*/
public function pop()
{
if ( == $this->length) {
return false;
} $this->head->next = $this->head->next->next;
$this->length--; return true;
} /**
* 入栈
*
* @param $data
*
* @return SingleLinkedListNode|bool
*/
public function push($data)
{
return $this->pushData($data);
} /**
* 入栈 node
*
* @param SingleLinkedListNode $node
*
* @return bool
*/
public function pushNode(SingleLinkedListNode $node)
{
if (null == $node) {
return false;
} $node->next = $this->head->next;
$this->head->next = $node; $this->length++;
return true;
} /**
* 入栈 data
*
* @param $data
*
* @return SingleLinkedListNode|bool
*/
public function pushData($data)
{
$node = new SingleLinkedListNode($data); if (!$this->pushNode($node)) {
return false;
} return $node;
} /**
* 获取栈顶元素
*
* @return SingleLinkedListNode|bool|null
*/
public function top()
{
if ( == $this->length) {
return false;
} return $this->head->next;
} /**
* 打印栈
*/
public function printSelf()
{
if ( == $this->length) {
echo 'empty stack' . PHP_EOL;
return;
} echo 'head.next -> ';
$curNode = $this->head;
while ($curNode->next) {
echo $curNode->next->data . ' -> '; $curNode = $curNode->next;
}
echo 'NULL' . PHP_EOL;
} /**
* 获取栈长度
*
* @return int
*/
public function getLength()
{
return $this->length;
} /**
* 判断栈是否为空
*
* @return bool
*/
public function isEmpty()
{
return $this->length > ? false : true;
}
}
调用示例：
$stack = new StackOnLinkedList();
$stack->pushData();
$stack->pushData();
$stack->pushData();
$stack->pushData();
var_dump($stack->getLength());
$stack->printSelf(); $topNode = $stack->top();
var_dump($topNode->data); $stack->pop();
$stack->printSelf();
$stack->pop();
$stack->printSelf(); var_dump($stack->getLength()); $stack->pop();
$stack->pop();
$stack->printSelf();
运行结果：