文档介绍：第4章 堆栈和队列---队列的定义
根据定义可见队列特点：
①.它是一个线性表；
②.它的操作是受限的，操作在表的两端进行，一端称为队首，另一端称为队尾；
③.随着入队和出队的进行队首和队尾的位置是要变化的，所以要设置二个指示器（分为称为队首指示器front和队尾指示器rear)，表示队列的变化。
a1
a2
an
•••
front
rear
出队列
进队列
堆栈与队列2
2021/1/15
1
第4章 堆栈和队列---队列的抽象数据类型
队列的抽象数据类型
ADT Queue is
Q: QueueType; //队列数据类型
Operation:
void InitQueue(QueueType& q); //初始化
void EnQueue(QueueType& q, ElemType item); //入队
ElemType OutQueue(QueueType& q); //出队
ElemType PeekQueue(QueueType q); //取队首元素
bool EmptyQueue(QueueType q); //判空
void ClearQueue(QueueType& q); //撤消队列
End Queue
堆栈与队列2
2021/1/15
2
第4章 堆栈和队列---队列的链式表示和实现
队列的链式表示和实现
用不带表头的单链表来表示
①. 结构定义---与单链表的结构定义类似
节点结构的C语言定义
struct LNode {
ElemType data;
struct LNode *next;
};
堆栈与队列2
2021/1/15
3
第4章 堆栈和队列---队列的链式表示和实现
根据队列的性质可见
队列链式表示的两个要素：
队首指针
队尾指针
a1
a2
an
∧
a3
…..
不带头结点的单链表
front
rear
q
堆栈与队列2
2021/1/15
4
第4章 堆栈和队列---队列的链式表示和实现
根据队列的性质可见
队列链式表示的两个要素：
队首指针
队尾指针
链式队列的C语言定义：
struct QueueType{
LNode *front; // 队首指针
LNode *reat; // 队尾指针
};
堆栈与队列2
2021/1/15
5
第4章 堆栈和队列---队列的链式表示和实现
根据队列的性质，要定义队首和队尾指针，用结构表示：
struct QueueType{
LNode *front; // 队首指针
LNode *reat; // 队尾指针
};
用不带表头的单链表来表示
当 front和rear均指向NULL是为空队列
a1
a2
an
∧
a3
…..
不带头结点的单链表
front
rear
q
堆栈与队列2
2021/1/15
6
第4章 堆栈和队列---队列的链式表示和实现
②.基本操作的实现
初始化
//将front和rear置为NULL
void InitQueue(QueueType & q)
{
= = NULL;
}
堆栈与队列2
2021/1/15
7
第4章 堆栈和队列---队列的链式表示和实现
判空
//队列空返回 true， 否则返回 false
bool EmptyQueue(QueueType q)
{
if( == NULL)
return true;
else
return false;
}
return == NULL;
堆栈与队列2
2021/1/15
8
第4章 堆栈和队列---队列的链式表示和实现
入队
bool EnQueue(QueueType & q, ElemType x)
{……
}
a0
a1
an-1
…..
Front
rear
x
P
②
③
④
⑤
front
rear
x
P
②
③
⑤
⑥
队列为空的情况
队列不空的情况:
1) p = new LNode;
2) p -> data = x;
3) p -> next = NULL;
if