文档介绍：第 4 章队列
1
队列是限定只能在表的一端进行插入,而在表的另一端进行删除的线性表
特点:’先进先出’,
队列又称作先进先出表(FIFO,即First In First Out)
2
出队(dlque)
队头front
队尾(rear)
a1
a2
a3
an
入队(enque)
队列的相关概念
Q=(a1,a2,……ai-1,ai,ai+1,……an)
队头(front)在表中允许删除的一端
队尾(rear)允许插入的一端
入队(enque) 向队尾插入一个元素的操作
出队(dlque)从队头取出一个元素的操作
随着入队、出队操作的执行,队列的队头、队尾也不断地随之改变。
应用:
操作系统中作业排队
图的遍历算法层次队列
求解杨辉三角形循环队列
3
队列抽象数据类型描述
数据元素: 可以是各种类型的数据,但必须同属于一个数据元素类。
结构关系: 队列中的n个元素呈线性关系。
基本操作: 对队列可执行以下的基本操作。
Initiate (Q) 构造一个空队列Q。
Clear (Q) 将队列Q清为空队列。
Length (Q) 求长度。
Empty(Q) 判空队列。
Full(Q) 判队列满。
EnQueue(Q,x) 入队列操作。
DlQueue(Q) 出队列操作。
GetFirst(Q) 取队头操作。
4
队列的抽象类定义
//
template <class Telem>
class Queue
{public:
virtual void clear()=0; //清空
virtual int leng()=0; //求长度
virtual bool full()=0; //判队列满
virtual bool empt()=0; //判空队列
virtual bool enque (Telem el)=0;
//将el存入队列,操作成功返回true否则返回false
virtual Telem dlque()=0;
//若队列非空则返回队头元素且删除队头元素,否则返回NULL
virtual Telem getf()=0;
//若队列非空返回队头元素,否则返回NULL
};
5
链队列类
6
队列在计算机中的存储方式可分为顺序存储方式和链式存储方式二种。
队列的存储方式
顺序: 顺序队列,顺序循环队列类
链式: 链队列类
链队列的存储结构
使用一个链表来表
示一个队列:
链尾相当于队尾;
链头相当于队头。
7
Data next
队头
NULL 队尾
rear
front
链队列指针变化状况
8
front
rear
front
rear
front
rear
front
rear
a
a
b
a
b
空队列
进队
进队
出队
front=rear
链队列的类型定义
struct Tnode{ Telem data;
Tnode *next;
};
typedef struct Tnode *Tlink;
typedef struct { Tlink front;
Tlink rear;
}TlinkQueue;
TlinkQueue lq1;
=,这个队列就成为空队列,否则,->next指向队头结点,。
9
data
next
front
rear
链队列的类定义及实现
10
template <class Telem> class LinkQueue;
template <class Telem> class Node
{ friend class LinkQueue <Telem>;
Telem data;
Node <Telem> *next;
public:
Node(Telem d=0,Node <Telem> *n=NULL)
:data(d),next(n){};
};
data
next
链队列结点类的定义