《计算机软件基础》第二章 线性数据结构（2-4）队列

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

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

242队列的顺序存储结构 a)线性队列 ☆顺序存储结构 (b)循环队列 线性队列:一维数组实现,用两个整型变量分别记 下队头( front)和队尾(rear)的位置; 循环队列:在线性队列基础上,为了解决“假溢出” 问题,在对队列操作中加入取模运算,使队列的存取 可在一个假想的环形内存区域上进行,节约了内存

2.4.2 队列的顺序存储结构 ❖ 顺序存储结构 (a) 线性队列 (b) 循环队列 • 线性队列：一维数组实现，用两个整型变量分别记 下队头（front）和队尾（rear）的位置； • 循环队列：在线性队列基础上，为了解决“假溢出” 问题，在对队列操作中加入取模运算，使队列的存取 可在一个假想的环形内存区域上进行，节约了内存

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

(a)线性队列 3 2 1 0 (a) rear=front= -1(队空） e3 e4 (c) (c) e1,e2出队，e4入队 队 满 rear =3 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 (rear+1)% maxlen=front (3)队空 注:实际上为了避免与队空标志冲 5 突,还留有一个空间。 3 队空条件: . front front = rear 队满

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

顺序存储队列的类型定义: tdefine maxlen 4 typedef struct queuetype Datatype q LMAXLEN] int front rear 泛指任何数据类型,具体 编程时应指定实际类型 J Queue

❖ 顺序存储队列的类型定义： #define MAXLEN 4 typedef struct queuetype {datatype q[MAXLEN]; int front,rear; }Queue; 泛指任何数据类型,具体 编程时应指定实际类型

(1)循环队列的初始化(置空队)算法: void InitQueue(Queue *sg) sq->front=sq->rear=0

(1)循环队列的初始化（置空队）算法： void InitQueue(Queue *sq) { sq->front=sq->rear=0; }

(2)循环队列的入队算法: void EnQueue (Queue *sq,int x) Rif(sq->rear+l)%MAXLEN==Sq->front) printf( queue is full!n); ese isq->rear=(sq->rear+1)%MAXLEN rear maslen=4 sq->qsq->rear=x; fE)g44=0 0 e ont 3

(2) 循环队列的入队算法： void EnQueue(Queue *sq,int x) {if((sq->rear+1)%MAXLEN==sq->front) printf("queue is full!\n"); else {sq->rear=(sq->rear+1)%MAXLEN; sq->q[sq->rear]=x; } } e4 e3 rear x

(3)循环队列的出队算法: int DelQueue(Queue *sq) Rif(sq->front==sq->rear) Sprintf( stack is empty! n") exit(1); else sq->front=(sq->front+1)%MAXLEN; return(sq->qIsq->front;

(3) 循环队列的出队算法： int DelQueue(Queue *sq) {if (sq->front==sq->rear) {printf("stack is empty!\n"); exit(1);} else {sq->front=(sq->front+1)%MAXLEN; return(sq->q[sq->front]); } }

2.4.3队列的链式存储结构 用带头结点的单链表存储,并且分别记下 队头和队尾结点的地址。 frontrear a a

用带头结点的单链表存储，并且分别记下 队头和队尾结点的地址。 2.4.3 队列的链式存储结构 front rear a1 a2 an ^ …

队列的链式存储数据类型的定义: typedef struct nodetype i datatype data struct node next } nodetype;//结点类型定义 typedef struct queuetype nodetype* front;//队头指针 nodetype*rear;//队尾指针 J QueueL

typedef struct nodetype { datatype data; struct node next; }nodetype;//结点类型定义 typedef struct queuetype { nodetype *front;//队头指针 nodetype *rear; //队尾指针 }QueueL; ❖ 队列的链式存储数据类型的定义：