不按照常理出牌，从理论上讲，单链表后面还有双向链表以及循环链表，但我就不按照常规来，今儿直接搞栈。

栈又叫做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两个方法包装了一下。

单纯看栈的用法大致就这点儿东西，下一篇章结合点儿栈的实际用例。