|
|
|
|
知识路径： > 计算机系统基础知识 > 计算机软件知识 > 数据结构与算法知识 > 队列、栈 > 栈和队列 >
|
|
|
被考次数：18次
|
|
|
被考频率：
高频率
|
|
|
总体答错率：
46%
|
|
知识难度系数：
|
|
|
考试要求：
掌握
|
|
|
相关知识点：2个
|
|
|
|
|
|
|
队列是一种先进先出（FIFO）的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾（Rear），允许删除元素的一端称为队头（Front）。
|
|
|
|
|
|
（1）置队空InitQueue(Q)：创建一个空的队列Q。
|
|
|
|
|
|
（3）入队EnQueue(Q,x)：将元素x加入到队列Q的队尾，并更新队尾指针。
|
|
|
|
（4）出队DeQueue(Q)：将队头元素从队列Q中删除，并更新队头指针。
|
|
|
|
（5）读队头元素Frontque(Q)：返回队头元素的值，但并不更新队头指针。
|
|
|
|
|
|
（1）顺序存储。队列的顺序存储结构是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在队列的两端进行，因此设置队头指针和队尾指针，分别指示当前的队首元素和队尾元素。
|
|
|
|
在顺序队列中，为了降低运算的复杂度，元素入队时只需修改队尾指针，元素出队时只需修改队头指针。由于顺序队列的存储空间是提前设定的，所以队尾指针会有一个上限值，当队尾指针达到其上限时，就不能只通过修改队尾指针来实现新元素的入队操作了。此时，可通过整除取余运算将顺序队列假想成一个环状结构，称之为循环队列。在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置是相同的。为了区别队空和队满的情况，可采用两种处理方式：其一是设置一个标志位，以区别头、尾指针的值相同时队列是空还是满；其二是牺牲一个元素空间，约定以"队列的尾指针所指位置的下一个位置是头指针时"表示队列满，头、尾指针的值相同时表示队列空。
|
|
|
|
（2）链式存储。用链表表示的队列简称为链队列。为了便于操作，给链队列添加一个头节点，并令头指针指向头节点。队列为空的判定条件是：头指针和尾指针的值相同，且均指向头节点。
|
|
|
|
|
|
队列结构常用于处理需要排队的场合，如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。
|
|
|
