Loading... ## 循环队列 ![循环队列工作原理图][1] ### 从上图我们可以总结出循环队列工作的要点 1. 队列空的条件：head == tail 2. 队列满的条件：(tail + 1) % maxlen == head 3. 约定数组最多存放maxlen - 1个元素 4. 当队列为空时，head和tail都置为-1，重新从0开始存放元素 ### C++实现循环队列 class MyCircularQueue { private: vector<int> myqueue; int maxlen; int head; int tail; public: /** Initialize your data structure here. Set the size of the queue to be k. */ MyCircularQueue(int k) { myqueue.resize(k+1); maxlen = k; head = -1; // head和tail都初始化为-1当元素入队时再从0开始 tail = -1; } /** Insert an element into the circular queue. Return true if the operation is successful. */ bool enQueue(int value) { if(!isFull()){ if(isEmpty()) head = 0; tail = (tail + 1) % maxlen; myqueue[tail] = value; return true; } return false; } /** Delete an element from the circular queue. Return true if the operation is successful. */ bool deQueue() { if(isEmpty()) return false; else{ if(head == tail){ head = -1; // 当队列为空时，head和tail都置为-1，再有元素入队重新从0开始 tail = -1; return true; } head = (head + 1) % maxlen; return true; } } /** Get the front item from the queue. */ int Front() { if(!isEmpty()) return myqueue[head]; else return -1; } /** Get the last item from the queue. */ int Rear() { if(!isEmpty()){ return myqueue[tail]; } return -1; } /** Checks whether the circular queue is empty or not. */ bool isEmpty() { if(head == -1) return true; else return false; } /** Checks whether the circular queue is full or not. */ bool isFull() { if((tail+1) % maxlen == head) return true; else return false; } }; [1]: http://kevinnan.org.cn/usr/uploads/2020/04/3943780676.png Last modification：June 28th, 2020 at 11:39 am © 允许规范转载