题目链接
622. 设计循环队列 - 力扣（LeetCode） (leetcode-cn.com)
题目简介
思路
开一个数组，空间为k+1(留空)(因为如果不给k+1个空间，当front==tail会让人疑惑
到底是为0个数据，还是数据满了，给了之后为0就是相等，满了会隔一个空间)，然后转。
// #define _CRT_SECURE_NO_WARNINGS 1 // #include<stdio.h> // #include<stdlib.h> // #include<assert.h> // #include<stdbool.h> // typedef int QDataType; // // 链式结构：表示队列 // typedef struct QListNode // { // struct QListNode* next; // QDataType data; // }QNode; // // 队列的结构 // typedef struct Queue // { // QNode* front; // QNode* tail; // }Queue; // // 初始化队列 // void QueueInit(Queue* q); // // 队尾入队列 // void QueuePush(Queue* q, QDataType data); // // 队头出队列 // void QueuePop(Queue* q); // // 获取队列头部元素 // QDataType QueueFront(Queue* q); // // 获取队列队尾元素 // QDataType QueueBack(Queue* q); // // 获取队列中有效元素个数 // int QueueSize(Queue* q); // // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 // int QueueEmpty(Queue* q); // // 销毁队列 // void QueueDestory(Queue* pq); // #define _CRT_SECURE_NO_WARNINGS 1 // // 初始化队列 // void QueueInit(Queue* q) // { // assert(q); // q->front = NULL; // q->tail = NULL; // } // // 队尾入队列 // void QueuePush(Queue* q, QDataType data) // { // assert(q); // QNode* newnode = (QNode*)malloc(sizeof(QNode)); // if (newnode == NULL) // { // perror("QueuePush:"); // exit(-1); // } // newnode->data = data; // newnode->next = NULL; // if (q->front ==NULL && q->tail == NULL) // { // q->front = q->tail = newnode; // } // else // { // q->tail->next = newnode; // q->tail = newnode; // } // } // int QueueSize(Queue* q) // { // assert(q); // QNode* cur=q->front; // int count=0; // while(cur!=NULL) // { // count++; // cur=cur->next; // } // return count; // } // // 队头出队列 // void QueuePop(Queue* q) // { // assert(q); // assert(q->front && q->tail); // QNode* next = q->front->next; // if (next != NULL) // { // free(q->front); // q->front = NULL; // q->front = next; // } // else // { // free(q->front); // q->front = NULL; // q->tail = NULL; // } // } // // 获取队列头部元素 // QDataType QueueFront(Queue* q) // { // assert(q); // assert(q->front != NULL); // return q->front->data; // } // // 获取队列队尾元素 // QDataType QueueBack(Queue* q) // { // assert(q); // assert(q->tail != NULL); // return q->tail->data; // } // // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 // int QueueEmpty(Queue* q) // { // assert(q); // return q->front ==NULL && q->tail == NULL; // } 上面是自己的队列 有问题应该 / #pragma once #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> typedef int QDataType; //typedef struct QueueNode //{ // QDataType data; // struct QueueNode* next; //}QNode, *PNode; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; //size_t size; }Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); bool QueueEmpty(Queue* pq); size_t QueueSize(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); assert(newnode); newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { assert(pq->head == NULL); pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } void QueuePop(Queue* pq) { assert(pq); assert(pq->head && pq->tail); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } } bool QueueEmpty(Queue* pq) { assert(pq); //return pq->head == NULL && pq->tail == NULL; return pq->head == NULL; } size_t QueueSize(Queue* pq) { assert(pq); QNode* cur = pq->head; size_t size = 0; while (cur) { size++; cur = cur->next; } return size; } QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->tail); return pq->tail->data; } // // 销毁队列 // void QueueDestory(Queue* q) // { // assert(q); // assert(q->front == NULL); // QNode* cur = q->front; // QNode* next = cur->next; // while (next != NULL) // { // free(cur); // cur = NULL; // cur = next; // next = next->next; // } // free(cur); // cur = NULL; // } // void QueueDestory(Queue* pq) // { // assert(pq); // QNode* cur = pq->front; // while (cur) // { // QNode* next = cur->next; // free(cur); // cur = next; // } // } /// //以上是栈 //思路:开一个数组，空间为k+1(留空)(因为如果不给k+1个空间，当front==tail会让人疑惑 //到底是为0个数据，还是数据满了，给了之后为0就是相等，满了会隔一个空间)，然后转。 // typedef struct { // int* a; // int front; // int tail; // int k; // } MyCircularQueue; // bool myCircularQueueIsFull(MyCircularQueue* obj); // bool myCircularQueueIsEmpty(MyCircularQueue* obj); // //1 // MyCircularQueue* myCircularQueueCreate(int k) { // MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); // assert(obj); // obj->a=(int*)malloc(sizeof(int)*(k+1)); // assert(obj->a); // obj->front=0; // obj->tail=0; // obj->k=k; // return obj; // } // bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { // assert(obj); // if(myCircularQueueIsFull(obj)) // return false; // obj->a[obj->tail]=value; // if(obj->tail==obj->k) // { // obj->tail=0; // } // else // { // obj->tail++; // } // return true; // // if(obj->front==obj->tail) // // { // // obj->a[obj->tail]=value; // // obj->tail++; // // } // // else // // { // // obj->a[obj->tail]=value; // // if(obj->tail==obj->k) // // { // // obj->tail=0; // // } // // else // // { // // obj->tail++; // // } // // } // // return true; // } // bool myCircularQueueDeQueue(MyCircularQueue* obj) { // assert(obj); // if(myCircularQueueIsFull(obj)) // return false; // // if((obj->front+1==obj->tail)||(obj->front-obj->tail==obj->k)) // // { // // return false; // // } // if(obj->front==obj->k) // { // obj->front=0; // } // else // { // obj->front++; // } // return true; // // if(obj->front<obj->k) // // { // // obj->front++; // // } // // else // // { // // obj->front=0; // // } // // return true; // } // int myCircularQueueFront(MyCircularQueue* obj) { // assert(obj); // if(myCircularQueueIsFull(obj)) // return -1; // return obj->a[obj->front]; // // if(obj->front==obj->tail) // // { // // return -1; // // } // // else // // { // // return obj->a[obj->front]; // // } // } // int myCircularQueueRear(MyCircularQueue* obj) { // assert(obj); // if(myCircularQueueIsFull(obj)) // return -1; // if(obj->tail==0) // { // return obj->a[obj->k]; // } // else // { // return obj->a[obj->tail-1]; // } // // if(obj->front==obj->tail) // // { // // return -1; // // } // // else // // { // // return obj->a[obj->tail]; // // } // } // bool myCircularQueueIsEmpty(MyCircularQueue* obj) { // //assert(obj); // return obj->front==obj->tail; // } // //1 // bool myCircularQueueIsFull(MyCircularQueue* obj) { // //assert(obj); // //if((obj->tail+1==obj->front)||(obj->front-obj->tail==0)) // if(obj->tail==obj->k && obj->front==0) // { // return true; // } // else // { // return obj->tail+1==obj->front; // //return false; // } // } // void myCircularQueueFree(MyCircularQueue* obj) { // assert(obj); // free(obj->a); // free(obj); // } /// typedef struct { int* queue; int front; int rear; int k } MyCircularQueue; /** Initialize your data structure here. Set the size of the queue to be k. */ //创建一个可以存放k个元素的循环队列，实际申请的空间为k + 1 MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* pcq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); pcq->queue = (int*)malloc(sizeof(int)*(k+1)); pcq->front = 0; pcq->rear = 0; pcq->k = k; return pcq; } /** Insert an element into the circular queue. Return true if the operation is successful. */ bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { //判满 if((obj->rear+1)%(obj->k+1) == obj->front) { return false; } //队尾入队 obj->queue[obj->rear++] = value; //如果队尾越界，更新为最小值 if(obj->rear == obj->k+1) obj->rear = 0; return true; } /** Delete an element from the circular queue. Return true if the operation is successful. */ bool myCircularQueueDeQueue(MyCircularQueue* obj) { //判空 if(obj->front == obj->rear) return false; //队头出队 ++obj->front; //如果队头越界，更新为最小值 if(obj->front == obj->k+1) obj->front = 0; return true; } /** Get the front item from the queue. */ int myCircularQueueFront(MyCircularQueue* obj) { if(obj->front == obj->rear) return -1; else return obj->queue[obj->front]; } /** Get the last item from the queue. */ int myCircularQueueRear(MyCircularQueue* obj) { if(obj->front == obj->rear) return -1; //队尾元素再rear索引的前一个位置，如果rear为0， //则队尾元素在数组的最后一个位置 if(obj->rear == 0) return obj->queue[obj->k]; else return obj->queue[obj->rear-1]; } /** Checks whether the circular queue is empty or not. */ bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->rear; } /** Checks whether the circular queue is full or not. */ bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear+1)%(obj->k+1) == obj->front; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->queue); free(obj); } /** * Your MyCircularQueue struct will be instantiated and called as such: * MyCircularQueue* obj = myCircularQueueCreate(k); * bool param_1 = myCircularQueueEnQueue(obj, value); * bool param_2 = myCircularQueueDeQueue(obj); * int param_3 = myCircularQueueFront(obj); * int param_4 = myCircularQueueRear(obj); * bool param_5 = myCircularQueueIsEmpty(obj); * bool param_6 = myCircularQueueIsFull(obj); * myCircularQueueFree(obj); */
最后的最后，创作不易，希望读者三连支持💖
赠人玫瑰，手有余香💖
