文档介绍：第三章队列
队列的定义、操作
队列的顺序存储
队列的链式存储
循环队列
引言:在日常生活中经常会遇到为了维护社会正常秩序而需要排队的情境,在计算机程序设计中也经常出现类似问题。数据结构"队列"与生活中的"排队"极为相似,也是按"先到先办"的原则行事的,并且严格限定:既不允许"加塞儿",也不允许"中途离队"。
一、队列的定义、操作
1、定义:只允许在表的一端进行插入,而在表的另一端进行删除,是一种先入先出的线性表(FIFO)。
a1 a2 …….an
队头队尾
front rear
出队
入队
比较:
堆栈:FILO 输入/输出都在栈顶
队列:FIFO 输入/输出分别由不同端处理
输出端(前端):front
输入端(后端):rear
2、队列中的基本概念
队头(front):允许删除(出队)的一端。
队尾(rear):允许插入的一端。
空队列:队列中没有元素。
进队:队的插入运算,即插入新的队尾元素。
出队:队的删除运算,删除队首元素。
3、队列中的基本运算
入队
出队
取队头元素
置空队列
判队列是否为空
二、队列的顺序存储
1、队列的顺序存储结构,用一组连续的存储单元依次存放队列中的元素。即用数组存储。
2、顺序队列的类型说明
#define MaxSize 10
int queue[MaxSize];
int front = -1;
int rear = -1;
其中:MaxSize—队列的最大容量;
front—记录队列队头的索引值,随数据输出而变动;
rear—记录队列队尾的索引值,随数据输入而变动。
3、顺序队列运算时的头、尾指针变化:
B
A
D
C
3
2
1
0
rear= -1
front= -1
front= -1
rear=1
空队列
A、B相继入队
A、B相继出队
C、D相继入队
rear= 1
front= 1
front= 1
rear=3
队列数组结构图
MaxSize-1
队头指针:front总是指向当前队头元素的前一个位置。
队尾指针:rear指向当前队尾元素的位置。
初始状态:front=rear= -1
入队运算:
rear ++; /*尾指针加1 */
queue[rear]=x; /* x入队*/
出队运算:
front ++; /* 头指针加1 */
4、顺序队列运算时有关约定:
队列长度:rear-front
队空:rear = =front
下溢:队空时再作出队操作。
队满:rear - front = = MaxSize
上溢:队满时再作入队操作。
5、顺序队列中入队的算法描述
void addqueue(int value)
{
if(rear>=MaxSize) printf(“the queue is full”);
else
{
rear++;
queue[rear]=value;
}
}