circular queue環狀佇列
初始值
陣列大小maxsize為6，陣列實際大小len為0，tail與front一開始都是0。
len
會記錄目前實際大小。
push與tail
Queue的push，tail一開始指向0，然後新增資料，再把tail + 1，len + 1。
新增完索引0的值，len會變成1，tail變成1。
新增完索引1的值，len會變成2，tail變成2。
新增完索引2的值，len會變成3，tail變成3。
.
.
.
新增完索引5的值，len會變成6，也就是有新增6個數值，陣列大小為6，不能再新增。
因此要判斷是否為陣列為滿，會用以下的程式碼判斷。
1
2
3
4
5
6
7
8
// 是否滿了？
public boolean isFull() {
// len 等於 6 就回傳true已經滿
if (len >= maxSize) return true;
// len < maxSize
// len小於6(不包含6)，回傳false沒有滿
return false;
}
pop與front
Queue的pop，front一開始指向0，先把資料取出，然後再把front + 1，len - 1。
push與公式
初始值 tail = 0
push公式
1
2
3
arr[tail] = val;
tail = (tail + 1) % maxSize;
len++;
第1次新增
將以下的值代入上方push語法中
最大容量為maxLen = 6
tail = 0
arr[tail] = 要新增的值100
tail = (0 + 1) % 6
新增完後，tail = 1 (指向索引1)
len = len + 1，實際大小增加1
tail指向陣列最後一個元素
將以下的值代入上方push語法中
最大容量為maxLen = 6
tail = 5
arr[5] = 要新增的值 30
tail = (5 + 1) % 6
新增完後，tail = 0 (指向索引0)
len = 2
len = 2 + 1，實際大小變成3。
pop與公式
pop語法
1
2
3
int rtn = arr[front];
front = (front + 1) % maxSize;
len--;
將以下的值代入上方push語法中
最大容量為maxLen = 6
front = 3
先把資料取出arr[front = 3]
然後再把front變數往後移動一格，front = (3 + 1) % 6
front = 4 (指向索引4)
len = 3 - 1，實際大小變成2
假設front指向陣列最後一個元素。
將以下的值代入上方push語法中
最大容量為maxLen = 6
front = 5
先把資料取出arr[front = 5]
然後再把front變數往後移動一格，front = (5 + 1) % 6
front = 0 (指向索引0)
len = 1 - 1，實際大小變成0
print語法跟push與pop語法也是一模一樣，把front代入就行。
i為0 .. len實際已占用大小，0<= i < len
1
(front + i) % maxLen
以上圖來說
i = 0，front = 3，最大容量為maxLen = 6
(3 + 0) % 6 = 3
i = 1，front = 3，最大容量為maxLen = 6
(3 + 1) % 6 = 4
i = 2，front = 3，最大容量為maxLen = 6
(3 + 2) % 6 = 5
i = 3，front = 3，最大容量為maxLen = 6
(3 + 3) % 6 = 0
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class CircularTest {
public static void main(String[] args) throws Exception {
CircularQueue queue = new CircularQueue(6);
System.out.println("=====push=========");
queue.push(1);
queue.push(2);
queue.push(3);
queue.push(4);
queue.push(5);
queue.push(6);
queue.push(7);
queue.print();
System.out.println("======pop========");
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
}
}
class CircularQueue {
int[] arr;
int maxSize;
int front, tail, len;
public CircularQueue(int size) {
arr = new int[size];
maxSize = size;
front = 0;
tail = 0;
len = 0;
}
public boolean isFull() {
if (len == maxSize) return true;
return false; // len < maxSize
}
public boolean isEmpty() {
if (len == 0) return true;
return false;
}
public void push(int val) {
if(isFull()) {
System.out.println("Queue已經滿，不能再push");
return;
}
arr[tail] = val;
tail = (tail + 1) % maxSize;
len++;
}
public int pop() throws Exception {
if (isEmpty()) {
throw new Exception("Queue is empty");
}
int rtn = arr[front];
front = (front + 1) % maxSize;
len--;
return rtn;
}
public int getSize() {
return len;
}
public void print() {
for (int i = 0; i < getSize(); i++) {
int index = (front + i) % maxSize;
System.out.println(arr[index]);
}
}
}