数据结构课件 第4章 队列.ppt

第四章队列
队列是一种特殊的线性表,是操作受限的线性表,
称其为限定性数据结构。
队列的定义及特点
定义:队列是限定只能在表的一端进行插入,在表的另一端进行删除的线性表
队尾(rear)——允许插入的一端
队头(front)——允许删除的一端
队列特点:先进先出(FIFO)
2017/11/11
1
福州大学数学与计算机科学学院
a1 a2 a3…………………….an
入队
出队
front
rear
队列Q=(a1,a2,……,an)
双端队列
a1 a2 a3…………………….an
端1
端2
入队
出队
入队
出队
2017/11/11
2
福州大学数学与计算机科学学院
ADT队列(Queue)
ADT队列上定义的常用的基本运算
Empty( ):
Full( ):
First( ):
(4) Last():
(5) EnQueue(x):
(6) DeQueue(x):
2017/11/11
3
福州大学数学与计算机科学学院
链队列
结点定义
template <class T>
class Node {
friend class Queue<T>;
private:
T data;
Node<T> *next;
};
2017/11/11
4
福州大学数学与计算机科学学院
用指针实现的队列模板类Queue的定义
template<class T>
class Queue {
public:
Queue( ) {front = rear = 0;}
~Queue( );
bool Empty( ) const {return ((front) ? false : true);}
bool Full( ) const;
T First( ) const;
T Last( ) const;
Queue<T>& EnQueue(const T& x);
Queue<T>& DeQueue(T& x);
private:
Node<T> *front; // 指向队首结点的指针
Node<T> *rear; //指向队尾结点的指针
};
2017/11/11
5
福州大学数学与计算机科学学院
front
rear
x入队
^
x
front
rear
空队
^
^
front
yz入队
x
y
rear
^
z
front
rear
x出队
y
^
z
x
2017/11/11
6
福州大学数学与计算机科学学院
入队算法
出队算法
2017/11/11
7
福州大学数学与计算机科学学院
队列的顺序存储结构
实现:用一维数组实现sq[M]
front=-1
rear=-1
1
2
3
4
5
0
队空
1
2
3
4
5
0
front
J1,J2,J3 入队
J1
J2
J3
rear
rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
front
设两个指针front,rear,约定:
rear指示队尾元素;
front指示队头元素前一位置
初值front=rear=-1
空队列条件:front==rear
入队列:sq[++rear]=x;
出队列:x=sq[++front];
rear
rear
front
rear
1
2
3
4
5
0
J1,J2,J3 出队
J1
J2
J3
front
front
front
2017/11/11
8
福州大学数学与计算机科学学院
存在问题
设数组维数为M,则:
当front=-1,rear=M-1时,再有元素入队发生溢出——溢出
当front-1,rear=M-1时,再有元素入队发生溢出——假溢出
解决方案
队首固定,每次出队剩余元素向下移动——浪费时间
循环队列
基本思想:把队列设想成环形,让sq[0]接在sq[M-1]之后,若rear+1==M,则令rear=0;
0
M-1
1
front
rear
…...
…...
实现:利用“模”运算
入队: rear=(rear+1)%M; sq[rear]=x;
出队: front=(front+1)%M; x=sq[front];
队满、队空判定条件
2017/11/11
9
福州大学数学与计算机科学学院
0
1
2
3
4
5
rear
front
J4
J5
J6
0
1
2
3
4
5
rear
front
J9
J8
J7
J4