事务所网站建设,如何取消网站备案,网站广告位设计,php做简单网站例子前言: 队列是一种具有先进先出特性的结构,但是当数据出队列以后,前面的空间就无法再次利用了,循环队列就可以解决这个问题
一:概念及结构:
1.循环队列概念 循环队列是一种线性数据结构#xff0c;其操作表现基于 FIFO#xff08;先进先出#xff09;原则并且队尾被连接在队…前言: 队列是一种具有先进先出特性的结构,但是当数据出队列以后,前面的空间就无法再次利用了,循环队列就可以解决这个问题
一:概念及结构:
1.循环队列概念 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环.
2.循环队列结构 循环队列可以使用数组实现也可以使用链表实现,但是还是建议使用数组实现.另外在给数组开辟空间时,要比队列实际长度多一个,如果开辟空间和队列存储数据的长度一样的话,在判断队列为空和队列为满时,两者都为 frontrear 会出现一样的情况导致无法判断,如 所以必须多开辟一个空间,这个空间不存储数据,这样就可以区分出两种情况 结构定义: front用于维护队头,指向队头元素位置,back用于维护队尾,总是指向队尾元素的下一个位置,k表示队列实际存数据的长度
ps:循环队列的长度是固定的
typedef struct {int *a;int front; int back;int k; //队列大小
} MyCircularQueue;
二:功能实现
1.入队: 首先要判断队列是否已满再进行入队的操作入队操作需要考虑索引循环的问题当索引越界需要让它变成最小值 如果入队是这种情况,直接在队尾处插入数据,back即可 但是如果碰到这种情况,back就不能简单加一就完事了了,还需要将back重新指向数组刚开始的空间,不然就体现不出循环的特点了 所以在队尾插入数据back后,进行 back(back)%(k1) 就可以使back重新指向数组起始位置(这里要注意的是,我定义的k是队列不带多开辟的那一个空间的长度)
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//入队前先判断是否还有空间return false;obj-a[obj-back]value;obj-back;obj-back%(obj-k1);return true;
}
2.出队: 首先判断队列是否为空,在进行出队操作,出队也需要考虑front的索引问题
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;obj-front;obj-front%(obj-k1);return true;
}
3.取队头元素 front指向的就是队头元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj-a[obj-front];
}
4.取队尾元素 由于back始终指向队尾的下一个元素,在一般情况下直接返回back-1所指向的元素即可,但是有一种特殊情况,如果此时back指向的是数组起始位置的话,访问back-1所指向的元素就会越界,所以这里也涉及循环的问题 方法一: 把特殊情况分离出来
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;if(obj-back0)return obj-a[obj-k];elsereturn obj-a[obj-back-1];
}
方法二: 两种情况统一处理
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj-a[(obj-back-1obj-k1)%(obj-k1)];
}
5.判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-frontobj-back;
}6.判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-back1)%(obj-k1)obj-front;
}
7.销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);obj-frontobj-back0;obj-k0;
}
8.求队列当前元素个数
当back在front之后时,back-front就可获得当前队列元素个数,但是当back在front前面时,back(k1)
可以让back指向不处理循环问题本身应该指向的位置
int myCircularQueueSize(MyCircularQueue* obj) {return (obj-back(k1)-obj-front)%(k1);
}
