《算法4》学习笔记（栈和队列）

背景

在本书开始会讲解Java语言的特性（因为本书的算法代码示例是基于Java代码呈现的），以及数据抽象，背包、栈、队列等基础知识，一切都为了后面真正展开算法讲解做好基础。

本次重新开始看《算法4》，Java编程基础部分和数据抽象部分基本上一目十行草草看过，毕竟老码农了（自恋）；本来打算连背包、栈、队列 部分也粗略跳过，但是突发奇想要不然我用其他语言实现一次？

注：关于什么是背包、栈、队列请自行了解，这里不再介绍。

PHP代码实现

造轮子

程序员的本职就是重复造轮子，所以第一件事就是找找有没有其他人做过类似的实现，一番搜索查找下来目前网上关于PHP实现栈和队列的方式大致分为三类：

利用PHP数组函数 array_push()、array_pop()、array_shift() 等实现。
利用PHP内置函数 SplQueue实现。
通过自建节点用链表结构的方式实现。

前两种对我来说暂时没有意义，所以我选择看第三种实现方式，找到了这篇博文《php实现基本数据结构之栈、队列》，思路不错，但是代码存在Bug，尤其是队列的实现这里完全跑不通 （已经有人在评论里反馈了，然而一年过去了作者没有任何答复），刚好我来修缮Bug以及补全队列实现部分，算是一个小练手。

单向链表和节点

由于实现栈和队列的方式采用单向链表的方式实现，因此先定义一个节点类。

原文中的实现如下：

class Node
{
    private $Data;
    private $Next;

    public function __construct($data, $next)
    {
        $this->Data = $data;
        $this->Next = $next;
    }

    public function __set($name, $value)
    {
        if (isset($this->$name)){
            $this->$name = $value;
        }
    }

    public function __get($name)
    {
        if (isset($this->$name)){
            return $this->$name;
        }else{
            return FALSE;
        }
    }
}

但是这个类存在一些弊端：

采用 __get()、__set() 这样的写法看起来很酷，然而并没有什么必要，反之如果$name错误甚至连个报错都没有，譬如我手误将 $node->Next = $newNode; 写成 $node->next = $newNode;，则什么都不会发生，也不会报错。
在 __get() 中使用 isset($this->$name) 这个判断给后面队列的实现挖了一个巨坑，因为某些Node在实例化的时候$next参数为NULL，从而导致私有类变量$this->Next的值为NULL，因此isset($this->$name)将永远为FALSE，无法设置其值。详见：isset()

所以，我简化了这个类：

class Node
{
    public $Data;
    public $Next;

    public function __construct($data, $next = FALSE)
    {
        $this->Data = $data;
        $this->Next = $next;
    }
}

栈

这里直接贴原文代码，我再解读：


class Stack
{
    private $top = NULL;

    public function isEmpty()
    {
        if ($this->top === NULL)
            return TRUE;
        return FALSE;
    }

    public function push($data)
    {
        $this->top = new Node($data, $this->isEmpty() ? NULL : $this->top);
    }

    public function pop()
    {
        if ($this->isEmpty())
            return NULL;
        $node = $this->top->Next;
        $data = $this->top->Data;
        $this->top = $node;
        return $data;
    }
}

Push 时，如果当前栈为空，那么实例化一个没有next的节点；否则实例化一个新节点，并且该节点的下一个节点指向当前完整链。
Pop 时，如果当前栈为空，直接返回NULL；否则取出当前头节点的数据，并且将当前链设置为头节点的下一个节点，返回取出的数据。

这里注意：栈实现中唯一一个设置节点next的地方是在节点实例化的时候进行的，而不是通过$this->top->Next = xxx; 的方式设置，因此就避开了我之前提到的Node类中isset函数的那个问题。

队列

还是先贴原文代码，我再解读：

class Queue
{
    private $front = NULL;//队头
    private $rear = NULL;//队尾

    public function isEmpty()
    {
        if ($this->front === NULL || $this->rear === NULL)
            return TRUE;
        return FALSE;
    }

    /**
     * 入队
     * @param $data
     */
    public function enQueue($data)
    {
        if ($this->isEmpty())
            $this->front = $this->rear = new Node($data, NULL);
        $this->rear->Next = new Node($data, NULL);
    }

    /**
     * 出队
     * @return null
     */
    public function deQueue()
    {
        if ($this->isEmpty())
            return NULL;
        $node = $this->front->Next;
        $data = $this->front->Data;
        if ($this->front == $this->rear)//当队头跟队尾相同时
            $this->rear = $node;
        $this->front = $node;
        return $data;
    }

}

enQueue 函数是有问题的，重复调用的话，最终结果是$this->front和$this->rear为同一个链，链中永远只有2个节点，即第一个和最后一个数据的节点。

