循环队列
从上图我们可以总结出循环队列工作的要点
- 队列空的条件:head == tail
- 队列满的条件:(tail + 1) % maxlen == head
- 约定数组最多存放maxlen - 1个元素
- 当队列为空时,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;
}
};