数据结构:理解循环队列

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

 1let loopQuene = new Array(5)    // 创建一个长度为 5 的循环队列。
 2let front = 0, rear = 0         // 初始化两个指针,记录头位置和尾+1位置。
 3/*
 4现在的样子:
 5[null, null, null, null, null]
 6 ^f,r
 7*/
 8
 9loopQuene[rear] = 1 //排队入队
10rear++;
11/*
12现在的样子:
13[1, null, null, null, null]
14 ^f  ^r
15*/
16
17loopQuene[rear] = 4 //排队入队
18rear++;
19/*
20现在的样子:
21[1, 4, null, null, null]
22 ^f     ^r
23*/
24
25loopQuene[front] = null //1 出队
26front++;
27/*
28现在的样子:
29[null, 4, null, null, null]
30       ^f  ^r
31*/

如果元素太多呢?

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

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

 1/*
 2现在的样子:
 3[1   , 1, 2, 3, 5]
 4 ^f^r
 5*/
 6// 出队
 7loopQuene[front] = null;
 8front++;
 9/*
10现在的样子:
11[null   , 1, 2, 3, 5]
12 ^r      ^f
13
14// 出队
15loopQuene[front] = null;
16front++;
17/*
18现在的样子:
19[null   , null, 2, 3, 5]
20 ^r             ^f
21*/
22
23// 入队
24loopQuene[rear] = 8;
25rear += (rear + 1) % loopQuene.length;
26/*
27现在的样子:
28[8   , null, 2, 3, 5]
29 ^r             ^f
30*/

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

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

标识法:

 1const delete = 0;
 2const append = 1;
 3let lastOperation = delete;
 4
 5if( front == rear && lastOperation == delete){
 6    alert("队空了!")
 7}
 8
 9if( front == rear && lastOperation == append){
10    alert("队满了!")
11}

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

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

 1/*
 2现在的样子:
 3[1, 1, 2, 3, <null>, null]
 4 ^f          ^r
 5*/
 6//排队入队
 7loopQuene[rear] = 5
 8rear = (rear + 1) % loopQuene.length
 9/*
10现在的样子:
11[1, 1, 2, 3, 5, <null>]
12 ^f              ^r
13此时队满,可见队满条件是 front == (rear + 1) % loopQuene.length
14*/
15/**
16出队:
17[ <null>, 1, 2, 3, 5, null]
18入队:
19[ <null>, 1, 2, 3, 5, 8]
20用起来没毛病!
21 */

最近发布

要查看全部文章,请点击右上角“归档”,下面是最近发布的几篇日志