数据结构（4）—— 队列的实现

文章目录

1. 什么是队列队列的抽象数据类型描述 2. 队列的顺序存储（1）入队列（2）出队列 3.队列的链式存储不带头结点的链式队列出队操作

1. 什么是队列

队列（Queue）：具有一定操作约束的线性表

插入和删除操作：只能在一端插入，而在另一端删除。

数据插入：入队列（AddQ）

数据删除：出队列（DeleteQ）

先进先服务

先进先出：FIFO

队列的抽象数据类型描述

类型名称：队列（Queue）

数据对象集：一个有0个或多个元素的有穷线性表

操作集：长度为MaxSize的队列Q∈Queue，队列元素item∈ElementType

Queue CreatQueue(int MaxSize)：生成长度为MaxSize的空队列；int IsFullQ(Queue Q,int MaxSize)：判断队列Q是否已满；void AddQ(Queue Q,ElementType item)：将数据元素item插入队列Q中；int IsEmptyQ(Queue Q)：判断队列Q是否为空；ElementType DeleteQ(Queue Q)：将队头数据元素从队列中删除并返回。

2. 队列的顺序存储

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾位置的变量rear组成。

#define MaxSize <存储数据元素的最大个数> struct QNode{ ElementType Data[MaxSize]; int rear; int front; }; typedef struct QNode *Queue;

解决循环队列无法判断是否满队或者全空的两种方案： ① 设置一个标志位 ② 空出一个位置不用

（1）入队列

void AddQ(Queue PtrQ,ElementType item) { if((PtrQ->rear+1)%MaxSize == PtrQ->front) { printf("队列满"); return; } PtrQ->rear = (PtrQ->rear+1)%MaxSize; PtrQ->Data[PtrQ->rear]=item; }

（2）出队列

ElementType DeleteQ(Queue PtrQ) { if(PtrQ->front == PtrQ->rear) { printf("队列空"); return ERROR; }else{ PtrQ->front = (PtrQ->front+1)%MaxSize; return PtrQ->Data[PtrQ->front]; } }

3.队列的链式存储

队列的链式存储结构也可以用一个单链表实现，插入和删除操作分别在链表的两头进行；

struct Node{ ElementType Data; struct Node *Next; }; struct QNode{ /* 链队列结构 */ struct Node *rear; /* 指向队尾结点 */ struct Node *front; /* 指向队头结点 */ }; typedef struct QNode *Queue; Queue PtrQ;

不带头结点的链式队列出队操作

ElementType DeleteQ(Queue PtrQ) { struct Node *FrontCell; ElementType FrontElem; if(PtrQ->front == NULL){ printf("队列空"); return ERROR; } FrontCell = PtrQ->front; if(PtrQ->front == PtrQ->rear) /* 若队列只有一个元素 */ PtrQ->front = PtrQ->rear = NULL; /* 删除后队列置为空 */ else PtrQ->front = PtrQ->front->Next; FrontElem = FrontCell->Data; free(FrontCell); /* 释放被删除节点空间 */ return FrontElem; }