|
知识路径: > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用数据结构 > 线性结构 > 栈和队列 > 队列 >
|
相关知识点:3个
|
|
|
|
(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)队列的链式存储。队列的链式存储也称为链队列。为了便于操作,可给链队列添加一个头结点,并令头指针指向头结点,如下图所示。因此,队列为空的判定条件是头指针和尾指针的值相同,且均指向头结点。
|
|
|
|
|