中南大学：《数据结构》课程教学资源（PPT课件讲稿）第二章 数据结构与算法概述（2.3）栈和队列 2.3.2 队列 2.4 数组（线性表的推广）

2.3栈和队列 栈和队列是两种特殊的线性表,它们是运算时要 受到某些限制的线性表,故也称为限定性的数据 结构。 (续)

2.3 栈和队列 栈和队列是两种特殊的线性表，它们是运算时要 受到某些限制的线性表，故也称为限定性的数据 结构。 (续)

232队列 2321队列的定义与运算 定义:一种特殊的线性结构,限定只能在表的一端进行插入,在 表的另一端进行删除的线性表。此种结构称为先进先出(FIFO) 表 a1 a2, a 3,a 4 a n-1, an 队头 队列示意图 队 尾 队列的主要运算 (1)设置一个空队列; (2)插入一个新的队尾元素,称为进队; (3)删除队头元素,称为出队; (4)读取队头元素;

队列的主要运算 （1）设置一个空队列； （2）插入一个新的队尾元素，称为进队； （3）删除队头元素，称为出队； （4）读取队头元素； 2.3.2 队列 2.3.2.1 队列的定义与运算 定义：一种特殊的线性结构，限定只能在表的一端进行插入，在 表的另一端进行删除的线性表 。此种结构称为先进先出（FIFO） 表。 a1 , a2 , a3 , a4 , ………… an-1 , an 队 列 示 意 图 队 头 队 尾

2.队列的存储结构 (a)线性队列 (1)顺序存储结构 (b)循环队列

2. 队列的存储结构 （1）顺序存储结构 (a) 线性队列 (b) 循环队列

(a)线性队列 队空时,令rear= front=-1,当有 新元素入队时,尾指针加1,当有元 素出队时,头指针加1。故在非空队 列中,头指针始终指向队头元素前 个位置,而尾指针始终指向队尾元素 的位置 3 rear =4 2 rear 3 2 front→ 0 front (a) (b) (c) rear= front=1(队空)(b)e1,e2,e3入队(c)el,e2出队,c4入队 队满

(a)线性队列 3 2 1 0 (a) rear=front=-1(队空） e3 e4 (c) (c) e1,e2出队，e4入队 队 满 rear =4 front e1 e2 e3 (b) rear front (b)e1,e2,e3入队 队空时，令rear=front=-1，当有 新元素入队时，尾指针加1，当有元 素出队时，头指针加1。故在非空队 列中，头指针始终指向队头元素前一 个位置，而尾指针始终指向队尾元素 的位置

(1)一般情况 rear front (b)循环队列 rear 将头尾连接成一 3 front 个环,形成循环 队列 e3 rear (3)队空 队满条件: 5 (Qrear+1)%MAX=Q front 3 front 注:实际上为了避免与队空标 志冲突,还留有一个空间。 队满

(b) 循环队列 rear front 0 1 2 3 (3) 队空 队满条件： (Q.rear+1)%MAX=Q.front 注：实际上为了避免与队空标 志冲突，还留有一个空间。 将头尾连接成一 个环，形成循环 队列。 e4 e3 (2) 队满 front e3 e4 0 1 2 3 rear e5

循环队列中加入一个元素的算法: int EnQueue(int QI lint x, int*pf,int*pr 将插入 已有队列 Q[max]己 的尾指针 有的循环 的值 队列 已有队列 的头指针

循环队列中加入一个元素的算法： int EnQueue(int Q[ ],int x, int *pf,int *pr) Q[max]已 有的循环 队列 将插入 的值 已有队列 的头指针 已有队列 的尾指针

循环队列中加入一个元素的算法: int En Queue(int Ql l,int x, int *pf, int*pr) f int front, rears front=*pf; rear=*pr; if((rear+1)%MAX==front) return(0) else MRearIR99040 f rear(rear+1)%MAX; Rear=x; arrear, 0 return(1); ont 3

循环队列中加入一个元素的算法： int EnQueue(int Q[ ],int x, int *pf,int *pr) { int front, rear; front=*pf; rear=*pr; if((rear+1)%MAX= =front) return(0); else { rear=(rear+1)%MAX; Q[rear]=x; *pr=rear; return(1);} } e4 e3 rear x

循环队列中删除一个元素的算法 int DeQueue(int Q, int py, int * pf, int *pr) 已有的循环 队列 已有队列 返回删 的尾指针 除的值 的地址 已有队列 的头指针

循环队列中删除一个元素的算法： int DeQueue(int Q[ ]，int *py， int *pf，int *pr) 已有的循环 队列 返回删 除的值 的地址 已有队列 的头指针 已有队列 的尾指针

循环队列中删除一个元素的算法 int DeQueue(int Ql, int py, int pf, int*pr) i int front, rear front=*pf; rear=*pr; if(rear==front)return(0) else i front(front+1%MAX; *py=Q front]; ¨pf- front; return(1);

循环队列中删除一个元素的算法： int DeQueue(int Q[ ]，int *py，int *pf，int *pr) { int front, rear; front=*pf; rear=*pr; if(rear= =front) return(0); else { front=(front+1)%MAX; *py=Q[front]; *pf=front; return(1);} }

(2)链式存储结构 Q front 队头 Q front a 删除一个元素 2 Q rear 队尾Q. .rear 添加 个元素 QI front a a n O rear

an a2 a1 an a3 a2 Q.front Q.rear 删 除一个元素 添加 一个元素 a1 a2 an e ^ Q.front Q.rear （2） 链式存储结构 Q.front Q.rear 队头 队尾 Q.rear Q.front