寿光网站建设推广,竞价托管代运营多少钱,做网站用asp div代码,网站开发招标目录 1.什么是循环队列
2.循环队列的实现#xff08;两种方法#xff09;
第一种方法 数组法
1.源代码
2.源代码详解#xff01;#xff01;
1.创造队列空间和struct变量
2.队列判空
3.队列判满#xff08;重点#xff09;
4.队列的元素插入
5.队列的元素删除
…目录 1.什么是循环队列
2.循环队列的实现两种方法
第一种方法 数组法
1.源代码
2.源代码详解
1.创造队列空间和struct变量
2.队列判空
3.队列判满重点
4.队列的元素插入
5.队列的元素删除
6.队列的头元素
7.队列的尾元素重点
8.队列空间的释放
第二种方法 双向循环链表法
1.源代码
2.源代码详解 1.创造哨兵位 和 struct 变量
2. 队列判空和队列判满
3.元素插入
4.元素删除
5.头元素
6.尾元素
7.空间的释放
三关于这两种方法的差距
3.循环队列有什么用 1.什么是循环队列
首先关于循环队列你得先知道什么是队列详情可以去看看我的另一篇博客
数据结构 栈与队列详解-CSDN博客
这里简单的说一下队列就是字面意思你在银行排队你不是什么VIP只是普通人那你先排队那你就先得服务队列就是 你先插入的数字入队就得先放出出队。大致就是这个意思。
而循环队列呢他的原理也是队列但和队列不同的地方在于他的空间是固定的。在一个空间里进行重复的入队出队。 这是一张循环队列的大致图。 其中和队列一样有两个指针指向头和尾。添加实在尾针处加而删除就是将队首的元素删除。为什么循环呢就是在你的尾指针走到最后一格的时候就是总共有5个空间你的尾指针已经走到5并且已经插入数据你的队列就满了这时候循环队列已经不能插入数据只能删除数据。 删除数据就是把你的头指针的元素删除如果删除走到尾指针头和尾在一个位置了。 所以综上可以抽象出当你的头和尾指针走到一起的时候这时候队列是空。 但你的尾走到底 头元素的上一个那就说明你的队列已充满。 当队尾追到了队头那就是满当队头追到了队尾那就是空 2.循环队列的实现两种方法
第一种方法 数组法
数组法采用的是 多开辟一个空间用来做假溢出判断队列是否充满当然还有一种定size法大家可以讨论一下
1.源代码
typedef struct {int* a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-a (int*)malloc(sizeof(int) * (k 1));obj-k k;obj-front 0;obj-rear 0;return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-front obj-rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-rear 1) % (obj-k 1) obj-front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}obj-rear % obj-k 1;obj-a[obj-rear] value;obj-rear;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}obj-front % obj-k 1;obj-front;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj-a[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj-a[obj-rear - 1];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);obj-a NULL;free(obj);obj NULL;
}
2.源代码详解
1.创造队列空间和struct变量
typedef struct {int* a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-a (int*)malloc(sizeof(int) * (k 1));obj-k k;obj-front 0;obj-rear 0;return obj;
} 关于 匿名typedef struc 就是定义了一个类型名就叫做MyCircularQueue。 里面的元素第一个用来开辟空间第二个定义头指针第三个定义尾指针第4个就是空间的大小。这里的指针并不是真的指针而是对于一个数组来说的下标 关于 创造队列的空间首先既然他是一个结构体变量那得先给他开辟一个空间用来给里面的元素地址存储 第二因为你是要在一个数组里进行循环队列那你就得开辟一块数组的空间。k1是因为这里采用的是多开辟一格进行判满。 第三给结构体里的变量赋初始值。 2.队列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-front obj-rear;
}关于队列的判空就是两个队头和队尾指针如果重叠时两者应该是满了或者空了的关系所以两者的判断表达式不能相同所以下面的判满得想到另一个表达式才能保证队列不报错当队尾追到了队头那就是满当队头追到了队尾那就是空 3.队列判满重点
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-rear 1) % (obj-k 1) obj-front;
}这里关于队列的判满采用的是这一串表达式的原因是假设这时你开辟的有元素的空间是3那现在的K就是3但由于采用的是多开辟一格来判满的方法那就是代表了开辟了4个空间。 4个空间对应的下标为0 1 2 3.那为什么要改两个指针rear和k加一呢假设这时你的rear和front 都还在下标为 0 的位置如果你不给 rear 加一 那你得出的结果就是 0 % 4 0. 这样导致的后果就是和 上面判空的条件 是一样的 0 0.会导致插入操作错误会一直判满从而不能进行插入。 而如果你给 rear 和 k 都加一 就变成了 1 % 4 1.而这时 front 是 0的 就不会出现误判的情况。只有当你的 rear 走到你多开辟的那一块空间后才会出现判满的情况。这只是当 front 没变的情况下的讨论关于 front改变后的讨论你可以构思一下大致相同。 4.队列的元素插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}obj-rear % obj-k 1;obj-a[obj-rear] value;obj-rear;return true;
}队列的插入就是在rear的 下标初进行插入。首先你要进行判满是因为循环队列如果满了以后就不会在追加新的元素就很像游戏里的背包满了以后就不能获得物品。为什么要让rear % k1呢因为当你的元素走到最后一格的下一格这时候是越界访问的。因为是循环队列所以可以把他重新变到下标为 0 的位置。 我们的rear 的位置每次都会加1 所以每次是在rear 的位置插入数据。 5.队列的元素删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}obj-front;obj-front % obj-k 1;return true;
}元素删除首先如果你的队列为空那就删除不了了返回false。 如果不为空那front 即可并且和 rear 一样要 % k1是为了使队列变成循环。如果不这样就会越界访问并且与题意不符循环。 要先 的原因是如果你后 就会导致如果此时你的front已经处于最后一个位置 后就会导致取头元素时 越界。如果先 然后在%k1 这样在出了最后一格以后可以及时变回0 下标不会越界。 6.队列的头元素
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj-a[obj-front];
}返回头元素相较简单只要返回此时front 位置的元素即可。 7.队列的尾元素重点
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}//if (obj-rear 0)//{// return obj-a[obj-k];//}//else//{// return obj-a[obj-rear - 1];//}return obj-a[((obj-rear - 1) (obj-k 1)) % (obj-k 1)];
} 和头元素的不同点在于队尾元素不能直接取队尾的下标。 因为由前面的插入操作我们可以知道在rear位置插入数据后rear是要进行的此时在rear下标里是没有元素的队尾实际上是在rear 的前一个下标的位置。 但如果你只用 obj-a[obj-rear - 1] 来访问的话如果你的rear是先%k 1再是可以的但如果是先再%就不可以了你可以思考一下当rear 0的时候那你访问的就是obj-[-1] 那就是未知访问错误。有两种方法。 第一种判断当rear 0的时候你可以直接选择返回 最后一格 obj-k 的元素 rear 0时就返回 obj-rear - 1的下标的元素。 第二种直接判断不用 if elseobj-a[((obj-rear - 1) (obj-k 1)) % (obj-k 1)]。 这串表达式的意思就是因为我们是要返回 rear - 1下标位置的元素所以我们 rear - 1 而 加上 k 1的原因是 在 rear -1 的位置下你加 上这个循环队列的大小那你还是在原地的这里是为了防止特殊情况 rear -1 时rear -1 原本是想访问 队列最后一个空间的元素但等于 - 1访问不到所以 rear -1 加上 一个 k1,其实就是等于 k k % k 1 k。所以访问最后一个位置的元素。 8.队列空间的释放
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);obj-a NULL;free(obj);obj NULL;
}将开辟的空间释放即可但要先释放obj-a 处的空间。 第二种方法 双向循环链表法
1.源代码
typedef struct MyCircularQueue {struct MyCircularQueue* prev;struct MyCircularQueue* next;int val;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* phead (MyCircularQueue*)malloc(sizeof(MyCircularQueue));phead-next phead;phead-prev phead;phead-val -1;phead-k k;return phead;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if (obj-next obj){return true;}return false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {MyCircularQueue* cur obj-next;int size 1;while (cur ! obj){cur cur-next;size;}return size obj-k;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}MyCircularQueue* newnode (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (newnode NULL){perror(malloc failed);exit(-1);}newnode-val value;MyCircularQueue* prev obj-prev;newnode-prev prev;newnode-next obj;prev-next newnode;obj-prev newnode;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}MyCircularQueue* Next obj-next;obj-next Next-next;Next-next-prev obj;free(Next);Next NULL;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj-next-val;
}int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj-prev-val;
}void myCircularQueueFree(MyCircularQueue* obj) {MyCircularQueue* cur obj-next;while (cur ! obj){MyCircularQueue* del cur;cur cur-next;free(del);del NULL;}free(obj);obj NULL;
}
2.源代码详解 1.创造哨兵位 和 struct 变量
typedef struct MyCircularQueue {struct MyCircularQueue* prev;struct MyCircularQueue* next;int val;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* phead (MyCircularQueue*)malloc(sizeof(MyCircularQueue));phead-next phead;phead-prev phead;phead-val -1;phead-k k;return phead;
} 我们定义一个双链表的struct 结构。 然后再定义一个头结点并且将 变量赋值。 2. 队列判空和队列判满
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if (obj-next obj){return true;}return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {MyCircularQueue* cur obj-next;int size 0;while (cur ! obj){cur cur-next;size;}return size obj-k;
} 相较于 数组的循环队列双链表的判空判满就比较简单。空就是 只有一个哨兵位就是空。 满就是用一个size 遍历链表后如果size obj-k 就是满。size 必须从 0 开始。 因为不从0 开始 总体队列会少一个空间。 3.元素插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}MyCircularQueue* newnode (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (newnode NULL){perror(malloc failed);exit(-1);}newnode-val value;MyCircularQueue* prev obj-prev;newnode-prev prev;newnode-next obj;prev-next newnode;obj-prev newnode;return true;
}元素的插入就是双链表的尾插。 4.元素删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}MyCircularQueue* Next obj-next;obj-next Next-next;Next-next-prev obj;free(Next);Next NULL;return true;
}元素删除就是双链表的头删。 5.头元素
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj-next-val;
}返回 头元素 6.尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj-prev-val;
}返回尾元素 7.空间的释放
void myCircularQueueFree(MyCircularQueue* obj) {MyCircularQueue* cur obj-next;while (cur ! obj){MyCircularQueue* del cur;cur cur-next;free(del);del NULL;}free(obj);obj NULL;
}双链表的销毁。 三关于这两种方法的差距 首先在数组 方法中我们并没有采用循环来执行这样的时间复杂度是01而双向链表中有多处我们采用了while 循环所以时间复杂度是 on。 数组写法中 坑很多需要很多思考但是总体代码量是偏少的。 而链表虽然简单明了但代码量是稍微多一点。需要细心检查。 3.循环队列有什么用 应用场景广泛由于其高效的插入和删除操作、空间利用率高以及能够动态调整队列大小的特性循环队列在许多领域都有广泛的应用如操作系统中的任务调度、通信协议中的数据包处理、线程池中的线程管理等。所以循环队列是比较重要的
