环形队列

---

---

什么是环形队列

环形队列也是队列的一种数据结构, 也是在队头出队, 队尾入队;
只是环形队列的大小是确定的, 不能进行一个长度的增加, 当你把一个环形队列创建好之后, 它能存放的元素个数是确定的;
一般我们实现这个环形队列是通过一个连续的结构来实现的;
虽然环形队列在逻辑上是环形的, 但在物理上是一个定长的数组;
那如何在逻辑上形成一个环形的变化, 主要是在头尾指针当走到连续空间的末尾的时候, 它会做一个重置的操作

循环队列的实现

第一种实现

typedef struct {//第一种实现:int* _data;//第一个元素的位置: 队头位置int _front;//最后一个元素的下一个位置int _rear;int _k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {//多开一个元素的空间MyCircularQueue* mq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));mq->_data = (int*)malloc(sizeof(int) * (k + 1));mq->_front = mq->_rear = 0;mq->_k = k;return mq;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->_front == obj->_rear)return true;elsereturn false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if((obj->_rear + 1) % (obj->_k + 1) == obj->_front)return true;elsereturn false;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//判断队列是否已满if(myCircularQueueIsFull(obj))return false;obj->_data[obj->_rear++] = value;//判断队尾是否越界if(obj->_rear > obj->_k)obj->_rear = 0;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//判断队列是否为空if(myCircularQueueIsEmpty(obj))return false;//出队obj->_front++;//判断队头是否越界if(obj->_front > obj->_k)obj->_front = 0;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->_data[obj->_front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;//返回队尾rear的前一个位置的元素//判断rear是否为0;if(obj->_rear != 0)return obj->_data[obj->_rear - 1];elsereturn obj->_data[obj->_k];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->_data);free(obj);
}

第二种实现

typedef struct {//第一种实现:int* _data;//第一个元素的位置: 队头位置int _front;//最后一个元素的下一个位置int _rear;int _k;int _size;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {//多开一个元素的空间MyCircularQueue* mq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));mq->_data = (int*)malloc(sizeof(int) * k);mq->_front = mq->_rear = 0;mq->_k = k;mq->_size = 0;return mq;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->_size == 0)return true;elsereturn false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if(obj->_size == obj->_k)return true;elsereturn false;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//判断队列是否已满if(myCircularQueueIsFull(obj))return false;obj->_data[obj->_rear++] = value;//判断队尾是否越界if(obj->_rear >= obj->_k)obj->_rear = 0;++obj->_size;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//判断队列是否为空if(myCircularQueueIsEmpty(obj))return false;//出队obj->_front++;//判断队头是否越界if(obj->_front >= obj->_k)obj->_front = 0;--obj->_size;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->_data[obj->_front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;//返回队尾rear的前一个位置的元素//判断rear是否为0;if(obj->_rear != 0)return obj->_data[obj->_rear - 1];elsereturn obj->_data[obj->_k - 1];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->_data);free(obj);
}