札记之链表实现队列

链表实现队列，重要在于出队，详情如下：

思路

初始化：创建一个指向队列节点的head头指针
入队：创建一个新节点，将它添加到链表尾部，如果链表为空，让头指针指向该节点
出队：头指针指向第一个节点，让头指针指向该节点的下一个节点，然后返回该节点的值

图示

札记之链表实现队列

代码实现

class ListNode
{
    private $data;
    private $next;
    public function __construct(string $data = NULL)
    {
        $this->data = $data;
    }
    public function __get($var)
    {
        return $this->$var;
    }
    public function __set($var, $val)
    {
        return $this->$var = $val;
    }
}

class linkedQueue
{
    private $head;
    private $tail;
    private $lenght;

    public function __construct()
    {
        $this->head = new ListNode();
        $this->tail = $this->head;
        $this->length = 0;
    }

    public function enqueue($data)
    {
        $newNode = new ListNode();
        $newNode->data = $data;
        $this->tail->next = $newNode;
        $this->tail = $newNode;
        $this->length++;
    }

    public function dequeue()
    {
        if ($this->length <= 0) {
            return false;
        }
        $node = $this->head->next;
        $this->head->next = $this->head->next->next;
        $this->length--;
        return $node;
    }

    public function getLenght()
    {
        return $this->length;
    }
   
    public function display()
    {
        echo 'LinkList length: ' . $this->length . PHP_EOL;
        $currentNode = $this->head;
        while ($currentNode !== NULL) {
            echo $currentNode->data . PHP_EOL;
            $currentNode = $currentNode->next;
        }
    }
}
$queue = new linkedQueue();
$queue->enqueue(1111);
$queue->enqueue(2222);
$queue->enqueue(3333);
print_r($queue->dequeue()->data);
echo PHP_EOL;
print_r($queue->dequeue()->data);
echo PHP_EOL;
print_r($queue->dequeue()->data);

结果：

1
2
3

1111
2222
3333