详解php中的队列

今天，我们就来学习另外一个也是非常经典的逻辑结构类型：队列。相信不少同学已经使用过 redis 、 rabbitmq 之类的缓存队列工具。其实，数据库、程序代码，这些都可以实现队列的操作，就和栈一样，队列也是有其特定的规则，只要符合这个规则，它就叫做队列。

什么是队列？

相对于栈来说，队列是一种先进先出（FIFO）的顺序逻辑结构。什么叫先进先出呢？就和我们的排队一样，当我们去银行或者医院的时候，总是要在门口取一个号，这个号是按顺序叫的。先来的人就可以先办业务或者看病，这就是一个典型的队列。同理，日常的排队就是一个标准的队列模式。如果有插队的，在有正当理由的情况下，我们可以认为它的优先级更高，这是队列中元素的一种特殊形式。就像我们会在等地铁或者公交的时候让孕妇优先，在排队买火车票的时候也有军人的优先窗口。不过，这个并不在我们这次的讨论范围之内。

在公交站排队时，排第一个的当然可以第一个上车，然后依次。这时，你来到了公交站，那么你只能排到最后一位。这个就是队列的具体表现形式。

同样，和栈一样，也有一些名词我们需要了解。当你来到公交站并排到最后一位时，这个操作叫作“入队”。当公交车进站后，第一位乘客上车，这个操作叫做“出队”。第一位乘客所处的位置叫做“队头”，你做为当前队列的最后一位乘客，你的位置就叫做“队尾”。回到代码逻辑上面来看，也就是说队列是从“队尾”“入队”，从“队头”“出队”。

顺序队列

OK，我们还是直接从来代码来看，首先看到的依然是顺序队的实现。

class SqQueue{
    public $data;
    public $front;
    public $rear;
}

既然是顺序队，我们依然还是用一个数组 data 来表示队内的元素。然后定义两个指针 front 和 rear 来表来源gao*daima.com搞@代#码网示队头和队尾。因为是顺序队，所以这里的指针其实也就是保存的是数组的下标。接下来的操作其实就非常的简单了，“入队”时 rear++ ，“出队”时 front++ 。

function InitSqQueue(){
    $queue = new SqQueue();
    $queue->data = [];
    $queue->front = 0;
    $queue->rear = 0;
    return $queue;
}

function EnSqQueue(SqQueue &$queue, $e){
    $queue->data[$queue->rear] = $e;
    $queue->rear ++;
}

function DeSqQueue(SqQueue &$queue){
    // 队列为空
    if($queue->front == $queue->rear){
        return false;
    }
    $e = $queue->data[$queue->front];
    $queue->front++;
    return $e;
}

$q = InitSqQueue();
EnSqQueue($q, 'A');
EnSqQueue($q, 'B');
print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//         )

//     [front] => 0
//     [rear] => 2
// )

是不是感觉学过了栈之后，队列也很好理解了。初始化队列时，就是让队头和队尾指针都是 0 下标的记录就可以了。入队的时候让队尾增加，在这段代码中，我们入队了两个元素，打印出来的顺序队列内容就如注释所示。

EnSqQueue($q, 'C');
EnSqQueue($q, 'D');
EnSqQueue($q, 'E');
print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//             [2] => C
//             [3] => D
//             [4] => E
//         )

//     [front] => 0
//     [rear] => 5
// )

echo DeSqQueue($q), PHP_EOL; // A
echo DeSqQueue($q), PHP_EOL; // B
echo DeSqQueue($q), PHP_EOL; // C
echo DeSqQueue($q), PHP_EOL; // D
echo DeSqQueue($q), PHP_EOL; // E

echo DeSqQueue($q), PHP_EOL; // 

print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//             [2] => C
//             [3] => D
//             [4] => E 
//         )

//     [front] => 5
//     [rear] => 5
// )

喜欢 (0)赏

[搞代码]

分享 (0)