目录
一：队列的表示和操作的实现
1.1 队列的示意图
1.2 队列的介绍
1.3：相关概念
1.4 实际生活中的实例
二：队列的抽象数据结构和 操作代码
2.1 抽象的数据结构
2.2 队列的顺序表示和实现 （分析和思考）
2.2.1 顺序队列的数据结构
2.2.2 顺序队列的入队和出队 图示：
编辑编辑
2.2.3 溢出思考：
2.3循环队列的表示和实现
2.3.1 循环队列的类型定义
2.3.2 循环队列的初始化
2.3.3 循环队列的求队列长度
2.3.4 循环队列入队
2.3.5 循环对列的出队
2.3.6 取队头元素
2.4：链队的表示和实现
关于链队的一些重点
2：链式队列的表示和基本操作
实例练习：行排队叫号系统
一：队列的表示和操作的实现
1.1 队列的示意图
类似：排队 滴水漏斗
1.2 队列的介绍
队列(Queue)是仅在表尾进行插入操作，在表头进行删除操作的线性表表尾即an端，称为队尾; 表头即a1端，称为队头。它是一种先进先出( FIFO )的线性表。插入元素称为人队;删除元素称为出队。队列的存储结构为链队或顺序队(常用循环顺序队)1.3：相关概念
逻辑结构：同线性表 一一对应关系
存储结构：顺序和链队，循环队列最常见
运算规则：只在队首和队尾运算，先进先出FIFO原则
实现方式：入队和出队等重要实现方式
1.4 实际生活中的实例
■脱机打印输出:按申请的先后顺序依次输出。
■多用户系统中，多个用户排成队，分时地循环使用CPU和主存
■按用户的优先级排成多个队，每个优先级一个队列
■实时控制系统中，信号按接收的先后顺序依次处理
二：队列的抽象数据结构和 操作代码
2.1 抽象的数据结构
2.2 队列的顺序表示和实现 （分析和思考）
2.2.1 顺序队列的数据结构
#define MAXQSIZE 100 //最大队列长度
typedef struct{
QElemType *base;//初始化的动态分配存储空间
int front;// 头指针
int rear; //尾指针
}SqQueue;
2.2.2 顺序队列的入队和出队 图示：
2.2.3 溢出思考：
数组大小为MAXQSIZE
rear = MAXQSIZE front !=0 再入队，发生假溢出
rear =MAXQSIZE front = 0 再入队，发生真溢出
如何解决假上溢？ 循环队列
解决方法：
继续解决：队满判断方法
2.3循环队列的表示和实现
2.3.1 循环队列的类型定义
#define MAXQSIZE 100 //最大队列长度
typedef struct{
QElemType *base;//初始化的动态分配存储空间
int front;// 头指针
int rear; //尾指针
}SqQueue;
2.3.2 循环队列的初始化
Status InitQueue(SqQueue &Q){
Q.base = (QElemType*)malloc(sizeof(QElemType));//分配数组空间
if(!Q.base) exit(OVERFLOW); //存储分配失败
Q.front =Q.rear =0;// 头指针置为 0 队列为空
return OK;
}
2.3.3 循环队列的求队列长度
int QueueLengh(SqQueue Q){
return ((Q.rear-Q.front+MAXSIZE)%MAXSIZE);
}
2.3.4 循环队列入队
Status EnQueue(SqQueue &Q,QElemType e){
if((Q.rear+1)%MAXSIZE==Q.front) return ERROR; //队满
Q.base[Q.rear]=e; //新元素入队尾
Q.rear = (Q.rear+1)%MAXSIZE; //队尾指针+1
return OK;
}
2.3.5 循环对列的出队
Status DeQueue(SqQueue &Q,QElemType &e){
if(Q.rear==Q.front) return ERROR; //队空
e = Q.base[Q.rear]; //新元素入队尾
Q.front = (Q.front+1)%MAXSIZE; //队尾指针+1
return OK;
}
2.3.6 取队头元素
SElemType GetHead(SqQueue Q){
if(Q.front!=Q.rear)// 队列不为空
return Q.base[Q.front]; // 返回对头指针元素的值 队头指针不变
}
2.4：链队的表示和实现
关于链队的一些重点
1：链队（链式队列）和循环队列（顺序队式）是队列的不同的表示方式。那么什么时候使用队列什么时候使用链队？
若用户无法估计所用队列的长度，则宜采用链队列
2：链队和栈链的不同？
链队先进先出（FIFO）和栈链后进先出（LILO），类比银行排队（链队）,弹夹子弹出膛（栈链）
3：链队和栈链的相似之处
栈和队列是限定插入和删除只能在表的"端点”进行的线性表
2：链式队列的表示和基本操作
链式队列的表示
（Q.front指向头结点,Q.rear指向尾结点）
心中有图 撸码自然神
一：链队的类型表示：
typedef int Status;
typedef int QElemType;
typedef struct Qnode{ //创建节点类型=data数据域＋*next指针域
QElemType data;
struct Qnode *next;
}QNode,*QueuePtr;//别名
//补： *QueuePtr指向该节点的指针类型
//引：所以Q.front是什么类型 ，有什么用？
//Q代表什么？
typedef struct{
QueuePtr front;
QueuePtr rear
}LinkQueue;//由两个结构体指针组成了链式队列
二：链队列的指针变化状况
基本操作的本质就是不同指针的不同变化状况
心中有图 撸码自然神
三：链队的操作
1 初始化
Status initQueue(LinkQueue &Q){
Q.front=Q.rear=(QueuePtr*)malloc(sizeof(QNode));
// 或者Q.front=Q.rear=new QNode;
Q.front->next=NULL;
return OK;
}
2 链队的销毁
Status DestroyQueue(LinkQueue &Q){
while(Q.front){
QueuePtr p；
p=Q.front->next;
free(Q.front)；
Q.front=p;
}
return OK;
}
3 链队列入队
Status EnLinkQueue(LinkQueue &Q,QElemType e){
QNode *p=new QNode;//或者p=(QueuePtr)malloc(sizeof(QNode));
if(!p)exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
4：链队列出队
在头结点上操作
Status DeLinkQueue(LinkQueue &Q,QElemType &e){
if(Q.front==Q.rear)return ERROR;
// QNode *p=new QNode;
QueuePtr p;
p= Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
delete p;
return OK;
}
5：算链队列的对头元素
了解队头是：Q.front还是Q.front->next?
Q.front：头结点 || Q.front->next ：队头元素x 所以：对头元素x在头结点的下一位置上
Status GetHead(LinkQueue &Q,QElemType &e){
if(Q.front==Q.rear)return ERROR;
e=Q.front->next->data;
return OK;
}
实例练习：行排队叫号系统
编写程序实现银行排队叫号系统，采用链队列作为存储结构。
//编写程序实现银行排队叫号系统，采用链队列作为存储结构。
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
#define MAX_QSIZE 30
typedef int Status;
typedef int QElemType;
typedef struct Qnode
{
QElemType data;
struct Qnode * next;
}QNode, *QueuePtr;//创建节点类型
typedef struct Queue{
QueuePtr front ; //队首指针
QueuePtr rear ; //队尾指针
}LinkQueue;
Status InitLinkQueue(LinkQueue &Q);//对链队列进行初始化
Status EnLinkQueue(LinkQueue &Q,QElemType e);//入队
Status DeLinkQueue(LinkQueue &Q,QElemType &e);//出队
Status QueueEmpty(LinkQueue Q);//判断队空
/* 请在这里填写答案 */
Status InitLinkQueue(LinkQueue &Q){
Q.front =Q.rear =(QNode*)malloc(sizeof(QNode));
Q.front->next= NULL;
return OK;
}
Status EnLinkQueue(LinkQueue &Q,QElemType e){
QNode *p=new QNode;
if(!p)exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
Status DeLinkQueue(LinkQueue &Q,QElemType &e){
if(Q.front==Q.rear)return ERROR;
// QNode *p=new QNode;
QueuePtr p;
p= Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
delete p;
return OK;
}
int main()
{
QElemType no=1;
QElemType callno;
int select,flag=1;
LinkQueue qu;
InitLinkQueue(qu);
while(flag==1)
{
//printf("1:排队2:叫号0:退出 请选择:");
scanf("%d",&select);
switch(select)
{
case 1: printf("您的序号为:%d\n",no);
EnLinkQueue(qu,no); //no入队
no++;
break;
case 2: if(DeLinkQueue(qu,callno)==ERROR)
printf(">>没有排队的客户!\n");
else//队不空
printf(">>请%d号办理业务\n",callno);
break;
case 0:flag=0;
}
}
return 0;
}
