[科普中国]-队列元素

简介

队列元素是指队列中的数据元素。在计算机中，队列是经常被使用的数据结构之一，不同的应用中，队列元素的类型也是各不相同。对队列元素进行有关操作，首先要符合队列的有关操作要求。为了方便对队列元素进行管理，在有关程序和应用中，一般都设置了队列元素的最大长度。同时防止队列元素溢出，系统中都设置了缓冲管理。

缓冲区在计算机系统中，缓冲区是指多个以不同速度或优先级运行的硬件或程序进程共享的数据区，缓冲区的存在使它们之间的相互等待变少了，提高了系统的运行效率。先结束的可以把结果放入缓冲区内，进行下面的工 作；而后干完的可以从缓冲区内取出原来的数据继续工作；不用像原来那样，先干完的必须等待后干完的，这样的等待在计算机内是十分耗时的。为了使这种相互等待变得比较少，对缓冲区大小的处理及缓冲算法一定要十分小心地选择。缓 冲区的作用是：(1)在高速和低速设备之间起一个速度平滑作用；(2)暂时存储数据；(3)经常访问的 数据可以放进缓冲区，减少对慢速设备的访问，以提高效率。缓冲区溢出（buffer overflow），是针对程序设计缺陷，向程序输入缓冲区写入使之溢出的内容（通常是超过缓冲区能保存的最大数据量的数据），从而破坏程序运行、趁中断之并获取程序乃至系统的控制权。缓冲区溢出原指当某个数据超过了处理程序限制的范围时，程序出现的异常操作。造成此现象的原因有：存在缺陷的程序设计。例如C语言，不像其他一些高级语言会自动进行数组或者指针的边界检查，增加溢出风险，另外C语言中的C标准库还具有一些非常危险的操作函数，使用不当也为溢出创造条件。

队列元素操作有关函数add( );

增加一个元素，如果队列已满，则抛出一个异常。

remove( );

移除并返回队列头部的元素，如果队列为空，则抛出一个异常。

element( );

返回队列头部的元素，如果队列为空，则抛出一个异常。

offer( );

添加一个元素并返回true ，如果队列已满，则返回false。

poll( );

移除并返问队列头部的元素，如果队列为空，则返回null。

peek( ) ;

返回队列头部的元素，如果队列为空，则返回null。

put( );

添加一个元素，如果队列满，则阻塞。

get( ) ;

移除并返回队列头部的元素，如果队列为空，则阻塞。

队列实现方式顺序队列顺序队列的定义

采用顺序存储结构的队列称为顺序队列，顺序队列实际上是运算受限的顺序表。

顺序队列的表示

①和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。

②由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。

顺序队列中的溢出现象

① "下溢"现象

当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。

② "真上溢"现象

当队列满时，做入队运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。

③ "假上溢"现象

由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

链队列在队列的形成过程中，可以利用线性链表的原理，来生成一个队列。

基于链表的队列，要动态创建和删除节点，效率较低，但是可以动态增长。

队列采用的FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。

循环队列在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。

在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=(rear+1)%MaxSize。