用C语言数组设计循环队列
解释:
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
来源:力扣(LeetCode)
链接:622. 设计循环队列 - 力扣(LeetCode) (leetcode-cn.com)
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:
此题可以用数组,也可以用链表的方式解答,下面用数组的方式理清一下思路;
1.数组要存首、尾下标,因为是链式结构 还要注意下标的处理方式;因为尾下标走到尽头时要跳回数组的头,每次都要处理好下标的表示;
2.在判断数据是空,还是满时,因为在一开始没有一个数据时首、尾下标都指向第一个地址,当添加数据时,尾下标会往后移,所以空间要多开辟一个,只为了能好判断数据满的时候,像,两个下标都指向一个地址,说明是首,如果满也是指到一个地址,这种表示办法有瑕疵,所以多开辟一个空间当尾下标往后一个就是首下标时就说明环形队列数据已满;
3.处理下标方面,有时候会从最后跳到最前面;(下标=下标数%总容量)总容量开辟的数组容量;
代码解析:
typedef struct {
int *a;//数组首地址
int front;//队首下标
int tail;//队尾下标
int k;//循环队列元素个数
} MyCircularQueue;
要先建立循环队列并初始化
MyCircularQueue* myCircularQueueCreate(int k) {
//先开辟一个结构体变量;
MyCircularQueue* cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//开辟数组为存循环队列数据
cq->a=(int*)malloc(sizeof(int)*(k+1));//多开辟一个元素空间;为了检测数据是否满
cq->front=cq->tail=0;
cq->k=k;
return cq;
}
检测函数不能少,一个检测数据是否为空,一个检测数据是否满;
//检查数据是否为空,为空就返回真
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->tail;
}
//检查数据是否满了,满了就返回真
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail+1)%(obj->k+1)==obj->front;
}
向队列内插入一个元素,如果成功返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//先检查数据是否满了,如果满了就是插入失败,返回假;
if(myCircularQueueIsFull(obj))
return false;
obj->a[obj->tail]=value;
obj->tail++;
obj->tail%=(obj->k+1);
return true;
}
向队列删除一个元素,删除成功返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//如果队列为空,返回假;
if(myCircularQueueIsEmpty(obj))
return false;
obj->front++;
obj->front%=(obj->k+1);
return true;
}
取队首元素,如果为空返回-1;返回队首直接访问下标;
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->front];
}
取队尾元素,如果为空返回-1;要确定队尾下标;
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
int i=(obj->tail==0)?obj->k:obj->tail-1;
//法二:int i=(obj->tail+obj->k)%(obj->k+1);
return obj->a[i];
}
最后释放空间;要一层一层由内往外依次释放;
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}