数据结构 --静态队列讲解

骑猪看日落 2022-03-12 03:56 164阅读 0赞

上次我在

http://blog.csdn.net/nvd11/article/details/8805772

已经解释了链式队列的大概结构和c语言代码实现.

也提到了另一种队列: 静态队列.  其实相对于链式队列来讲. 其实静态队列更加复杂.

## 1. 什么是静态队列. ##

这个不难理解, **所谓静态队列就是以数组为内核的一种队列结构.**

至于什么是队列可以参考上面的文章.

而所谓数组就是内存里的一块连续内存, 也就是说数组相邻的元素在内存里的地址也是相邻的.

只需要知道数组的头部地址, 就可以快速的访问到制定元素的值. 而不需要像链表那样根据指针1个1个遍历.

所以静态队列的处理速度理论上是比链式队列快的.

而相对于数组, 链表的优势是方便地在线性存储中增加和删除元素, 而队列本身恰恰是不允许这样做的. 只能在入口入列, 出口出列. 所以链表的优势不明显了.

当然, 静态队列还有1个数组的缺点, 就是长度有限制啊. (不重新分配内存的情况下)

## 2. 静态队列的大概结构 ##

### 2.1 1个数组内核    ###

我们来举个简单的例子:

假如我们在内存里通态划分1个长度为8的数组, 也就是最多只能有8个元素啦.

而这个数组的头部地址是P,   那么就可以用P\[0\] ~ p\[7\] 来表表示这个数组的8个元素了.  0 ~ 7是数组的下标.

我定义这个数组后, 将里面的各个元素初始化为'0',  那么我们认为这个数组是逻辑上是1个空数组. 还没有放入数据嘛..

如下图:

![444127020140512215953079.png][]

### 2.2 pFront 指针和 pRear 指针 ###

假如我这时往这个数组写入3个元素 p\[0\] = 'a' , p\[1\] = 'b', p\[2\] ='c'

那么数组中还有5个元素是空的(或者存放垃圾数据)

如下图:

![444127020140512223201046.png][]

假如我想表示由 这个3个元素组成的1个队列, 该如何实现呢.

实际上类似于链式队列, 我们也可以利用 两个指针  pFront 和 pRear 来存放队列的 **出口元素地址**和**入口地址**.

出口元素地址:

就是下一次出列元素的地址,  也就是队列前端第1个元素的地址.如上图中的元素P\[0\]的地址啊,  pFront 会指向它.

入口地址:

通常入口地址不是指队列中尾部元素的地址,  而是尾部元素地址的下1个地址,  就是上图的p\[3\]啊.  也就是下1个入列的元素的地址啊

如下图:

![444127020140512224436084.png][]

那么就可以清楚地表示由 p\[0\] ~ p\[1\] 组成的1个队列了.

## 3. 静态队列的入列操作 ##

继续用上面的例子, 加入我想往队列P增加1个元素'd', 就是入列操作了. 该如何现实.

上面提到了, 我们会用pRear指针指向队列的入口,  那么只要把 'd' 写入 pRear指向的位置, 就是p\[3\]啊,

然后, pRear 必须指向 队列的新的入口地址, 就是p\[4\]啊, 相当与pRear 往 内存高位移动1个位置啊.

然后这时队列就有4个元素了, 相当于队列长度加1啊

如下图:

![444127020140512224824020.png][]

## 4. 静态队列的出列操作 ##

假如我要将这个队列执行出列操作, 那么出列元素肯定是pFront指针指向的元素, 就是上图的p\[0\]啊.

出列操作相对更简单,  pFront指向下1个出列元素地址p\[1\], 那么p\[0\] 就相当于不存在与这个队列中了.

如下图:

![444127020140512230102019.png][]

出列后, pFront 指向p\[1\] .  队列元素个数减1.

## 5. 无论入列或出列, pFront 和 pRear指针都向内存的高位移动. ##

见到上的情况, 无论入列或出列, pFront 或 pRear指针都向内存的高位(图右边)移动一位.

那么随着队列不断出列和入列, 队列左边的内存空间就貌似不能再被使用了.

而数组的长度是有限的.(除非重新动态分配内存)

当出口位置到达数组的最后1个位置会发生神马情况?

对于上面的例子, 假如我再入列3个元素, e, f , g 那么队列中就有6个元素了,  而且入口元素指向p\[7\].

如下图:

![444127020140512230926049.png][]

实际上, p\[7\]这个位置并不属入队列, 但是它仍然在数组的范围内, 所以p\[7\]的空间是可以被使用的, 当执行下次入列操作时, 入列元素就会放在p\[7\]

## 6. 静态队列必须是循环队列. ##

接上面的例子, 加入我再入列1个元素h, h就肯定放入p\[7\] 这个位置了, 那么pRear 指向哪?

如果继续向右移动以为, 则pRear 就指向p\[8\]了.  其实pRear 指向内存的任何位置都是合法的.

但是p\[8\] 并不属于这个数组的内存范围啊, 很可能是其他对象甚至是其他程序进程的内存.

而pRear指向的下1个元素的入口,  再执行1次入列操作时, 元素会被放入p\[8\],  这就是非法操作了, 所谓的内存溢出啊! 就是指非法修改了范围之外的内存!

所以pRear不能指向p\[7\]的 右边1个位置p\[8\], 那么应该指向哪里呢?

上面提过狠多次了, pRear应该指向下1个元素的入口, 也就是下1个入列元素应该放的位置, 假如我入列了h, 那么数组内还有什么地方可以放新入列的元素?

其实分析得出, 当入列了h后 p\[1\] ~ p\[7\]都放了对列的元素, 个数是7个,  而数组的长度是8个. 还有1个在哪? 就是在被出列的p\[0\]啊, 有人说p\[0\]放着元素'a', 的确, 但是p\[0\]已经出列,  这个位置的值是允许被改写的.

所以pRear应该指向p\[0\], 如下图:

![444127020140512232836012.png][]

同理, 假如当前的出口元素是在p\[7\]时,  pFront就指向p\[7\], 那么出列后, pFront会指向下1个出口元素, 下1个出口元素在哪, 是p\[0\]啊!

假如当前pRear 指向的数组下标是 i, 那么入列后,  pRear指向的下标就是

**(i+1) % 数组长度                        这个就是求指针下1个位置的公式了**

pFront同理哦

所以实际上, 当pRear 或 pFront, 指向数组的最后1个位置时, 他们的下个位置就在数组的第1个位置, 那么pRear 和 pFront实际上就在数组内单方向循环移动了, 这样数组内的位置也可以被循环使用!

所以这就是所谓的循环队列了, 作为1个静态队列,  它也必须是循环队列啊.

## 7.确定1个 静态队列(静态队列) 所需的参数 ##

其实参考上的例子, 我们确定1个数组内的队列需要什么参数呢?

对于链式队列来讲, 只需要知道头节点和 尾节点就ok了. 其他参数都可以通过遍历来推算出来了.

但是对于静态队列来讲:  
1. 必须确定静态队列的内核数组

2. pFront 和  pRear 指针

具体来讲就是下列4个元素:

1. 数组的头部地址.

2.数组的长度

3. pFront指针(实际上只需要存放数组的下标)

4. pRear指针(实际上只需要存放数组的下标)

## 8. 如何初始化1个静态队列. ##

具体点讲, 就是初始化1个队列时, 需要做什么动作, pFront 和 pRear指针指向哪里.

第一步,  肯定是动态分配1个数组p

而这个数组是1个空数组, 里面的静态队列肯定也是1个空队列.

那么当放入第1个元素时, 这个元素会放在p\[0\], 所以p\[0\]就是这个空队列的入口地址, 所以pRear指向p\[0\]

既然是空队列, 则不存在出口元素,  那么指向哪呢,  实际上也会指向p\[0\],

也就是说初始化1个静态队列后,  pFront 和 pRear 都指向p\[0\]

## 9. 如何判断1个静态队列为空 ##

首先数组的地址和长度应该不会判断不出队列是否为空的.

那么静态队列的参数只剩下两个了,  就是pFront 和 pRear 的位置.

那么如何根据这两个指针的位置来判断静态队列是否为空呢?

让我们先来看看1个静态队列即将为空的状态,  什么是即将为空, 就是当1个队列只剩下1个元素, 而且马上就出列了, 一但出列后就是1个空队列, 那么我们先看看出列前的状态.

用回上面的例子, 假如1个队列只剩下1个元素p\[3\] , 那么这个元素肯定就是出口的元素了.

所以pFront会指向p\[3\],   那么pRear 就指向p\[3\]后面的下1个地址,

根据公式 (3+1)% 数组的长度   就是p\[4\]啊.  所以当前情况下 pRear 会指向pFront的后1个位置.

如下图:

![444127020140512233027093.png][]

那么出列后, p\[3\]就 不存在于队列中,

而按照上面的公式,    队列下1个位置 =   (i+1)% 数组的长度,  恰恰就是pRear 的位置啊, 如下图:

![444127020140512234823060.png][]

那么当前 pFront 和 pRear 就指向同1个位置p\[4\]

根据上面pFront 和 pRear的定义.

