解决顺序表实现队列的假溢出的循环队列 |
您所在的位置：网站首页 › 循环队列算法思想解释 › 解决顺序表实现队列的假溢出的循环队列 |
|
循环队列的参考视频：https://www.bilibili.com/video/BV1nJ411V7bd?p=60 问题：什么是顺序队列的假溢出？从队首倒到队尾完全占用了分配的空间，是溢出。相反，队尾元素占用了分配的最后一个空间，队首元素还是占有的不是第一个分配的空间，相当于队列对外是满的，但是内部空间利用不充分，还有剩余，此时就称为假溢出。 解决假上溢的方法-引入循环队列把把队列首元素queue[front=0] 接在queue[MAXQSIZE-1]之后，若rear+1 == MAXQSIZE，则令rear=0； 解决办法：使用模运算（%） //插入元素： queue[rear] = x; rear = ( rear + 1 ) % MAXQSIZE; //删除元素： x = queue[front]; front = ( front + 1) % MAXQSIZE;相当于下表为0的元素的前驱变成了原队尾（MAXQSIZE-1）的后继。 遇到新问题判断队列空或满时，都是 front == rear 解决方案： 设置标志，以区别队空、队满另设一个变量，计算元素个数少利用一个空间（以下编码使用这种方式） 少用一个空间如何区别队满？队满判断条件：front ==（rear+1）% MAXQSIZE； 实现代码 /* * @Author: jinbo.ma * @Mail: [email protected] * @Date: 2021-05-04 09:39:21 * @LastEditTime: 2021-05-05 16:02:41 */ #include #include #define MAXQSIZE 6 int queue_length (int front, int rear) { return (rear - front + MAXQSIZE) % MAXQSIZE; } int entry_queue (int *q, int *front, int *rear, int data) { printf ("data=%d\n", data); //判断队满 if ( (*rear+1)%MAXQSIZE == *front ) { return 0; } q[*rear] = data; *rear = (*rear + 1) % MAXQSIZE; return 1; } int exit_queue (int * q, int *front, int *rear, int *data) { //判断队空 if (*front == *rear) { return 0; } *data = q[*front]; *front = (*front + 1) % MAXQSIZE; return 1; } /** * 顺序表-循环队列之实现 */ int main() { int queue[MAXQSIZE] = {0}, front = 0, rear = 0; int data; //空队出队操作 if ( exit_queue(queue, &front, &rear, &data) ) { printf("空队列出队成功这是不可能的事情！data=%d\n\n", data); } else { printf("空队列出队失败才是正常的, front=%d, rear=%d\n\n", front, rear); } printf("\n----------------------------------------------------------------\n"); //求空队列的长度 printf("queue length=%d\n", queue_length(front, rear) ); printf("\n----------------------------------------------------------------\n"); //试验真溢出 for (int i = 0; i |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |