[数据结构与算法][leetcode]C语言用数组或链表实现循环队列

实现循环队列，我们需要实现的操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满

一、数组的方式实现循环队列

typedef struct {
	int *a;    //定义动态数组存储数据
	int front; 
	int tail;
	int capacity;//数据的存储容量
} MyCircularQueue;

//构造队列
MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue*cp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	cp->a = (int*)malloc(sizeof(int)*(1 + k));//多开一个空间，方便判空和判满
	cp->front = cp->tail = 0;
	cp->capacity = k;
	return cp;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//写IsEmpty、IsFull函数声明，这样下列函数可以使用
bool myCircularQueueIsFull(MyCircularQueue* obj);
//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	if (myCircularQueueIsFull(obj))//判满，满了就返false
		return false;

	obj->a[obj->tail] = value;//赋值value
	obj->tail++;
	obj->tail %= (obj->capacity + 1);//保证tail在有效范围内
	return true;
}
//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))//判满，满了就返false
		return false;

	obj->front++;
	obj->front %= (obj->capacity + 1);//保证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;
	//方法1
	//int i = (obj->tail + obj->capacity) % (obj->capacity + 1);
	//return obj->a[i];
	//方法2
	 if(obj->tail==0)
	 return obj->a[obj->capacity];
	else
	 return obj->a[obj->tail-1];
}
// 检查循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->front == obj->tail;
}
//检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return (obj->tail + 1) % (obj->capacity + 1) == obj->front;
}

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

?二、链表的方式实现循环队列

//链表实现
typedef struct QNode
{
    int val;
    struct QNode *next;
}QNode;
typedef struct {
    QNode*front;
    QNode*tail;
    int capacity;//最大存储数
    int n;//实际存储数
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*cp=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cp->capacity=k;
    cp->front=cp->tail=NULL;
    cp->n=0;
    return cp;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if( myCircularQueueIsFull(obj))
    return false;
        QNode *N = (QNode*)malloc(sizeof(QNode));
    N->next = NULL;
    N->val = value;

    if(obj->n==0)
    {
         obj->front=N;
         obj->tail=N;
    }
  
   else
   {
    obj->tail->next=N;
    obj->tail=obj->tail->next;
   }

   obj->n++;
   return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
		return false;

    obj->front=obj->front->next;
        obj->n--;
        return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
		return -1;

        return obj->front->val;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
		return -1;

        return obj->tail->val;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->n==0)
    return true;
    else
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if(obj->capacity==obj->n)
    return true;
    else
    return false;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
		return ;
    QNode*head=obj->front;
   QNode*next=NULL;
    while(head->next)
    {
        next=head->next;
        free(head);
        head=next;
        
    }
    free(obj);
}