不按照常理出牌，从理论上讲，单链表后面还有双向链表以及循环链表，但我就不按照常规来，今儿直接搞栈。
栈又叫做stack，栈也是线性表，只不过这种线性表比较特殊而已，和普通线性表唯一不一样的地方就是：如果你要删除或者添加结点，只能在线性表的尾部进行操作：
- 你要添加一个新的结点，就只能往线性表最后添加，这个操作术语叫做 入栈，英文叫做push
- 你要删除一个老的结点，也只能删除线性表最后一个结点，这个操作术语叫做 出栈，英文叫做pop
我知道，肯定又有人要出馊主意了，因为pop和push另他们联想到了两个php函数：array_push和array_pop。弄一个php数组，然后用这两个函数在数组最后一个元素上一顿操作猛如虎，栈不就这点儿东西么？php数组是可以用来模拟栈的，而且配合上array_push和array_pop确实可以完美实现对栈的操作。
成也php数组，败也php数组。多少人因为php array的强大，一辈子窝在了php array中。
选择了array模式的童鞋，看到这里可以出门左拐了。
困难模式，从这行开始。开局就一个线性表，能掌握多少全靠亲自码。
前面说了，栈就是线性表而已，一般说来，线性表的第一个元素可以称为栈底，线性表的最后一个元素成为栈顶。为了方便理解，我建议大家将脑海中“一”字型线性表脑补成“|”字型的，这样竖向的线性表更容易体现出“顶”和“底”的概念。
假设现在有4、5、6三个数字从头到位依次入栈，整个流程如下：
那么，出栈顺序整个流程就如下图：
代码上，相对来说就简单了，因为线性表我们前面已经写过了，我们只需要在原来的基础上添加两个方法pop和push即可（以单链表代码为基础）：
<?php
// 将结点抽象成一个node class，具备data和next两个属性
class Node{
public $data = null;
public $next = null;
public function __construct( $data = null ){
$this->data = $data;
}
}
// 单链表的存储
class Linked_sq{
private $head = null;
public function __construct(){
// 添加一个头结点
$this->head = new Node();
}
/*
* @desc : 获取单链表长度
*/
public function get_length(){
// 注意 头结点 不算在单链表的长度内
$length = 0;
$head = $this->head;
while( $head->next ){
$head = $head->next;
$length++;
}
return $length;
}
/*
* @desc : 添加一个结点
* @param : index
* @param : item
*/
public function add_item( $index, $item ){
$length = $this->get_length();
if( $index < 0 || $index > $length ){
return false;
}
// 获取头结点
$head = $this->head;
for( $i = 0; $i < $index; $i++){
$head = $head->next;
}
// 初始化一个新结点
$node = new Node( $item );
$node->next = $head->next;
$head->next = $node;
return true;
}
/*
* @desc : 删除一个结点
* @param : index
*/
public function delete_item( $index ){
$length = $this->get_length();
if( $index < 0 || $index > $length ){
return null;
}
$head = $this->head;
// 这里循环的终止条件一定要想明白了，我要删除index位置上的结点，从0开始寻找一直到index这个结点，但是
// 当循环终止的时候，被选中的结点是 index - 1 位置上的结点
for( $i = 0; $i < $index; $i++ ){
$head = $head->next;
}
// 这个才是要被删除的结点
$delete_node = $head->next;
$value = $delete_node->data;
// 修改指针指向
$head->next = $head->next->next;
// 删除结点
unset( $delete_node );
return $value;
}
/*
* @desc : 查找某个位置上的数值
* @param : index
*/
public function get_item_by_index( $index ){
$length = $this->get_length();
if( $index < 0 || $index > $length ){
return null;
}
$head = $this->head;
// 注意这里终止条件，这里获取到的是 index-1 位置上的结点
for( $i = 0; $i < $index; $i++ ){
$head = $head->next;
}
return $head->next->data;
}
/*
* @desc : 清空整个单链表
*/
public function truncate(){
// 第一个结点,就是头结点
$head = $this->head;
while( $head->next ){
$temp = $head->next;
unset( $head->next );
$head = $temp;
}
return true;
}
/*
* @desc : 栈的pop方法
*/
public function pop(){
$length = $this->get_length();
return $this->delete_item( $length - 1 );
}
/*
* @desc : 栈的push方法
*/
public function push( $item ){
$length = $this->get_length();
$this->add_item( $length, $item );
}
}
$link = new Linked_sq();
echo '单链表初始长度为：'.$link->get_length().PHP_EOL;
// 添加一个结点
$link->push( 9 );
echo '单链表长度为：'.$link->get_length().PHP_EOL;
$link->push( 1 );
$link->push( 2 );
$link->push( 5 );
echo '单链表长度为：'.$link->get_length().PHP_EOL;
echo '第二个位置上的：'.$link->get_item_by_index( 1 ).PHP_EOL;
$link->pop();
echo '单链表长度为：'.$link->get_length().PHP_EOL;我们在单链表的代码基础上添加了pop和push两个新方法，而且这两个方法本质上也是将原有的add_item和delete_item两个方法包装了一下。