|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用数据结构 > 线性结构 > 栈和队列 >
|
被考次数：3次
被考频率：中频率
总体答错率：46%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
相关知识点：5个
|
|
|
|
|
|
|
队列是一种先进先出（FIFO）的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾（rear），允许删除元素的一端称为队头（front）。
|
|
|
|
|
|
①初始化队列initQueue（Q）：创建一个空的队列Q。
|
|
|
|
②判队空isEmpty（Q）：当队列为空时返回“真”值，否则返回“假”值。
|
|
|
|
③入队enQueue（Q，x）：将元素x加入到队列Q的队尾，并更新队尾指针。
|
|
|
|
④出队deQueue（Q）：将队头元素从队列Q中删除，并更新队头指针。
|
|
|
|
⑤读队头元素frontQueUe（Q）：返回队头元素的值，但不更新队头指针。
|
|
|
|
|
|
（1）队列的顺序存储。队列的顺序存储结构又称为顺序队列，它也是利用一组地址连续的存储单元存放队列中的元素。由于队中元素的插入和删除限定在表的两端进行，因此设置队头指针和队尾指针，分别指示出当前的队首元素和队尾元素。
|
|
|
|
设顺序队列Q的容量为6，其队头指针为front，队尾指针为rear，头、尾指针和队列中元素之间的关系如下图所示。
|
|
|
|
|
|
|
|
在顺序队列中，为了简化运算，元素入队时，只修改队尾指针；元素出队时，只修改队头指针。由于顺序队列的存储空间是提前设定的，因此队尾指针会有一个上限值，当队尾指针达到其上限时，就不能只通过修改队尾指针来实现新元素的入队操作了。此时，可将顺序队列假想成一个环状结构，如下图所示，称之为循环队列。
|
|
|
|
|
|
|
|
设循环队列Q的容量为MAXSIZE，初始时队列为空，且Q.rear和Q.front都等于0，如下图（a）所示。元素入队时修改队尾指针，即令Q.rear=（Q.rear+1）% MAXSIZE，如下图（b）所示。元素出队时修改队头指针，即令Q.front=（Q.front+1）% MAXSIZE，如下图（c）所示。
|
|
|
|
|
|
|
|
根据出队列操作的定义，当出队操作导致队列变为空时，有Q.rear==Q.front，如上图（d）所示；若队列满，则Q.rear==Q.front，如上图（e）所示。在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置是相同的，此时仅仅根据Q.rear和Q.front之间的关系无法断定队列的状态。为了区分队空和队满的情况，可采用两种处理方式：其一是设置一个标志位，以区别头、尾指针的值相同时队列是空还是满；其二是牺牲一个元素空间，约定以“队列的尾指针所指位置的下一个位置是头指针”表示队列满，如上图（f）所示，而头、尾指针的值相同时表示队列为空。
|
|
|
|
设队列中的元素类型为整型，则循环队列的类型定义为：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
（2）队列的链式存储。队列的链式存储也称为链队列。为了便于操作，可给链队列添加一个头结点，并令头指针指向头结点，如下图所示。因此，队列为空的判定条件是头指针和尾指针的值相同，且均指向头结点。
|
|
|
|
|
|
|
|
|
|
队列常用于处理需要排队的场合，如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。
|
|
|
