数据结构之队列

队列的定义

队列：只允许在一端进行插入，在另一端删除的线性表

插入操作：入队
删除操作：出队

形象比喻

排队

一些相关术语

队列的基本操作

队列的顺序实现

结构体

typedef struct a{
int data[MaxSize];//用静态数组存放数据元素
int front,rear;//队头指针和队尾指针
}*Queue,SqQueue;
1
2
3
4

初始化

void Iint(Queue a){//初始化
    a->front=a->rear=0;//队头刚开始指向0，队尾的一直让他作为插入元素存放的位置（已有元素后一个位置），刚开始0也没有元素正好=0
}
1
2
3

入队操作

改进前代码

bool EnQuene(Queue Q,int e){
	if(队列满的条件)//之后我们探索队列什么时候是满的
	return false;
	Q->data[Q->rear]=e;
	rear++;//这句话有问题，看后面操作
	return true;
}
1
2
3
4
5
6
7

大多数同学可能认为
当rear==MaxSize
就是满的了

但是不一定，因为
当进行出队操作时front向后移
所以其实前面是有空余的数组位置的，并没有填满

那么如何实现插入到前面的操作呢？
可以把

Q->rear++；变为
Q->rear=(Q->rear+1)%MaxSize;
1
2

这样当rear=9时（最后一个位置），就会又会回到0，开始插入操作
这样不算插队，原本队尾和队头的位置就是front和rear对应空间，而不是对应实际的内存空间

那么这样判断满的操作怎么做呢?

(Q->rear+1)%MaxSize==Q->front
1

用这行代码喽
这行代码会浪费一个数据空间
因为是+1后的结果=之前的front
为什么要这样呢？
因为我们刚开始就是使front=rear=0
如果写Q->rear==Q->front
两个扩机相同不合理，所以只能浪费一个空间做判满喽

改进后代码

bool EnQuene(Queue Q,int e){
	if((Q->rear+1)%MaxSize==Q->front)
	return false;
	Q->data[rear]=e;
	Q->rear=(Q->rear+1)%MaxSize;
	return true;
}
1
2
3
4
5
6
7

出队操作

bool DeQueue(Queue Q,int *x){
if(Q->real==Q->front)//当队列为空时
	return false;
	*x=Q->data[Q->front];
	Q->front=(Q->front+1)%MaxSize;
	return true;	
}
1
2
3
4
5
6
7

图片左下方是获取队列元素的对头元素

顺序队列队长计算

int Length(Node *q) {
	return (q->rear - q->front + MaxSize) % MaxSize;
}

1
2
3
4

判断队列空/满/队列的元素个数

主要看队列元素
用(rear+MaxSize-front)%MaxSize计算

不浪费空间的做法size

多定义一个size来储存队列长度
好判断
队列满还是空

不浪费空间tag记录删除和插入篇

当队尾指向的就是队尾元素

当队尾就是指向队尾元素时候

而不是队尾元素的下一个元素
要先+1个元素在进行赋值操作

这个时候赋初始值
应该使
队头=0
队尾=Maxsize-1

Q->rear=(Q->rear+1)%Maxsize;
Q->data[Q->rear]=x;
1
2

判断空和满

其实原来的方法看似能判满
其实不行

判断空是后一个位置
判断满不可能也是后一个位置啊
所以
1.牺牲一个存储单元

判断空
(Q->rear+1)%MaxSize==Q->front;
判断满
(Q->rear+2)%MaxSize==Q->front;
1
2
3
4

方案2
增加一个变量上面的tag和size都是ok1的

小结

队列的链式实现

初始化

入队

出队

小结

双端队列