在leetCode上学习数据结构时发现circulation Queue。从头理下思路，在此记录。
有时候我们在开发中可能会遇到一个恒定长度得队列，但队列中的数据确可能存在变化。（可以简单理解为一个定长、按时间顺序缓存的队列）
1、Create Circulation Queue Step：
能判断是否为空，或者存满，在未满时可以添加，未空时可以删除
step1：创建一个数组，在此创建： int[ ] data,定义队首字段：head，队尾字段：tail;
step2：初始化队列长度K，data = new int[ k ],head=-1,tail=-1;
step3：创建判断是否已满、是否为空的方法：isFull（），isEmpty（），
step4：增加元素方法：增加从队尾增加，value为需要添加到队列参数
① 判断是否已满，如果已满，则return false
②判断是否为空，如果为空，head增加一个数据后应head = 0；
tail = （tail+1）%size
data[tail] = value; return true；
step5： 减少元素方法，从队首减少，
若为空，则return false；
若不为空，正常删除，
当head = tail时，则表示已删完，重置：head=-1.tail=-1；return true；
从队首删除，则head = （head+1）%size，return true；
以下为代码：
class MyCircularQueue {
private int[] data;
private int head;
private int tail;
private int size;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
data = new int[k];
head = -1;
tail = -1;
size = k;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if (isFull() == true) {
return false;
}
if (isEmpty() == true) {
head = 0;
}
tail = (tail + 1) % size;
data[tail] = value;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if (isEmpty() == true) {
return false;
}
if (head == tail) {
head = -1;
tail = -1;
return true;
}
head = (head + 1) % size;
return true;
}
/** Get the front item from the queue. */
public int Front() {
if (isEmpty() == true) {
return -1;
}
return data[head];
}
/** Get the last item from the queue. */
public int Rear() {
if (isEmpty() == true) {
return -1;
}
return data[tail];
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return head == -1;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return ((tail + 1) % size) == head;
}
}
网友评论