文档介绍：数据结构与算法
2009年秋季
授课教师：曾文林伟华
授课班级：114081-3班
Chapter6 队列（Queue）
本章教学内容
队列结构特性
抽象数据类型
公式化描述（顺序队列）
链表描述（链队列）
队列应用
栈与队列的综合应用
【回顾】循环队列
FIFO
队列的顺序存储
“假溢出”
循环队列
%运算
front、rear的约定
队空条件：front==rear
队满条件：(rear+1)%Maxsize== front
循环队列演示
算法设计示例
假设以数组Q[m]存放循环队列中的元素, 同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(enqueue)和删除(dlqueue)元素的操作。
#include <>
template <class T> class Queue { //循环队列的类定义
public:
Queue ( int=10 );
~Queue ( ) { delete [ ] elements; }
void EnQueue ( T & item );
T DeQueue ( );
T GetFront ( );
void MakeEmpty ( ) { length = 0; } //置空队列
int IsEmpty ( ) const { return length == 0; } //判队列空否
int IsFull ( ) const { return length == maxSize; } //判队列满否
private:
int rear, length; //队尾指针和队列长度
T *elements; //存放队列元素的数组
int maxSize; //队列最大可容纳元素个数
};
构造函数
template <class T>
Queue<T>:: Queue ( int sz ) : rear (maxSize-1), length (0), maxSize (sz)
{
//建立一个最大具有maxSize个元素的空队列。
elements = new T[maxSize]; //创建队列空间
assert ( elements != 0 ); //断言: 动态存储分配成功与否
}
插入函数
template<class T>
void Queue<T> :: EnQueue ( T &item )
{
assert ( ! IsFull ( ) ); //判队列是否不满，满则出错处理
length++; //长度加1
rear = ( rear +1) % maxSize; //队尾位置进1
elements[rear] = item; //进队列
}
删除函数
template<class T>
T Queue<T> :: DeQueue ( )
{
assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理
length--; //队列长度减1
return elements[(rear-length+maxSize) % maxSize];//返回原队头元素值
}
读取队头元素值函数
template<class T>
T Queue<T> :: GetFront ( )
{
assert ( ! IsEmpty ( ) );
return elements[(rear-length+1+maxSize) % maxSize];//返回队头元素值
}
课后思考题
如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分尾指针和头指针相同时的队列状态时“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法比较好）。
Θ(1)
Θ(1)
Θ(1)
O(n)
队列的链表描述（链队列）
两种链表队列的比较