文档介绍：第三章栈与队列 (2)队列部分
数据结构电子教案
殷人昆王宏
1
栈
队列
栈的应用:表达式求值
栈的应用:递归
队列的应用:打印杨辉三角形
双端队列
优先级队列
第三章栈与队列
2
队列的基本概念
只允许在表的一端插入,在另一端删除。
允许插入的一端叫做队尾(rear),
允许删除的一端叫做队头(front)。
队列所具有的这种特性称为先进先出
FIFO(First In First Out)。
a1 a2 a3 …… an
front
rear
3
template <class T>
class Queue {
public:
Queue() { }; //构造函数
~Queue() { }; //析构函数
virtual bool EnQueue(T x) = 0; //进队列
virtual bool DeQueue(T& x) = 0; //出队列
virtual bool getFront(T& x) = 0; //取队头
virtual bool IsEmpty() const = 0; //判队列空
virtual bool IsFull() const = 0; //判队列满
};
队列的抽象数据类型
4
#include <>
#include <>
#include “”
template <class T>
class SeqQueue : public Queue<T> { //队列类定义
protected:
int rear, front; //队尾与队头指针
T *elements; //队列存放数组
int maxSize; //队列最大容量
public:
SeqQueue(int sz = 10); //构造函数
队列的数组存储表示─顺序(循环)队列
5
~SeqQueue() { delete[ ] elements; } //析构函数
bool EnQueue(T x); //新元素进队列
bool DeQueue(T& x); //退出队头元素
bool getFront(T& x); //取队头元素值
void makeEmpty() { front = rear = 0; }
bool IsEmpty() const { return front == rear; }
bool IsFull() const
{ return ((rear+1)% maxSize == front); } //循环
int getSize() const
{ return (rear-front+maxSize) % maxSize; }
};
6
非循环队列的进队和出队(指针变化)
front
rear
空队列
front
rear
A进队
A
front
rear
B进队
A B
front
rear
C, D进队
A B C D
front
rear
A出队
B C D
front
rear
B出队
C D
front
rear
E,F,G进队
C D E F G
C D E F G
front
rear
H进队,假溢出
7
非循环队列的进队和出队原则
进队时先将新元素按 rear 指示位置加入,再将队尾指针加一 rear = rear + 1。
队尾指针指示实际队尾的后一位置。
出队时按队头指针指示位置取出元素,再将队头指针进一 front = front + 1,
队头指针指示实际队头位置。
队满时再进队将溢出出错(可能是假溢出) ;
队空时再出队将按队空处理。
解决假溢出的办法之一:将存放队列元素的数组首尾相接,形成循环(环形)队列。
8
队列存放数组被当作首尾相接的表处理。
队头、队尾指针加1时从maxSize-1直接进到0,可用语言的取模(余数)运算实现。
队头指针进1: front = (front+1) % maxSize;
队尾指针进1: rear = (rear+1) % maxSize;
队列初始化:front = rear = 0;
队空条件:front == rear;
队满条件:(rear+1) % maxSize == front
思考: 按以上定义, 队列中最多可容纳多少元素
循环队列(Circular Queue)
9
0
1
2
3
4
5
6
7
front
0
1
2
3
4
5
6
7
front
0
1
2
3
4
5
6
7
front
rear
A
A
B