文章目录提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
- 一、队列的定义
- 二、队列的相关术语
- 三、队列的基本操作
- 四、队列的存储结构
- 4.1 顺序存储--顺序队列
- 4.1.1 顺序队列定义
- 4.1.2 顺序队列初始化
- 4.1.3 顺序(循环)队列出队以及判空操作
- 4.1.4 顺序(循环)队列入队以及判满操作
- 4.1.5 顺序(循环)队列不浪费空间去区分队空队满
- 4.1.5.1 方案一：队列中元素的个数
- 4.1.5.2 方案二：设置tag
- 4.2 链式存储--链队列
- 4.2.1 链队列定义
- 4.2.2 链队列初始化
- 4.2.3 链队列入队操作
- 4.2.4 链队列出队操作
- 五、队列的应用
- 六、总代码
- 6.1 顺序队列（已验证）
- 6.2 链队列（已验证）
队列是一种特殊的线性表（限定性的线性表），是只允许在一端进行插入，在另一端进行删除的线性表
二、队列的相关术语空队、队头、队尾
特点：先进先出
InitQueue(Q): 初始化队列
EnterQueue(Q,x): 插入操作
DeleteQueue(Q,x): 删除操作
GetHead(Q,x)：查询操作，不出队
IsEmpty (Q):判空操作
IsFull(Q)：判满操作
#define MAXSIZE 10
typedef struct{
char data[MAXSIZE]; //静态数组存放队列元素
int front; //队头指针
int rear; //队尾指针
}SeqQueue;
4.1.2 顺序队列初始化
//初始化
void InitQueue(SeqQueue *Q){
printf("初始化队列n");
Q->front=Q->rear;
}
4.1.3 顺序(循环)队列出队以及判空操作
//出队
int DeleteQueue(SeqQueue *Q,char *c){
if(isEmpty(Q)){
printf("队列中没有元素n");
return 0;
}else{
*c=Q->data[Q->front];
Q->front=(Q->front+1)%MAXSIZE;
return 1;
}
}
//判空
int isEmpty(SeqQueue *Q){
if(Q->front==Q->rear){
return 1;
}else
return 0;
}
4.1.4 顺序(循环)队列入队以及判满操作
那么什么时候为队满？
rear=MaxSize时为队满？
因此有了循环队列：
//进队
int EnterQueue(SeqQueue *Q,char c){
if(isFull(Q)){
printf("队列已满n");
return 0;
}else{
Q->data[Q->rear]=c;
Q->rear=(Q->rear+1)%MAXSIZE;
printf("插入成功n");
printf("队尾指针：%dn",Q->rear);
return 1;
}
}
//判满
int isFull(SeqQueue *Q){
if((Q->rear+1)%MAXSIZE==Q->front){
return 1;
}else
return 0;
}
4.1.5 顺序(循环)队列不浪费空间去区分队空队满
4.1.5.1 方案一：队列中元素的个数
size=(rear+MAXSIZE-front)%MAXSIZE
队满时：
队空时：
最近执行的是出队操作置为0
最近执行的是入队操作置为1
执行入队操作：
队满时：
执行出队操作：
队空时：
typedef struct LinkNode{
char data;
struct LinkNode *next;
}LinkQueueNode;
typedef struct{
LinkQueueNode *front; //队头指针
LinkQueueNode *rear; //队尾指针
}LinkQueue;
4.2.2 链队列初始化
//初始化
int InitQueue(LinkQueue *Q){
//头尾指针
Q->front=Q->rear=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
if(Q->front!=NULL){
Q->front->next=NULL;
return 1;
}
else return 0;
}
4.2.3 链队列入队操作
//入队操作
int EnterQueue(LinkQueue *Q,char x){
LinkQueueNode *s=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
if(s!=NULL){
s->data=x;
s->next=NULL;
Q->rear->next=s;
Q->rear=s;
return 1;
} else return 0;
}
4.2.4 链队列出队操作
//出队操作
int DeleteQueue(LinkQueue *Q,char *x){
//判断队列是否为空
if(Q->front==Q->rear)
return 0;
LinkQueueNode *p;
p=Q->front->next;
Q->front->next=p->next;
if(Q->rear==p){ //p是最后一个元素
Q->rear=Q->front;
}
*x=p->data;
free(p);
return 1;
}
五、队列的应用
树的层次遍历、图的广度优先遍历(之后会提到)
#include6.2 链队列（已验证）#include #define MAXSIZE 10 typedef struct{ char data[MAXSIZE]; //静态数组存放队列元素 int front; //队头指针 int rear; //队尾指针 }SeqQueue; //初始化 void InitQueue(SeqQueue *Q){ printf("初始化队列n"); Q->front=Q->rear; } //判空 int isEmpty(SeqQueue *Q){ if(Q->front==Q->rear){ return 1; }else return 0; } //判满 int isFull(SeqQueue *Q){ if((Q->rear+1)%MAXSIZE==Q->front){ return 1; }else return 0; } //进队 int EnterQueue(SeqQueue *Q,char c){ if(isFull(Q)){ printf("队列已满n"); return 0; }else{ Q->data[Q->rear]=c; Q->rear=(Q->rear+1)%MAXSIZE; printf("插入成功n"); printf("队尾指针：%dn",Q->rear); return 1; } } //出队 int DeleteQueue(SeqQueue *Q,char *c){ if(isEmpty(Q)){ printf("队列中没有元素n"); return 0; }else{ *c=Q->data[Q->front]; Q->front=(Q->front+1)%MAXSIZE; return 1; } } //获取队头元素 不出队 int GetHead(SeqQueue *Q,char *c){ if(isEmpty(Q)){ printf("队列中没有元素n"); return 0; }else{ *c=Q->data[Q->front]; return 1; } } int main(){ SeqQueue queue; InitQueue(&queue); printf("==================入队操作==================n"); EnterQueue(&queue,'a'); EnterQueue(&queue,'b'); EnterQueue(&queue,'c'); EnterQueue(&queue,'d'); printf("==================出队操作==================n"); char res1; DeleteQueue(&queue,&res1); printf("取出的队头元素为：%cn",res1); printf("==================查询操作==================n"); char res2; GetHead(&queue,&res2); printf("取出的队头元素为：%cn",res2); }
代码如下（示例）：
#include#include typedef struct LinkNode{ char data; struct LinkNode *next; }LinkQueueNode; typedef struct{ LinkQueueNode *front; //队头指针 LinkQueueNode *rear; //队尾指针 }LinkQueue; //初始化 int InitQueue(LinkQueue *Q){ //头尾指针 Q->front=Q->rear=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); if(Q->front!=NULL){ Q->front->next=NULL; return 1; } else return 0; } //入队操作 int EnterQueue(LinkQueue *Q,char x){ LinkQueueNode *s=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); if(s!=NULL){ s->data=x; s->next=NULL; Q->rear->next=s; Q->rear=s; return 1; } else return 0; } //出队操作 int DeleteQueue(LinkQueue *Q,char *x){ //判断队列是否为空 if(Q->front==Q->rear) return 0; LinkQueueNode *p; p=Q->front->next; Q->front->next=p->next; if(Q->rear==p){ //p是最后一个元素 Q->rear=Q->front; } *x=p->data; free(p); return 1; } int main(){ LinkQueue Q; //声明一个队列 InitQueue(&Q); //初始化一个队列 printf("==================入队操作====================="); EnterQueue(&Q,'a'); EnterQueue(&Q,'b'); EnterQueue(&Q,'c'); EnterQueue(&Q,'d'); EnterQueue(&Q,'e'); }
