力扣（LeetCode) ——622. 设计循环队列（C语言）

题目：622. 设计循环队列

示例1：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

解题思路：

根据题目要求设计一个循环队列，需要满足以下要求：

最终代码1：

通过额外开辟一个空间，解决空和满的冲突问题。

typedef struct {
	int* a;
	int head;//指向头
	int tail;//指向尾的下一个
	int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

	obj->a = (int*)malloc(sizeof(int) * (k + 1));
	obj->head = 0;
	obj->tail = 0;
	obj->k = k;
	return obj;
}
//是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->head == obj->tail;
}
//是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return (obj->tail + 1) % (obj->k + 1) == obj->head;
}
//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	if (myCircularQueueIsFull(obj))
	{
		return false;
	}
	obj->a[obj->tail] = value;
	obj->tail++;
	obj->tail = (obj->tail) % (obj->k + 1);
	return true;

}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return false;
	}
	obj->head++;
	obj->head = (obj->head) % (obj->k + 1);
	return true;
}
//不为空取首元素
int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	return obj->a[obj->head];
}
//不为空取尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	return obj->a[(obj->tail + obj->k) % (obj->k + 1)];
}

void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	free(obj);
}

最终代码2：

通过增加一个size来判断队列是否为空或满。

typedef struct {
    int* a;
    int phead;
    int ptail;
    int k;
    int size;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int)*k);
    obj->phead = 0;
    obj->ptail = 0;
    obj->k = k;
    obj->size = 0;
    return obj;
}
//是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->size == 0;

}
//是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->size == obj->k;
}

//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        if(myCircularQueueIsEmpty(obj))
        {
            obj->a[obj->phead] = value;
        }
        obj->a[obj->ptail] = value;
        obj->ptail++;
        obj->ptail %= obj->k;
        obj->size++;
        
        return true;
    }
}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->phead = (obj->phead+obj->k+1)%obj->k;
        obj->size--;
        return true;
    }
}
//取首元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[obj->phead];
}
//取尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return obj->a[(obj->ptail+obj->k-1)%obj->k];
    }
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}