1
front 2 a1
3 a2
.
a3
rear .
N-1
循环队列（臆造）
N-1
0
1
rear
front a1
2
a3 a2
3
15
新问题：在循环队列中，队空时 front=rear；队满时也 会有 front=rear；判决条件将出现二义性！ 解决方案有二： ①使用一个计数器记录队列中元素个数（即队列长度）； ②人为浪费一个单元，约定：队列头指针在队列尾指针的 下一位置上作为队列呈“满”状态的标志。则队满特征可 改为front=(rear+1)%N （N为最大队列长度）；
（2）删除动作分析： 前面约定指针front指向队首元素的位置，故： e = Q. base [ Q. front ] ; Q. front = ( Q. front + 1 ) % MAXQSIZE;
先取出元素，后 移动队头指针
队列尺寸
25
出队操作完整算法
Status DeQueue ( SqQueue &Q, QElemType &e) {//若队列不空，删除循环队列q的队头元素，
rear; //队尾指针
}SqQueue
建队核心语句：
Q. base=(QElemType *)malloc(sizeof (QElemType ）
* MAXQSIZE); //分配空间
17
队空条件 : front = rear (初始化时：front = rear ) 队满条件： front = (rear+1) % N (N=MAXQSIZE) 队列长度：L=（N＋rear－front）% N
5
三、队列的表示和实现
1.单链队列
// ---Leabharlann -队列的链式存储结构-----结点类型定义：
链队中任一 结点的结构
typedef struct QNode {
QElemType
data; //元素
struct QNode *next; //指向下一结点的指针
} Qnode , * QueuePtr ;
InitStack(temps);
27
while( ! QueueEmpty (Q) ) //初始化temps栈 {
DeQueue (Q, x); Push (temps, x); }
While( ! StackEmpty (temps) ) {
Pop (temps, x); EnQueue (Q, x); } }
12
问题：（1）怎样实现入队和出队操作？核心语句如下：
入队(尾部插入)： Q[rear]=e ; rear++ ; 出队(头部删除)： e=Q[front] ; front++;
（2） 空队列的特征？ 约定：front=rear
（3）队列会满吗？ 极易装满！因为数组通常有长度限制，而其
前端空间无法释放。有假溢出现象。如图：
允许插入的一端为队尾，允许删除的一 端为队头。
例如：队列 Q= (a1 , a2 , a3 , …， an )
队头元素
队尾元素
在队尾插入元素称为入队；
在队首删除元素称为出队。 2
2. 逻辑结构： 与线性表相同，仍为一对一关系。 3. 存储结构：顺序队或链队，以循环顺序队更常见。
4. 运算规则：只能在队首和队尾运算，且访问结点 时依照先进先出（FIFO）的原则。
} ADT Stack
4
基本操作: 建队列、判断队列是否为空、入队、 出队、读队头元素值，等等。
（1）初始化队列 InitQueue(&Q) （2）入队 EnQueue(&Q,e) （3）出队 DeQueue(&Q,&e) （4）获取队头元素内容 GetHead(Q,&e) （5）判断队列是否为空 QueueEmpty(Q)
J2 J1
front=1
J3 J4
J5
J8 J9 J7
J6 J5
rear=4
rear=0 front=5
rear=0
front=5
解：由图可知，队头和队尾指针的初态分别为front=1
和rear=0。
删除4个元素后front=5；
再插入4个元素后，rear=(0+4)%6=4
19
例2. Q[0…10]是一个循环队列，初始状态为 front=rear=0,画出做完下列操作后队列的头尾指针 的状态变化情况，若不能入队，请指出其元素，并说 明理由。 d, e, b, g, h 入队 d, e 出队 i, j, k, l, m 入队 b 出队 n, o, p 入队
11
2. 顺序队列 队列的顺序存储结构如下图所示：
0
1
2
n-2 n-1
a1
a2
a3
...
an-1 an
front
rear
附设两个指针front和rear分别指示队列头元素的位
置和队列尾元素的下一个位置
约定：初始化建空队列时，令front=rear=0；
0
1
2
...
n-2 n-1
front=0
rear=0
算法说明：向循环队列的队尾插入一个元素
分 析： (1) 插入前应当先判断队列是否满？
if (( Q . rear + 1 ) % MAXQSIZE )==Q.front) return ERROR;
(2）插入动作 Q. base [Q. rear] = e; Q. rear = ( Q . rear + 1 ) % MAXQSIZE;
∧
Q.rear
Q. front==Q. rear
7
// -----基本操作的算法描述-----
建队操作——构造空队列Q Status InitQueue (LinkQueue &Q) { // 构造一个空队列
Q.front = Q.rear =
(QueuePtr)malloc(sizeof(QNode));
J2
J3
J1
front
J4 J5
rear
问1：左图中队列 MAXQ6 SIZE N=？
问2：左图中队列长度 L=？ 5
问3： 在具有N个单元的循 环队列中，队满时共有多少 个元素？ N-1个
18
例1. 一循环队列如下图所示，若先删除4个元素，接 着再插入4个元素，请问队头和队尾指针分别指向哪个 位置?
front->next=p->next; free(p);
链队会满吗？ 一般不会，因为删除时有free动作。除
非内存不足！
9
Status EnQueue (LinkQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素
p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); //存储分配失败 p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; }
5. 实现方式 ：关键是掌握入队和出队操作，具体实 现依顺序队或链队的不同而不同。
3
二、队列的抽象数据类型定义
ADT Queue { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n } 约定a1 端为队列头，an 端为队列尾。 基本操作：
10
Status DeQueue (LinkQueue &Q, QElemType &e) {
// 若队列不空，则删除Q的队头元素， //用 e 返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; //一定要考虑 free (p); return OK; }
第三章 栈和队列
3.1 栈（Stack） 3.2 队列 （Queue)
1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式
1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式
1
一、概念：
3.2 队列
1. 定义 只能在表的一端进行插入运算，在表的 另一端进行删除运算的线性表。
if (!Q.front) exit (OVERFLOW);
//存储分配失败
Q.front->next = NULL;
return OK;
}
8
链队列的入队和出队操作
Q front
p
a1
a2
(队首)
rear
a3 ^ S e ^
(队尾)
入队（尾部插入）：rear->next=S; rear=S;
出队（头部删除）：p=front->next;
链队列类型定义：
关于整个链队的 总体描述
typedef struct { QueuePtr front ; QueuePtr rear ;
//队头指针 //队尾指针
} LinkQueue;
6
为了操作方便，添加一个头结点，令头指针指向头结点。
Q.front Q.rear
a1
…
an ∧
空队列 Q.front