pRear 是指向下1个入列元素的位置,  所以再入列后, 下1个元素就出现在p\[4\], 这时队列又有1个元素了.  而这时pRear会指向p\[4\]的下1个位置p\[5\].

而pFront就仍然指向p\[4\], 恰好就是队列唯一元素的地址, 是符合逻辑的.

**所以综上所述,  当pFront 和 pRear指向同1个位置时, 我们就认为当前静态队列是1个空的队列.**

## 10. 如何判断1个静态队列已满 ##

这个就有点特别了,   继续上面的例子.

上面的数组P 有8个位置, 那么理论上队列是不可能有9个元素的.

假设 队列里有8个元素, 就占满整个数组了.     那么我们来看下当数组里有7个元素时的状态.

假如  pFront 指在p\[4\] 那么, p\[4\]就是队列中前端第1个元素, 也是下1个出列元素, 接下来的6个元素,  按照出列(或入列)循序就是 p\[5\], p\[6\], p\[7\], p\[0\],p\[1\],p\[2\].               只有p\[3\]是不属于队列中的,  而pRear会指向队列最后1个元素p\[2\] 的下1个元素位置, 就是p\[3\]啊.

如下图:

![444127020140512234951053.png][]

而这时 pFront的位置 是 pRear的后1个位置,         也就说 (

(pRear的下标 + 1) % 数组的长度 == pFront的下标.

加入我们占用数组最后1个位置,  把元素'i' 入列, 那么这个元素就会放在 pRear的位置 p\[3\].

而pRear就根据公式移动下1个位置,  就是上面pFront的位置p4啊.

如下图

![444127020140512235519025.png][]

这时, pRear,  pFront 就指向同1个位置了,   但是我们刚刚说过, 当1个队列为空时, 这个两个指针也是指向同1个位置的啊!

所以当pFront 和 pRear指向同1个位置时, 我们就无法判断这个队列究竟是1个空队列还是满的队列了.

除非增加1个参数, 就是当前对列的长度, 每出列或入列后更新1次这个参数.

但是增加1个参数就增加了成本了.

实际上, 更多情况下我们会限制队列的元素个数,

也就是说, **当静态队列中的元素个数 等于  数组的长度 - 1时, 我们就认为这个队列未满了**, 不允许再入列(除非扩容数组). 这样, 就可以避免无法判断的情况.!

对于上面的例子, 当对立有7个元素时, pFront 在 pRear的后1个位置.

**也就说当 (pRear的下标 + 1) % 数组长度 = pFront的下标时, 我們就认为这个队列是满的了**

## 11. 如何获得静态队列的长度, 也就是队列的元素个数 ##

这个,  首先可以肯定的是, 静态队列的长度肯定是由 pFront 的位置,  pRear的位置, 数组的长度这3个参数所决定的.

我们可以将pFront 和 pRear的位置关系分成3种情况:

### 11.1  当pFront 和 pRear 重合, 也就是pRear 的下标  - pFront 的下标 = 0 ###

这种情况下 代表队列长度为0, 上面说过了

### 11.2  当pFront 在pRear 左边, 也就是pRear 的下标  - pFront 的下标 > 0 ###

![444127020140512230926049.png][]

如上图,  长度就是 pRear 的 下标 - pFront 的下标 = 7-1 =6了

### 11.3  当pFront 在pRear右边, 也就是pRear 的下标  - pFront 的下标 <0 ###

如上图:  长度就是 pRear 的下标 - pFront的下标 + 数组长度

就是 3-4 + 8 =7啊

![444127020140512234951053.png][]

在综上所述,   假如 pRear 的下标 - pFrotnt的下标 =x

那么长度 len =  f(x)      x必须在 数组正负绝对值的范围内.

f(int x){
            if (x == 0)
                    return 0;
            if (x > 0)
                    return x;
            if (x < 0)
                    return x + 数组的长度; 
    }

简单点来将

len = (x+ 数组的长度) % 数组的长度

也就是说:

静态队列长度  =    (pRear下标 - pFront下标 + 数组长度) % 数组长度

## 12. 如何扩充队列的元素上限个数 ##

简单点来讲, 就是当1个队列满了后, 假如还有元素要入列, 点算?

因为我们动态分配1个数组时, 必然要指定数组的长度, 系统才会在内存里划一块连续空间给你.

当队列满时,  当然我们可以提示用户不能再入列.

但是实际上我们写的容器通常是不限制长度的(当然内存足够大),  实现的原理就是:

当入列时, 首先判断队列是否已经满,  如果满则执行扩容.

那么如果扩容呢, 需要那些动作?

下面继续用上面的例子讲解,

加入当前数组P 有8个位置,  里面的队列元素有7个, 就是说这个队列已经满了.

如下图:

![444127020140512234951053.png][]

假如这时我想为这个队列扩容4个位置.

实际上的操作就是为这个数组扩充4个位置.

所以这个数组必须是动态分配内存的, 这个是前提

### 步骤1, 为这个数组延长4个位置. ###

通常这个4个位置会在数组接着的后面4个空间, 加入那些空间已经被其他对象使用, 则会在内存另外1个地方找1个足够大(12)的空间, 并把原数据copy过去.

扩容后就是下图状态

![444127020140512235945053.jpg][]

明显看出, 这时的队列状态是不正确的, 因为虽然我么扩充了队列元素个数上限.

但是队列的实际长度不应该改变

然而按照长度计算公式,

上图的中的长度就是   (3-4 + 12) % 12 =11 满了啊, 实际上应该还是7啊

### 步骤2, 调整pFront和相关元素的位置. ###

这个就有点复杂了,

其实我们定1个目标, 就是把pRear 和 pFront的位置调整到正确的位置.

pRear是入口地址, 这个是不需要改变的,

那么要调整的就是pFront的位置了.

那么pFront 要调到哪里呢

目标也很明确,  假设 pFront的下标新下标x  那么   (pRear的下标 - x + 新数组长度)  % 新数组长度 必须等于当前队列长度

假设pFront的旧下标是y

那么:

(pRear的下标 - y +旧数组长度) % 旧数组长度 =  (pRear的下标 - x + 新数组长度)  % 新数组长度

即是

假如当 pRear的下标 -y >=0 时

pRear的下标 - x =pRear的下标 -y                //求长度公式 参考上面

也就是说 x=y, 不用调整啊!

但是上图的情况是  第二种情况:

当 pRear下标 - y <0 时

(pRear的下标 - y +旧数组长度) = (pRear的下标 - x +新数组长度)

x = y + 新数组长度 - 旧数组长度

也就是说

pFront的位置向右移动 被扩容元素的个数啊, 如下图:

![444127020140513000536076.jpg][]

pFront 被移动到去 p\[8\]了

实际上现在状态还是错误的.

还需要把 pFront原来位置的对应元素 及右边的元素, 各自移动4个位置(扩充的数量)

如下图:

![444127020140513000655089.jpg][]

这样就ok了.

上面还提到当 pRear- pFront >=0 时不用pFront的位置调整?

其实这就是pRear 在 pFront右边的情况,

例如扩容前:

![444127020140512230926049.png][]

扩容后:

![444127020140513000903025.jpg][]

看, 不需改变哦

## 13. 一些总结 ##

上面其实粗略讲解了静态数组的一些关键属性和伪算法, 接下来我会在另一篇博文里用c语言实现这个容器.

[444127020140512215953079.png]: http://image16.poco.cn/mypoco/myphoto/20140512/21/444127020140512215953079.png
[444127020140512223201046.png]: http://image16.poco.cn/mypoco/myphoto/20140512/22/444127020140512223201046.png
[444127020140512224436084.png]: http://image16.poco.cn/mypoco/myphoto/20140512/22/444127020140512224436084.png
[444127020140512224824020.png]: http://image16.poco.cn/mypoco/myphoto/20140512/22/444127020140512224824020.png
[444127020140512230102019.png]: http://image16.poco.cn/mypoco/myphoto/20140512/23/444127020140512230102019.png
[444127020140512230926049.png]: http://image16.poco.cn/mypoco/myphoto/20140512/23/444127020140512230926049.png
[444127020140512232836012.png]: http://image16.poco.cn/mypoco/myphoto/20140512/23/444127020140512232836012.png
[444127020140512233027093.png]: http://image16.poco.cn/mypoco/myphoto/20140512/23/444127020140512233027093.png
[444127020140512234823060.png]: http://image16.poco.cn/mypoco/myphoto/20140512/23/444127020140512234823060.png
[444127020140512234951053.png]: http://image16.poco.cn/mypoco/myphoto/20140512/23/444127020140512234951053.png
[444127020140512235519025.png]: http://image16.poco.cn/mypoco/myphoto/20140512/23/444127020140512235519025.png
[444127020140512235945053.jpg]: http://image16.poco.cn/mypoco/myphoto/20140512/23/444127020140512235945053.jpg
[444127020140513000536076.jpg]: http://image16.poco.cn/mypoco/myphoto/20140513/00/444127020140513000536076.jpg
[444127020140513000655089.jpg]: http://image16.poco.cn/mypoco/myphoto/20140513/00/444127020140513000655089.jpg
[444127020140513000903025.jpg]: http://image16.poco.cn/mypoco/myphoto/20140513/00/444127020140513000903025.jpg