行业知识
【C语言】【LeetCode】循环队列
���录
(一)题目描述
(二)数据结构的选择
(三)函数接口的分析实现
正文开始:
(一)题目描述
题目链接:622. 设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
- MyCircularQueue(k): 构造器,设置队列长度为 k 。
- Front: 从队首获取元素。如果队列为空,返回 -1 。
- Rear: 获取队尾元素。如果队列为空,返回 -1 。
- enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
- deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
- isEmpty(): 检查循环队列是否为空。
- isFull(): 检查循环队列是否已满。
示例:
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3circularQueue.enQueue(1); // 返回 truecircularQueue.enQueue(2); // 返回 truecircularQueue.enQueue(3); // 返回 truecircularQueue.enQueue(4); // 返回 false,队列已满circularQueue.Rear(); // 返回 3circularQueue.isFull(); // 返回 truecircularQueue.deQueue(); // 返回 truecircularQueue.enQueue(4); // 返回 truecircularQueue.Rear(); // 返回 4
提示:
- 所有的值都在 0 至 1000 的范围内;
- 操作数将在 1 至 1000 的范围内;
- 请不要使用内置的队列库。
(二)数据结构的选择
在C语言中,实现队列的数据结构可以选择使用数组或链表,具体选择哪种数据结构取决于应用的需求和对性能的要求。
-
数组:使用数组实现队列的优势是简单和高效。可以使用一个固定大小的数组来表示队列,并使用两个指针front和rear来分别指示队列的前端和后端。入队操作可以通过将元素添加到rear指针指向的位置来实现,而出队操作可以通过将元素从front指针指向的位置移除来实现。数组的缺点是长度固定,一旦实现的队列满了,就不能再添加元素。
-
链表:使用链表实现队列的优势是可以动态地调整队列的大小,没有固定的长度限制。可以使用一个指针来表示链表的头部,并使用另一个指针来表示链表的尾部。入队操作可以通过在链表的尾部添加节点来实现,而出队操作可以通过删除链表的头部节点来实现。链表的缺点是相对于数组来说,操作稍微复杂一些,需要维护指针的指向关系。
综上所述,如果对队列的长度有明确的限制,可以选择使用数组实现队列。如果队列的长度不确定或需要频繁地进行插入和删除操作,可以选择使用链表实现队列。
在循环队列的题目要求中,指定了队列的数据个数为K,因此本次实现队列采用数组的方式实现;通过定义一个结构体来方便对循环队列的维护:
typedef struct { int* a;//动态数组 int k;//队列大小 int front;//队头指针,指向队头数据 int rear;//队尾指针,指向队尾数据的下一个位置} MyCircularQueue;如果rear指向的是队尾元素,那么数据个数为0和数据个数为1的情况无法区分,仔细想一想,这两种情况都是front和rear指针指向队首(数组下标为0的位置);
于是,我们可以通过多创建1个位置,让rear指向队尾元素的下一个位置——开辟k+1个位置,满足了存储k个数据的要求,又可以将数据个数为0和数据个数为1的情况区分开。
一般认为:rear + 1 == front时,表示队列满了,但是当rear指向队尾时,rear + 1 就跑到队列外面了,为了解决这一问题,我们通过取模实现;
//obj为实例化的对象 (obj->rear+1)%(obj->k+1)==obj->front
得出结论:F和R的下标相同时,表示队列是空的。
(三)函数接口的分析实现
(1) MyCircularQueue(k): 构造器,设置队列长度为 k。
MyCircularQueue* myCircularQueueCreate(int k) { //申请并初始化环形链表 MyCircularQueue* que = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); que->a = (int*)malloc(sizeof(int)*(k+1));//多开辟一个空间 que->front = 0;//指向队列头部 que->rear = 0;//指向队列尾部的下一个元素 que->k = k; return que;}(2) isEmpty(): 检查循环队列是否为空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->rear;}(3) isFull(): 检查循环队列是否已满。
bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear+1)%(obj->k+1)==obj->front;}(4) enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj))//满了,返回假 { return false; } //没有满,插入 obj->a[obj->rear++] = value; obj->rear %= (obj->k+1); return true;}(5) deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj))//空了,返回假 { return false; } obj->front++; if(obj->front == obj->k+1) obj->front = 0; return true;//没有空,出数据}(6) Front: 从队首获取元素。如果队列为空,返回 -1 。
int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[obj->front];}(7)Rear: 获取队尾元素。如果队列为空,返回 -1 。
int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[(obj->rear-1 + obj->k+1) % (obj->k+1)];}(8)C语言没有析构函数,需要手动释放循环队列
void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj);}完~
未经作者同意禁止转载
-
上一篇:域名后缀邮箱怎么注册的
下一篇:神武新服务器怎么升级?