文档介绍：队列
网络工程教研中心陈卫卫
出队方向进队方向
a b c … x
first last
队头指针队尾指针
头
尾
顺序队列
学习目标和要求
;
;
第2章表结构解放军理工大学
1. 队列的概念
队的术语和图示:
插入端,队尾(rear)
删除端,队头(front)
first和last:分别指向队头元素和队尾元素
进队和出队
出队进队
a b c … x
first last
第2章表结构解放军理工大学
2. 队列的特点
队结构——管道
一端进入,另一端退出
先进先出表
FIFO表
出队方向进队方向
a b c … x
first last
队头指针队尾指针
第2章表结构解放军理工大学
3. 顺序队
顺序队的基本用法: 首尾指针用法
数组q[m]:
0 1 2 …… n …… m-1
first last
第2章表结构解放军理工大学
3. 顺序队
顺序队的基本用法: 首尾指针用法
[1] last指向当前尾,first指向当前头(麻烦)
0 1 2 …… n …… m-1
first last
0 1 2 …… n …… m-1
a1 a2 ak
first last
第2章表结构解放军理工大学
3. 顺序队
顺序队的基本用法: 首尾指针用法
[2] 尾指针last前置
0 1 2 …… n …… m-1
first last
0 1 2 …… n …… m-1
a1 a2 ak
first last
第2章表结构解放军理工大学
3. 顺序队
顺序队的基本用法: 首尾指针用法
[3] 首指针first后置
0 1 2 …… n …… m-1
first last
0 1 2 …… n …… m-1
a1 a2 ak
first last
第2章表结构解放军理工大学
3. 顺序队
[1] last指向当前尾,first指向当前头(麻烦)
[2] 尾指针last前置
[3] 首指针first后置
如何判断队空?
当first=last=i(i是0~m-1之间的任一值),都
表示队空。
第2章表结构解放军理工大学
3. 顺序队
如何判断队满?
情况1: 在程序执行期间,如果要求进队的元素总量不超过数
组长度m,不会出现队满情况
第2章表结构解放军理工大学