特殊的线性表 - 队列

Friday. March 29, 2019 - 4 mins

数据结构与算法系列（六）

介绍完栈之后，接下来我们要介绍的是另一种跟栈很相似的数据结构 —— 队列，和栈一样，队列也是一中特殊的线性表结构，只不过队列是在一端插入，另一端删除，就跟我们平常排队一样的道理，从队尾入队，在队头出去，所以队列的特性是先入先出（FIFO），允许插入的一端叫队尾，允许删除的一端叫队头。一张图可以形象的体现两者的差别：

和栈一样，队列也可以通过数组和链表实现，通过数组实现的叫顺序队列，通过链表实现的叫做链式队列，栈只需要一个栈顶指针就可以了，因为只允许在栈顶插入删除，但是队列需要两个指针，一个指向队头，一个指向队尾。我们先来看通过 PHP 数组实现的顺序队列代码：

<?php
/**
 * 通过 PHP 数组实现的队列
 */
class SimpleQueue
{
    private $_queue = [];
    private $_size = 0;

    public function __construct($size = 10)
    {
        $this->_size = $size;
    }

    // 入队
    public function enqueue($value)
    {
        if (count($this->_queue) > $this->_size) {
            return false;
        }
        array_push($this->_queue, $value);
    }

    // 出队
    public function dequeue()
    {
        if (count($this->_queue) == 0) {
            return false;
        }
        return array_shift($this->_queue);
    }

    public function size()
    {
        return count($this->_queue);
    }
}

$queue = new SimpleQueue(5);
$queue->enqueue(1);
$queue->enqueue(3);
$queue->enqueue(5);
var_dump($queue->dequeue());  # 1
var_dump($queue->size());  # 2

SPL关于队列的实现;

SplQueue extends SplDoublyLinkedList implements Iterator , ArrayAccess , Countable {
    /* 方法 */
    __construct ( void )
    dequeue ( void ) : mixed //取数据
    enqueue ( mixed $value ) : void //存数据

    /** 
     * 设置迭代模式
     * - 迭代的顺序 (先进先出、后进先出)
     *  - SplDoublyLnkedList::IT_MODE_LIFO (堆栈)
     *  - SplDoublyLnkedList::IT_MODE_FIFO (队列)
     *
     * - 迭代过程中迭代器的行为
     *  - SplDoublyLnkedList::IT_MODE_DELETE (删除已迭代的节点元素)
     *  - SplDoublyLnkedList::IT_MODE_KEEP   (保留已迭代的节点元素)
     *
     * 默认的模式是 0 : SplDoublyLnkedList::IT_MODE_FIFO | SplDoublyLnkedList::IT_MODE_KEEP
     *
     * @param $mode 新的迭代模式
     */
    setIteratorMode ( int $mode ) : void  
    /* 继承的方法 */
    public SplDoublyLinkedList::add ( mixed $index , mixed $newval ) : void
    public SplDoublyLinkedList::bottom ( void ) : mixed
    public SplDoublyLinkedList::count ( void ) : int
    public SplDoublyLinkedList::current ( void ) : mixed
    public SplDoublyLinkedList::getIteratorMode ( void ) : int
    public SplDoublyLinkedList::isEmpty ( void ) : bool
    public SplDoublyLinkedList::key ( void ) : mixed
    public SplDoublyLinkedList::next ( void ) : void
    public SplDoublyLinkedList::offsetExists ( mixed $index ) : bool
    public SplDoublyLinkedList::offsetGet ( mixed $index ) : mixed
    public SplDoublyLinkedList::offsetSet ( mixed $index , mixed $newval ) : void
    public SplDoublyLinkedList::offsetUnset ( mixed $index ) : void
    public SplDoublyLinkedList::pop ( void ) : mixed
    public SplDoublyLinkedList::prev ( void ) : void
    public SplDoublyLinkedList::push ( mixed $value ) : void
    public SplDoublyLinkedList::rewind ( void ) : void
    public SplDoublyLinkedList::serialize ( void ) : string
    public SplDoublyLinkedList::setIteratorMode ( int $mode ) : void
    public SplDoublyLinkedList::shift ( void ) : mixed
    public SplDoublyLinkedList::top ( void ) : mixed
    public SplDoublyLinkedList::unserialize ( string $serialized ) : void
    public SplDoublyLinkedList::unshift ( mixed $value ) : void
    public SplDoublyLinkedList::valid ( void ) : bool
}

通过数组实现的顺序队列有一个问题，就是随着队列元素的插入和删除，队尾指针和队头指针不断后移，而导致队尾指针指向末尾无法插入数据，这时候有可能队列头部还是有剩余空间的，如下图所示：

我们当然可以通过数据搬移的方式把所有队列数据往前移，但这会增加额外的时间复杂度，如果频繁操作数据量很大的队列，显然对性能有严重损耗，对此问题的解决方案是循环队列，即把队列头尾连起来：

这样一来就不会出现之前的问题了，此时判断队列是否为空的条件还是tail==head，但是判断队列是否满的条件就变成了 (tail+1) % maxsize == head，maxsize 是数组的长度，浪费一个空间是为了避免混淆判断空队列的条件。当然如果通过链表来实现队列的话，显然没有这类问题，因为链表没有空间限制。

队列的应用也非常广泛，比如我们常见的消息队列就是队列的典型应用场景。

PS

迭代器：类继承PHP的Iterator接口，批量操作。

1. 迭代器模式，在不需要了解内部实现的前提下，遍历一个聚合对象的内部元素。
1. 相比传统的编程模式，迭代器模式可以隐藏遍历元素的所需操作。

接口Iterator

current() 返回当前元素
key() 返回当前元素的键
next() 向前移动到下一个元素
rewind() 返回到迭代器的第一个元素

特殊的线性表 - 队列

数据结构与算法系列（六）

PS

Related Posts