队列的程序、链式存储构造实现
Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".
题目作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetb...
题解作者:WildDuck
顺序存储构造的实现形式
struct MyCircularQueue{ int front; int tail; int Max_size; int* data;};typedef struct MyCircularQueue MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* head =(MyCircularQueue*)malloc(sizeof(struct MyCircularQueue)); head->data = (int*)malloc(sizeof(int)*(k+1)); head->front = 0; head->tail = 0; head->Max_size = k+1; return head;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) { if(obj->front == obj->tail) { return true; } else return false;}bool myCircularQueueIsFull(MyCircularQueue* obj) { if((obj->tail+1)%obj->Max_size == obj->front) { return true; } else return false;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value){ if(myCircularQueueIsFull(obj) == false) { obj->data[obj->tail] = value; obj->tail = (obj->tail+1)%obj->Max_size; return true; } else return false;}bool myCircularQueueDeQueue(MyCircularQueue* obj){ if(myCircularQueueIsEmpty(obj) == false) { obj->data[obj->front] = -1; obj->front = (obj->front+1)%obj->Max_size; return true; } else return false;}int myCircularQueueFront(MyCircularQueue* obj){ if(myCircularQueueIsEmpty(obj) == false) { return obj->data[obj->front]; } else return -1; }int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj) == false) { if(obj->tail-1 >= 0) { return obj->data[obj->tail-1]; } else return obj->data[obj->Max_size-1]; } else return -1;}void myCircularQueueFree(MyCircularQueue* 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);*/
链式存储构造实现
struct Linklist{ int data; struct Linklist* next;};typedef struct Linklist* Linklist_pointer;typedef struct { int Max_length; int current_length; Linklist_pointer front; Linklist_pointer rear;} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj) { if (obj->current_length == 0) { return true; } else return false;}bool myCircularQueueIsFull(MyCircularQueue* obj){ if (obj->current_length == obj->Max_length) { return true; } else return false;}MyCircularQueue* myCircularQueueCreate(int k){ MyCircularQueue* record = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); record->Max_length = k; record->current_length = 0; record->front = NULL; record->rear = NULL; Linklist_pointer head = (Linklist_pointer)malloc(sizeof(struct Linklist)); record->front = head; record->rear = head; return record;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value){ if(myCircularQueueIsFull(obj) == false) { Linklist_pointer new_elem = (Linklist_pointer)malloc(sizeof(struct Linklist)); new_elem -> data = value; new_elem -> next = NULL; obj->rear->next = new_elem; obj->rear = new_elem; obj->current_length = obj->current_length +1; return true; } return false;}bool myCircularQueueDeQueue(MyCircularQueue* obj){ if(myCircularQueueIsEmpty(obj) == false) { Linklist_pointer temp_pointer = obj->front->next; obj->front->next = obj->front->next->next; obj->current_length = obj->current_length -1; if(myCircularQueueIsEmpty(obj) == true)//删除过后队列为空，须要解决rear指针的指向 { obj->rear = obj->front; } free(temp_pointer); return true; } return false;}int myCircularQueueFront(MyCircularQueue* obj){ if(myCircularQueueIsEmpty(obj) == false) { return obj->front->next->data; } return -1;}int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj) == false) { return obj->rear->data; } return -1;}void myCircularQueueFree(MyCircularQueue* 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);*/