网站建设费用多少,网络安全设计报告,wordpress企业中文模板下载地址,新月直播大全免费下载手机版实现循环队列最难的地方就在于如何判空和判满#xff0c;只要解决了这两点循环队列的设计就没有问题。接下来我们将会使用数组来实现循环队列。
接下来#xff0c;为了模拟实现一个容量为4的循环队列#xff0c;我们创建一个容量为4 1 的数组。
接下来我们将会对这个数组…实现循环队列最难的地方就在于如何判空和判满只要解决了这两点循环队列的设计就没有问题。接下来我们将会使用数组来实现循环队列。
接下来为了模拟实现一个容量为4的循环队列我们创建一个容量为4 1 的数组。
接下来我们将会对这个数组进行增删
下图是对于这个循环进行插值其中h代表headt代表tail。h代表循环列表的第一个元素t代表循环列表的末尾元素的下一个。0代表空的还未利用的空间。
当t走到末尾时再加一将会跳转到数组的头部以此实现逻辑上的循环。
添加元素 删除元素 继续添加元素 继续删除元素 继续添加元素 通过这些图我们可以清晰地看到当ht的时候循环列表为空。当t1 h时循环列表为满。
熟悉了方法后实现它就不难了。接下来我将会提供代码我将会写上必要的注释方便理解。
头文件
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int QueueData;
typedef struct MyCircularQueue
{QueueData* a;int k;int head;int tail;
} MyCircularQueue;// 这个函数用于创建一个循环队列。参数 k 表示队列的容量。
// 返回值是一个指向循环队列对象的指针。
MyCircularQueue* myCircularQueueCreate(int k);// 这个函数用于向循环队列中添加一个元素。
// 参数 obj 是指向循环队列对象的指针value 是要添加的元素的值。
// 如果成功添加元素则返回 true如果队列已满则返回 false。
bool myCircularQueueEnQueue(MyCircularQueue* obj, QueueData value);// 这个函数用于从循环队列中移除一个元素。
// 参数 obj 是指向循环队列对象的指针。
// 如果成功移除元素则返回 true
// 如果队列为空则返回 false。
bool myCircularQueueDeQueue(MyCircularQueue* obj);// 这个函数用于获取循环队列的队首元素。
// 参数 obj 是指向循环队列对象的指针。返回队首元素的值。
int myCircularQueueFront(MyCircularQueue* obj);// 这个函数用于获取循环队列的队尾元素。
// 参数 obj 是指向循环队列对象的指针。返回队尾元素的值。
int myCircularQueueRear(MyCircularQueue* obj);// 这个函数用于检查循环队列是否为空。
// 参数 obj 是指向循环队列对象的指针。
// 如果队列为空则返回 true否则返回 false。
bool myCircularQueueIsEmpty(MyCircularQueue* obj);// 这个函数用于检查循环队列是否已满。
// 参数 obj 是指向循环队列对象的指针。
// 如果队列已满则返回 true否则返回 false。
bool myCircularQueueIsFull(MyCircularQueue* obj);// 这个函数用于释放循环队列对象所占用的内存。
// 参数 obj 是指向循环队列对象的指针。
// 在调用该函数后指向循环队列对象的指针将不再有效。
void myCircularQueueFree(MyCircularQueue* obj);
函数的实现
#include Cycle_Queue.hMyCircularQueue* myCircularQueueCreate(int k)
{assert(k 0);MyCircularQueue* ret (MyCircularQueue*)malloc(sizeof(MyCircularQueue));QueueData* arr (QueueData*)malloc(sizeof(QueueData) * (k 1));if (ret NULL || arr NULL){perror(malloc faile);exit(-1);}ret-a arr;ret-k k;ret-head ret-tail 0;return ret;
}void myCircularQueueFree(MyCircularQueue* obj)
{assert(obj);free(obj-a);obj-a NULL;obj-k 0;free(obj);
}int myCircularQueueFront(MyCircularQueue* obj)
{assert(obj);if (myCircularQueueIsEmpty(obj))return -1;return obj-a[obj-head];
}int myCircularQueueRear(MyCircularQueue* obj)
{assert(obj);if (myCircularQueueIsEmpty(obj))return -1;// 值得注意的是tail指向的是队列末尾元素的下一个所以你需要让他向前走完一圈后再后退一步才能得到末尾元素。// 也即(obj-tail obj-k) % (obj-k 1)其中% (obj-k 1)是为了保证tail的值可以再某个区间里以实现循环队列。return obj-a[(obj-tail obj-k 1 - 1) % (obj-k 1)];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{assert(obj);return obj-head obj-tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj)
{assert(obj);// 当tail再往前走一步就碰到head了就说明此时的队列已经满了。return obj-head (obj-tail 1) % (obj-k 1);
}bool myCircularQueueEnQueue(MyCircularQueue* obj, QueueData value)
{assert(obj);if (myCircularQueueIsFull(obj))return false;obj-a[obj-tail] value;obj-tail (obj-tail 1) % (obj-k 1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)
{assert(obj);if (myCircularQueueIsEmpty(obj))return false;obj-head (obj-head 1) % (obj-k 1);return true;
}
