钛节点

数据结构之队列

发表@2018-09-13 09:15:21

更新@2023-01-21 22:47:40

啦啦啦，啦啦啦，这将是线性表系列文章的最后一篇了，就是队列。flag也先立了，队列也是线性表，一种有着特殊表现的线性表。

其实很多时候，现实生活中案例就是活脱脱的队列应用案例。你们去过周一到周五早上八点左右的天通苑地铁站或者周一到周五的西二旗地铁站吗？![](https://ti-node.com/static/upload/6345443000872599553)![](https://ti-node.com/static/upload/6345443000872599553)![](https://ti-node.com/static/upload/6345443000872599553)

一般情况下，不出意外应该都是这样的：

![](https://ti-node.com/static/upload/6402051506186485761)

如果你有无人机的，空中航拍一下，俯瞰效果大概可能会类似于下图：

![](https://ti-node.com/static/upload/6402053156548640768)

如果你要添加节点，那就只能往队列的尾巴上添加新节点。如果你要删除节点，那就只能从队列的头部删除节点。这种特性，我们用先进先出（FIFO, First-In-First-Out）来形容，而上节的栈实际上是后进先出（LIFO，Last-In-First-Out）。

多说一句，为啥地铁站要这么干？实际上就是为了限流。这和大家嘴中常说的利用消息队列限流保证服务不会冲跨就是一个道理。

由于队列本质上也是线性表，所以我们依然拿单链表的代码进行修改，摇身一变变成队列：
```php
    <?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 : shift
       */
      public function shift(){
        $length = $this->get_length();
        return $this->delete_item( 0 );
      }
      /*
       * @desc : push
       */
      public function push( $item ){
        $length = $this->get_length();
        return $this->add_item( $length, $item );
      }
    }
    $link = new Linked_sq();
    echo 'length : '.$link->get_length().PHP_EOL;
    // 添加一个结点
    $link->push( 9 );
    echo 'length : '.$link->get_length().PHP_EOL;
    $link->push( 12 );
    $link->push( 3 );
    $link->push( 5 );
    echo 'length : '.$link->get_length().PHP_EOL;
    // 获取第2个位置上的数字
    echo "index 2 : ".$link->get_item_by_index( 2 ).PHP_EOL;
    // 删除第1个位置上的数字
    echo $link->shift().PHP_EOL;
    echo 'length : '.$link->get_length().PHP_EOL;
    echo "index 2 : ".$link->get_item_by_index( 2 ).PHP_EOL;
```

线性表这里的基础章节就到这里结束啦，后面的文章有两个可能：
- 线性表的一些实际用例
- 开始二叉树相关内容

---