原因:
被删除元素的空间没有再被使用
每次出队时向前移一位置。 解决: 大量移动元素 循环队列
11
采用循环队列克服“假上溢”
sq->r
MAXNUM-1
。 。 。
0 1
sq->f
指针移动方向
12
4.5.1 顺序队列
采用循环队列克服“假上溢” 入队：if (sq->r+1>=MAXNUM) sq->r=0; else sq->r++;
3
4.5 队列的实现
4.5.1. 顺序队列 4.5.2. 链队列
4
4.5.1 顺序队列
队列的顺序存储结构简称为顺序队列。顺序队 列实际上是运算受限的顺序表。
由于队列的队头和队尾的位置均是变化的，因
而要设置两个指针，分别指示当前队头元素和队尾 元素在向量空间中的位置。
5
4.5.1 顺序队列
顺序队列的定义
进队列
EnQueue(int value) { //要先判断队列是否已满 if ((tail + 1) % QUEUE_SIZE == head) { printf("队列已满，无法从队尾插入元素\n"); } else { queue[tail] = value; tail = (tail + 1) % QUEUE_SIZE; } }
29
2. 判队空
int isEmptyQueue_seq( PSeqQueue sq ) { return (sq->f == sq->r); }
30
3. 取队头元素
DataType frontQueue_seq( PSeqQueue sq ) /* 对非空队列,求队列头部元素 */ { return (sq->q[sq->f]); }
r
k4
k5 k6 k7 k8 ③队列满
4
5 6 7 ②约定
f r
k7 k8
r
①队列空
④队列数组越界
4.5.1 顺序队列
顺序队列的入队和出队 开;data[sq->r]=x; sq->r++;
出队： sq->f++;
8
4.5.1 顺序队列
元素个数（队列长度）:（sq->r) - (sq->f)
* */ int IsFull(){ if ((tail + 1) % QUEUE_SIZE == head) { printf("队列已满\n"); return 1; } printf("队列未满\n"); return 0;
}
/打印出队列元素 void PrintQueue(){ for (int i = head; i < tail; i++) { printf("%d ",queue[i]); } printf("\n"); }
39
2. 判队空（算法4.22）
int isEmptyQueue_link( PLinkQueue plqu ) {
return (plqu->f == NULL);
}
40
3. 取队头结点数据（算法4.25）
DataType frontQueue_link( PLinkQueue plqu ) /* 在非空队列中求队头元素 */ { return (plqu->f->info); }
#include<stdio.h> #define QUEUE_SIZE 200 int queue[QUEUE_SIZE]; int head=0;//头指针 int tail=0;//尾指针
int main（） { EnQueue(4);EnQueue(1);EnQueue( 2);EnQueue(9);EnQueue(8); PrintQueue(); DeQueue();DeQueue(); PrintQueue(); return 0;
若（sq->r) - (sq->f)=0 ，则队列长度 为0，即空队列。再出队会“下溢”
若 (sq->r)-(sq->f)=MAXNUM，则队满。 队满时再入队会“上溢”
9
顺序队列
f r
0 1 2 3
f
k1 k2 k3
r
4
5 6 7
f r
k5 k6
队列空
队列数组越界
4.5.1 顺序队列
假上溢：当前队列并不满，但不能入队。
利用模运算 sq->r=(sq->r+1)%MAXNUM
出队： sq->f=(sq->f+1)%MAXNUM
13
4.5.1 顺序队列
判断队空和队满
某一元素出队后，若头指针已从后面追上尾指针， 则当前队列为空： sq->f=sq->r
某一元素入队后，若尾指针已从后面追上头指针， 则当前队列为满：
sq->f=sq->r
4.4 队列 队列的概念及运算(逻辑结构)
1
队列的概念
队列 只允许在表的一端进行插入，而在另一端 进行删除。 队头 队尾 允许删除的一端 允许插入的一端
队列是先进先出表
出队
a1
队头
a2
...
an
队尾
入队
2
队列的运算
队列的基本运算：
•
• • • •
创建一个空队列 Queue createEmptyQueue ( void ) 判队列是否为空队列 int isEmptyQueue ( Queue qu ) 往队列中插入一个元素 void enQueue ( Queue qu, DataType x ) 从队列中删除一个元素 void deQueue ( Queue qu ) 求队列头部元素的值 DataType frontQueue ( Queue qu )
an-3 . .
n-3
rear= n-1
front=n-3
an-2 n-2 . . 1 0 rear= n-1
插入元素0：1 rear 顺时针移动一位 MaxQsize-1 2
…… an-3 an-2 x
rear=0 an-3 . .
n-3
front=n-3 front=n-3
an-2 n-2 . . 1 x rear = (rear+1) MOD MaxQSize n-1
队列的链接表示
struct Node; typedef struct Node *pNode; struct Node { DataType info; pNode link; }; struct LinkQueue { PNode f; PNode r; }; typedef struct LinkQueue, *PLinkQueue;
32
5. 出队
void deQueue_seq( PSeqQueue sq ) /* 删除队列头部元素 */ { if( sq->f == sq->r ) printf( "Empty Queue.\n" ); else sq->f = (sq->f + 1) % MAXNUM;
}
33
4.5.2 链队列
31
4. 入队
void enQueue_seq( PSeqQueue sq, DataType x ) /* 在队列中插入一元素x */ { if( (sq->r + 1) % MAXNUM == sq->f ) printf( "Full queue.\n" ); else { sq->q[sq->r] = x; sq->r = (sq->r + 1) % MAXNUM; } }
k2 k3 k4 k5 k6 k1
sq.front
sq.rear
k7
图(a) 空队列
图(b) 队列满
图4.9
循环队列
4.5.1 顺序队列
在循环队列上实现五种基本运算： 1.置空队
2.判队空
3.取队头元素 4.入队 5.出队
17
循环队列
0
1 2
front= n-3
MaxQsize-1
…… an-3 an-2
/判断队列是否为空 int IsEmpty() { if (head == tail) { printf("队列为空\n"); return 1; }
printf("队列不为空\n"); return 0;
}
判断队列是否已满
/** * 我这里判断队满的的方法：
牺牲一个单元来区分队空和队满，入队时少 用一个队列单元。如果数组的大小为Size,那 么实际只能存放(Size-1)个元素。（这是比 较常用的判满的方式）
队列的链式存储结构简称为链队列，它是限制仅在 表头删除和表尾插入的单链表。
显然仅有单链表的头指针不便于在表尾做插入操作， 为此再增加一个尾指针，指向链表上的最后一个结点。 于是，一个链队列由一个头指针和一个尾指针唯一地确
定。
34
plqu f r
k0 k1 k2
….
kn-1

图4.10 队列的链接表示
0 rear=0
删除元素：front顺时针移动一位
front = (front+1) MOD MaxQSize;
. .
..
D
C
0
删除C
front=9
. .
.. 1
D rear
1 rear