Site Overlay

数据结构笔记:五分钟搞明白循环队列

循环队列:一个数组,和一个头指针、尾指针。(这里的指针不是真的指针,只是记录下标的整数)。现在还不明白没关系,我们看下面的代码:

let loopQuene = new Array(5)    // 创建一个长度为 5 的循环队列。
let front = 0, rear = 0         // 初始化两个指针,记录头位置和尾+1位置。
/*
现在的样子:
[null, null, null, null, null]
 ^f,r
*/

loopQuene[rear] = 1 //排队入队
rear++;
/*
现在的样子:
[1, null, null, null, null]
 ^f  ^r
*/

loopQuene[rear] = 4 //排队入队
rear++;
/*
现在的样子:
[1, 4, null, null, null]
 ^f     ^r
*/

loopQuene[front] = null //1 出队
front++;
/*
现在的样子:
[null, 4, null, null, null]
       ^f  ^r
*/

如果元素太多呢?

/*
现在的样子:
[1, 1, 2, 3, null]
 ^f          ^r
*/
loopQuene[rear] = 5 //排队入队
rear++;//溢出了
// 所以为了避免溢出,我们这样:
rear = (rear + 1) % loopQuene.length
/*
现在的样子:
[1   , 1, 2, 3, 5]
 ^f^r
*/

为啥是循环队列呢?继续出队

/*
现在的样子:
[1   , 1, 2, 3, 5]
 ^f^r
*/
// 出队
loopQuene[front] = null;
front++;
/*
现在的样子:
[null   , 1, 2, 3, 5]
 ^r      ^f

// 出队
loopQuene[front] = null;
front++;
/*
现在的样子:
[null   , null, 2, 3, 5]
 ^r             ^f
*/

// 入队
loopQuene[rear] = 8;
rear += (rear + 1) % loopQuene.length;
/*
现在的样子:
[8   , null, 2, 3, 5]
 ^r             ^f
*/

看,就像首尾相连起来了。这样的好处(相对于不循环的直接数组模拟的队列)是不用在出队的时候批量移动元素。

另外发现,队满和队空时都会有 front == rear 成立。为了避免无法判断是空是满,解决方法如下:

标识法:

const delete = 0;
const append = 1;
let lastOperation = delete;

if( front == rear && lastOperation == delete){
    alert("队空了!")
}

if( front == rear && lastOperation == append){
    alert("队满了!")
}

计数法:添加一个变量 queneLength 记录队列中元素数量,每当入队时 queneLength++,出队时 queneLength--

空闲单元法:说白了就是队尾一直维持一个空元素,这样需要在初始化队列的时候提前增加一个空间。

/*
现在的样子:
[1, 1, 2, 3, <null>, null]
 ^f          ^r
*/
//排队入队
loopQuene[rear] = 5
rear = (rear + 1) % loopQuene.length
/*
现在的样子:
[1, 1, 2, 3, 5, <null>]
 ^f              ^r
此时队满,可见队满条件是 front == (rear + 1) % loopQuene.length
*/
/**
出队:
[ <null>, 1, 2, 3, 5, null]
入队:
[ <null>, 1, 2, 3, 5, 8]
用起来没毛病!
 */

发表评论

电子邮件地址不会被公开。 必填项已用*标注