一、队列的定义

 

线性表:是具有相同数据类型的n(n≥0)个数据元素的有限序列,其中n为表长,当n=0时,线性表是一个空表。若用L命名线性表,则其一般表示为L=(a1,a2,...,ai,ai+1,...,an)。

栈:是只允许在一段进行插入或删除操作的线性表。

队列:是只允许在一端进行插入,在另一端删除的线性表。

队头、队尾、空队列

特点:先进先出(FIFO) First in first out

二、队列的基本操作

 2.1 队列的定义
#define MaxSize 10//定义队列中元素的最大个数 typedef struct{ ElemType
data[MaxSize];//用静态数组存放队列元素 int front,rear;//队头指针和队尾指针 }SqQuene; void
testQueue(){ SqQueue Q;//声明一个队列(顺序存储) }//后续操作...

 2.2 初始化操作
void InitQueue(SqQueue &Q){ //初始时,队头、队尾指针指向0 Q.rear=Q.front=0; } void
testQueue(){ //声明一个队列(顺序存储) SqQueue Q; InitQueue(Q); //后续操作... }

 判断队列是否为空
bool QueueEmpty(SqQueue Q){ if(Q.rear==Q.front)//队空条件 return true; else return
false; }
2.3 入队操作

bool EnQueue(SqQueue &Q,ElemType x){ if(队列以满) return false;//队满则报错
Q.data[Q.rear]=x;//将x插入队尾 Q.rear=Q.rear+1;//队尾指针后移 return true; }
Q.data[Q.rear]=x——将 x放入队尾指针所指的位置

 Q.rear=Q.rear+1——队尾指针加一,后移

 静态数组存满后,队尾指针是10

 所以队列已满的条件是:rear==MaxSize????

答案不是

 当取出元素时,rear还是等于10,不会变,但这时候队列有空

所以更改代码,采用取余操作Q.rear=(Q.rear+1)%MaxSize,将存储空间从逻辑上变成了“环状”
bool EnQueue(SqQueue &Q,ElemType x){ if(队列以满) return false;//队满则报错
Q.data[Q.rear]=x;//将x插入队尾 Q.rear=(Q.rear+1)%MaxSize;//队尾指针+1取模 return true; }
 因为判断队满的条件是判断rear==front,因此必须牺牲一个单元

 队列已满的条件:队尾指针的在下一个位置是队头,即(Q.rear+1)%MaxSize==Q.front;
bool EnQueue(SqQueue &Q,ElemType x){ if((Q,rear+1)%MaxSize==Q.front)//判断队满条件
return false;//队满则报错 Q.data[Q.rear]=x;//将x插入队尾
Q.rear=(Q.rear+1)%MaxSize;//队尾指针+1取模 return true; }
队列元素个数:

(rear+MaxSize-front)%MaxSize 

2.4 出队操作

只能让队头元素出队
//出队(删除一个队头元素,并用x返回) bool DeQueue(SeQueue &Q,ElemType &x){ if(Q.rear==Q.front)
return false;//队空则报错 x=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return
ture; }
2.5 队列查找

获得队头元素,用x返回
bool GetHead(SqQueue Q,ElemType &x){ if(Q.rear==Q.front) return false;//队空则报错
x=Q.data[Q.front]; return true; }
其他元素呢???

2.6 不浪费内存条件下判断队列已满/已空

方法二:
#define MaxSize 10 typedef struct{ ElemType data[MaxSize]; int front,rear; int
size;//队列当前长度 }SqQuene;
初始化时rear==front==0;size=0;

插入成功:size++

删除成功:size--;

队满条件:size==MaxSize;

队空条件:size==0;

方法三:
#define MaxSize 10 typedef struct{ ElemType data[MaxSize]; int front,rear; int
tag;//最近进行的是删除(0)/插入(1) }SqQuene;
初始化时,rear=front=0;tag=0;

每次删除操作成功时,都令tag=0;

每次插入操作成功时,都令tag=1;

只有删除操作才可能导致队空,因此队空条件为:front==rear&&tag==0;

同理,队满条件为:front==rear&&tag==1;

2.7 rear指针指向队尾元素情况

判空:

(Q.rear+1)%MaxSize==Q,front

判满:

(Q.rear+1)%MaxSize==Q,front

两种方法:

1.牺牲一个存储单元:

rear与front隔了两个单元,队满、隔了 一个单元,队空

2.增加辅助变量

size、tag

三、链式存储实现队列

3.1 队列的链式实现
typedef struct LinNode{//链式队列结点 ElemType data; struct LinkNode *next;
}LinkNode; typedef struct{//链式队列 LinkNode *front,*rear;//队列的队头和队尾指针 }LinkQueue;

 3.2 初始化

带头结点
typedef struct LinkNode{ ELEMtype data; struct LinkNode *next; }LinkNode;
typedef struct{ LinkNode *front,*rear; }LinkQueue; //初始化队列 void
InitQueue(LinkQueue &Q){ //初始时 front、rer都指向头结点
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); Q.front->next=NULL;//判空操作 }
void testLinkQueue(){ LinkQueue Q;//声明一个队列 InitQueue(Q);//初始化一个队列 //后续操作.... }
其他判空操作:

bool IsEmpty(LinkQueue Q){ if(Q.front==Q.rear) return true; else return false;
}
不带头结点

 3.3 入队操作

带头结点
void EnQueue(LinkQueue &Q,ElemType x){ LinkNode *s=(LinkNode
*)malloc(sizeof(LinkNode)); s->data=x; s->next=NULL;
Q.rear->next=s;//新结点插入rear之后 Q.rear=s;//修改表尾指针 }
元素都是队尾插入,所以s的next指针为空 

 不带头结点

 3.4 出队操作

带头结点

bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.front==Q.rear) return false;//空队
LinkNode *p=Q.front->next; x=p->data;//用变量x返回队头元素
Q.front->next=p->next;//修改头结点的next指针 if(Q.rear==p)//此次是最后一个结点出队
Q.rear=Q.front;//修改rear指针 free(p);//释放结点空间 return true; }

不带头结点

四、双端队列

只允许从两端插入、两端删除的线性表 

 若只使用其中一端插入、删除操作,则效果等同于栈

技术
今日推荐
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信