怎么把网站排名优化,网站软件免费下载大全,工商咨询服务,app个人主页设计环形队列是一种线性数据结构#xff0c;其操作表现基于 FIFO#xff08;先进先出#xff09;原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 环形队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里#xff0c;一旦一个队列…环形队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 环形队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。
思路 在环形队列中队列为空时队头队尾指向同一个位置。当队列不为空时队头指向插入的第一个数据队尾指向最后一个数据的下一个位置。当tail1等于front时说明环形队列已满。
注意 环形队列的队尾不能像常规队列中队尾一样指向最后一个数据如果这样的话我们将不能区别环形队列的状态是空还是满因为此时队头和队尾都指向同一个位置。这就意味着我们必须留出一个空间这个空间不能存放数据这样我们才能很好的区别环形队列的状态是空还是满。 我们如果用一个数组来实现这个环形队列的话上面这三种状态就对应于以下三种状态 可以看出此时这个数组和环形完全扯不上关系这其实很简单我们只需注意判断两个地方 1.当指针指向整个数组的后方的时候让该指针重新指向数组的第一个元素。 2.当指针指向整个数组的前方的时候让该指针直接指向数组最后一个有效元素的后面。
这样就使得该数组在逻辑上是“环形”的了。
代码
// 设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
#include stdbool.h
#include stdlib.h
// 循环队列的结构使用数组来存储队头队尾的下标一个存储数据的数组。K表示队列长度
typedef struct
{int *queue;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue *myCircularQueueCreate(int k) {// 数组大小要开辟k1 预留一个空的空间以方便判断空和满的两种情况MyCircularQueue *obj (MyCircularQueue *) malloc(sizeof(MyCircularQueue));obj-queue (int *) malloc(sizeof(int) * (k 1));obj-front 0;obj-rear 0;obj-k k;return obj;
}// 队列判空front rear
bool myCircularQueueIsEmpty(MyCircularQueue *obj) {assert(obj);// 判空的条件是front和rear都为0return obj-front obj-rear;
}// 队列判满 (rear1)%(k1)front
bool myCircularQueueIsFull(MyCircularQueue *obj) {assert(obj);// 判满的条件是队列满了rear指向了最后一个空的数组1需要回到front的位置也就是(rear1)%(k1)frontreturn ((obj-rear 1) % (obj-k 1)) obj-front;
}//求有效长度(rear-frontk1)%(k1)
int myCircularQueueLength(MyCircularQueue *obj) {assert(obj);if (myCircularQueueIsEmpty(obj))return 0;return (obj-rear - obj-front obj-k 1) % (obj-k 1);
}bool myCircularQueueEnQueue(MyCircularQueue *obj, int value) {assert(obj);// 进队列 如果队列满了就无法进队列返回falseif (myCircularQueueIsFull(obj))return false;obj-queue[obj-rear] value;// rear的值溢出需要重新设置obj-rear % (obj-k 1);/* 也可以这么写if (obj-rear obj-k)obj-rear 0;*/return true;
}bool myCircularQueueDeQueue(MyCircularQueue *obj) {assert(obj);if (myCircularQueueIsEmpty(obj))return false;obj-front;// front溢出重新设置obj-front % (obj-k 1);/* 也可以这么写if (obj-front obj-k)obj-front 0;*/return true;
}int myCircularQueueFront(MyCircularQueue *obj) {assert(obj);if (myCircularQueueIsEmpty(obj))return -1;return obj-queue[obj-front];
}int myCircularQueueRear(MyCircularQueue *obj) {assert(obj);if (myCircularQueueIsEmpty(obj))return -1;// 如果rear 0 说明rear在最后的位置 也就是k的位置if (obj-rear 0)return obj-queue[obj-k];elsereturn obj-queue[obj-rear - 1];
}void myCircularQueueFree(MyCircularQueue *obj) {free(obj-queue);free(obj);
}