如果我们Node类用原文中那个实现的话，链中更是只有一个节点，因为$this->rear->Next = new Node($data, NULL);这段代码什么都不会发生（详见单向链表和节点部分）。

所以基本上可以确认原文博主没有进行过代码测试就发文了，强烈谴责一下，这也是为什么我特别不喜欢看国人写的博文的原因，一万个坑等着你去踩。要不是这些天我的穿云梯被人拆了还没来得急修，我才不会用中文搜索引擎。

那么，该如何通过链表实现一个队列呢？PHP内置函数 SplQueue描述说是通过双向链表进行实现的，具体源码我没有去看，我还是希望可以通过单向链表的方式来进行实现。

最终实现如下：


class Queue
{
    private $queue = FALSE;
    private $endNode = FALSE;

    public function isEmpty()
    {
        if ($this->queue === FALSE){
            return TRUE;
        }
        return FALSE;
    }

    public function enQueue($data)
    {
        if ($this->isEmpty()){
            $this->queue = new Node($data, FALSE);
            return;
        }

        $newNode = new Node($data, FALSE);

        if ($this->queue->Next === FALSE){
            $this->queue->Next = $newNode;
        }else{
            $this->endNode->Next = $newNode;
        }

        $this->endNode = $newNode;
    }

    public function deQueue()
    {
        if ($this->isEmpty()){
            return FALSE;
        }

        $node = $this->queue->Next;
        $data = $this->queue->Data;

        $this->queue = $node;

        if($this->queue === FALSE){
            $this->endNode = FALSE;
        }

        return $data;
    }
}

其中 queue 为完整的单向链表，保存完整的队列数据；而 endNode 总是指向链表尾部，用以追加新入队的数据到链尾。

enQueue和deQueue函数实现就不多解释了，一目了然。

另一个错误的队列实现

与此同时发现了另外一个博主使用链表实现队列的文章：数据结构与算法之PHP实现队列、栈

代码如下：

<?php
/**
 * php用链表实现队列:先进先出FIFO
    1. isEmpty(): 判断队列是否为空
    2. enqueue(): 入队，在队尾加入数据。
    3. dequeue(): 出队，返回并移除队首数据。队空不可出队。
    4. clear(): 清空队列
    5. show(): 显示队列中的元素
 */
// 节点类
class Node {
    public $data;   // 节点数据
    public $next;   // 下一节点

    public function __construct($data) {
        $this->data = $data;
        $this->next = NULL;
    }
}
// 队列类
class Queue {
    private $header;        // 头节点

    function __construct($data) {
        $this->header = new Node($data);
    }
    // 判断队列是否为空
    public function isEmpty() {
        if ($this->header->next !== null) { // 不为空
            return false;
        }
        return true;
    }
    // 入队，在队尾加入数据。
    public function enqueue($element) {
        $newNode = new Node($element);
        $current = $this->header;
        if ($current->next == null) { // 只有头节点
            $this->header->next = $newNode;
        } else { // 遍历到队尾最后一个元素
            while ($current->next != null) {
                $current = $current->next;
            }
            $current->next = $newNode;
        }
        $newNode->next = null;
    }
    // 出队，返回并移除队首数据。队空不可出队。
    public function dequeue() {
        if ($this->isEmpty()) { // 队列为空
            return false;
        }
        // header头节点没有实际意义，队首节点是header指向的结点。
        $current = $this->header;
        $current->next = $current->next->next;
    }
    // 清空队列
    public function clear() {
        $this->header = null;
    }
    // 显示队列中的元素
    public function show() {
        $current = $this->header;
        if ($this->isEmpty()) {
            echo "空！";
        }
        while ($current->next != null) {
            echo $current->next->data . PHP_EOL;
            $current = $current->next;
        }
    }
}
// 测试
$q = new Queue('header');
$q->enqueue('a');
$q->enqueue('b');
$q->enqueue('c');
echo "队列为：";
$q->show();
echo "</br>";
echo "a出队，队列为：";
$q->dequeue();
$q->show();
echo "</br>";
$q->clear();
echo "清空队列后，队列为";
$q->show();

简直就给我人看傻了，enqueue函数中，当链中有数据时用 while 遍历整个链到最后一个节点（即链尾）…… 简直无力吐槽。

之所以用链表实现队列，就是因为链表的特性：数据大小和操作复杂度无关；他这个实现等于说队列中的数据越多，每次入队时的复杂度和数据长度成正比。

后记

栈、队列、背包（本文没有提及，但是更容易实现）只是作为后面的算法代码的基础构成，本身是很基础的东西，其实发这篇博文的关键原因只有一个：

再次奉劝，想学习前沿知识尽可能不要看国人的文章和博客，也尽可能不要用中文搜索引擎，会踩无穷无尽的坑；虽然不能一棒子打死，但是我真的是在中文博客和文章上踩了几千次坑了，引以为戒吧。