---
title: 'Queue 佇列'
disqus: kyleAlien
---
Queue 佇列
===
## OverView of Content
如有引用參考請詳註出處，感謝 :smile_cat:
> **First in First out** 先進先出，只能從尾端取得資料
[TOC]
## 靜態 Queue
```java=
public class StaticQueue {
public static void main(String[] args) {
Queue q = new Queue(6);
q.enqueue(5);
q.enqueue(4);
q.enqueue(0);
q.enqueue(100);
q.print();
System.out.println("dequeue: " + q.dequeue());
System.out.println("dequeue: " + q.dequeue());
q.print();
q.enqueue(200);
q.enqueue(1);
q.print();
System.out.println("dequeue: " + q.dequeue());
System.out.println("dequeue: " + q.dequeue());
q.print();
}
}
class Queue {
private int size;
private int [] Queue;
private int front = 0 , rear = 0;
Queue(int size) {
this.size = size;
Queue = new int[size];
}
//"1: "
void enqueue(int data) {
if(rear + 1 >= size) {
System.out.println("Over size Cannot enqueue " + data);
return;
}
Queue[rear++] = data;
}
//"2: "
int dequeue() {
if(rear == front) {
System.out.println("Over size Cannot dequeue");
return -1;
}
int result = Queue[front++];
return result;
}
void print() {
for(int i = front; i <= rear; i++) {
System.out.println("i = " + i + ", value = " + Queue[i]);
}
}
}
```
1. enqueue() 取出資料
> 移動最近的指標 (rear)，放入最新的資料
2. dequeue() 加入資料
> 移動最遠的指標 (front)，也就是取出最舊的資料
3. print()
> 最舊到最新 rear to front，印出所有資料
**--實做--**
> 
## 靜態 Queue + 位移
* 這樣會發生一件事情，指標的位移不代表資料真的有位移
> 一開始 enqueue() 7 次 Data_1~7 依序放入
> > 
>
> 經過兩次 deququ() Data_1 and Data_2(先入先出)，並且 enqueue() 1次，這時 Data_1, 2, 7 其實都還在 array 內部，只是指標變位資料仍在
> > 
> > 這時候有 3 個位子，不過卻只能再放 1 個，**因為 rear 指標位子的關係**
>
> **移動全部參數，這樣可以多出空間，但`如果`陣列內資了過於龐大，會耗費過多資源**
> > 
* 新增一個 fixArray() 到每次 dequeue()
```java=
public class DynamicQueue {
public static void main(String[] args) {
dyQueue d = new dyQueue();
d.enquue(199);
d.enquue(20);
d.enquue(0);
d.print();
System.out.println("Dequeue: " + d.dequeue());
System.out.println("Dequeue: " + d.dequeue());
d.enquue(10);
d.enquue(1000);
d.print();
System.out.println("Dequeue: " + d.dequeue());
System.out.println("Dequeue: " + d.dequeue());
}
}
...
int dequeue() {
if(rear == front) {
System.out.println("Over size Cannot dequeue");
return -1;
}
front++;
int result = Queue[front];
fixArray();
return result;
}
private void fixArray() {
//"1. "
if(front != 0) {
//"2. "
for(int i = front, j = 0; i < rear; i++, j++) {
Queue[j] = Queue[i];
}
//"3. "
rear = rear - front;
front = 0;
}
System.out.println("--------------- after fix");
print();
}
```
1. 如果指標不是指向 0 時，才開始修正位置(資料 and 指標)
2. 資料的複製，複製到最前方 0 開始的位子
3. 修正指標(rear & front)位子
**--實做--**
> 
## 動態 Queue
* 動態 Queue 是解決靜態問題的好方法，**不受到資料大小限制，也不需移位**
```java=
public class DynamicQueue {
public static void main(String[] args) {
dyQueue d = new dyQueue();
d.enquue(199);
d.enquue(20);
d.enquue(0);
d.print();
System.out.println("Dequeue: " + d.dequeue());
System.out.println("Dequeue: " + d.dequeue());
d.enquue(10);
d.enquue(1000);
d.print();
System.out.println("Dequeue: " + d.dequeue());
System.out.println("Dequeue: " + d.dequeue());
}
}
class QNode {
int data;
QNode next;
QNode(int data) {
this.data = data;
}
}
class dyQueue {
QNode Front, rear;
boolean isEmpty() {
return Front == null;
}
void enquue(int data) {
QNode n = new QNode(data);
if(Front == null) {
Front = n;
rear = n;
rear.next = Front;
} else {
Front.next = n;
Front = n;
}
}
int dequeue() {
if(isEmpty()) {
System.out.println("Queue empty cannot dequeue");
return -1;
} else {
int result;
if(Front == rear) {
result = rear.data;
Front = null;
rear = null;
} else {
result = rear.data;
rear = rear.next;
}
return result;
}
}
void print() {
QNode temp = rear;
while(temp != null) {
System.out.println("Value: " + temp.data);
temp = temp.next;
}
}
}
```
**--實做--**
> 
## Queue 應用
### 環狀佇列
* 本質是**靜態佇列**的變型
* **圖型走訪先廣度後深度搜尋法時、CPU 排程**，就是使用佇列
* 可以看到靜態佇列，經過位移後可以到達空間利用，但是如果資料大量時會浪費資源
> 1. 預設指標 rear & front 為 0
> 2. 新增資料後 rear + 1，指標**指向即將要放置的區域**
> 3. 取出資料後 front + 1指標**指向即將要取的區域**
> 4. 為了判斷何時為 Empty or Full
> > **Empty** 時**指標會重疊**，代表已無資料可取
> > **Full** 時**犧牲一個空間**不放資料，也就是**只能放置 n-1 個**資料，這樣**指標不會重疊**
> > 
```java=
public class CircleQueue {
public static void main(String[] args) {
cQueue q = new cQueue(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);
q.enqueue(60);
q.print();
System.out.println("Dequeue: " + q.dequeue());
System.out.println("Dequeue: " + q.dequeue());
System.out.println("Dequeue: " + q.dequeue());
System.out.println("Dequeue: " + q.dequeue());
System.out.println("Dequeue: " + q.dequeue());
System.out.println("Dequeue: " + q.dequeue());
q.print();
}
}
class cQueue {
private int[] Queue;
private int rear = 0, front = 0;
cQueue(int size) {
Queue = new int[size];
}
boolean isEmpty() {
return rear == front;
}
boolean isFull() {
//"1: "
if(rear + 1 >= Queue.length) { //a
return true;
}
boolean block = (rear + 1) == front; //b
if(block) {
System.out.println("block");
}
return block;
}
void enqueue(int data) {
if(isFull()) {
//"2: "
if(rear + 1 >= Queue.length) {
System.out.println("fix rear ptr: " + data);
} else {
System.out.println("Circle full cannot enqueue " + data);
return;
}
}
Queue[rear++] = data;
//"3: "
if(rear >= Queue.length) {
rear = 0;
}
}
int dequeue() {
if(isEmpty()) {
System.out.println("Circle empty cannot dequeue data");
return -1;
}
int data = Queue[front++];
if(front >= Queue.length) {
front = 0;
}
//"3: "
return data;
}
void print() {
int f = front;
int r = rear;
System.out.println("\nfornt: " + front + ", rear: " + rear);
while(f != r) {
System.out.println("Queue["+ f + "] = " + Queue[f++]);
if(f >= Queue.length) {
f = 0;
}
}
}
}
```
1. 資料滿 (Full) 時有**兩種狀況**
> a. 資料超出原本預設的 Size，rear+1 >= Queue.length
> b. 下一個指標指向重複位子，rear+1 == front
2. isFull() 是判斷是否超出，在內部在判斷一次是否需要返回(跳出)
3. 放資料後指標 +1，要確認指標是否已超出預設 Size
**--實做--**
> 
### 雙向佇列
* **動態佇列**的應用
* 使用兩個指標，頭端跟尾端皆可 放&取 資料
> 
```java=
public class DoubleQueue {
public static void main(String[] args) {
dQueue q = new dQueue();
q.enqueue(10, DOUBLE_TYPE.START);
q.enqueue(20, DOUBLE_TYPE.END);
q.enqueue(30, DOUBLE_TYPE.START);
q.enqueue(40, DOUBLE_TYPE.END);
q.print();
/*
System.out.println("Dequeue Data: " + q.dequeue(DOUBLE_TYPE.START));
System.out.println("Dequeue Data: " + q.dequeue(DOUBLE_TYPE.START));
System.out.println("Dequeue Data: " + q.dequeue(DOUBLE_TYPE.START));
System.out.println("Dequeue Data: " + q.dequeue(DOUBLE_TYPE.START));
System.out.println("Dequeue Data: " + q.dequeue(DOUBLE_TYPE.START));
q.print();
*/
System.out.println("Dequeue Data: " + q.dequeue(DOUBLE_TYPE.END));
System.out.println("Dequeue Data: " + q.dequeue(DOUBLE_TYPE.END));
System.out.println("Dequeue Data: " + q.dequeue(DOUBLE_TYPE.END));
System.out.println("Dequeue Data: " + q.dequeue(DOUBLE_TYPE.END));
System.out.println("Dequeue Data: " + q.dequeue(DOUBLE_TYPE.END));
}
}
class QueueNode {
int value;
QueueNode next = null;
QueueNode(int value) {
this.value = value;
}
}
class dQueue {
QueueNode front, rear;
enum DOUBLE_TYPE {
START, END
};
boolean isEmpty() {
return front == null || rear == null;
}
void enqueue(int value, DOUBLE_TYPE e) {
QueueNode q = new QueueNode(value);
QueueNode temp;
if(isEmpty()) {
front = q;
rear = q;
//"1: "
//front.next = rear; // err: 自己指向自己
} else {
switch(e) {
case START:
temp = front;
front = q;
q.next = temp;
break;
case END:
temp = rear;
rear = q;
temp.next = q;
break;
}
}
}
int dequeue(DOUBLE_TYPE e) {
int value = -1;
if(isEmpty()) {
System.out.println("Double Queue is Empty cannot Dequeue");
return value;
}
switch(e) {
case START:
value = front.value;
front = front.next;
break;
case END:
QueueNode temp = front;
QueueNode saveTemp = front;
while(temp != rear) {
saveTemp = temp;
temp = temp.next;
}
//"2: "
if(front == rear) {
value = rear.value;
rear = null;
} else {
value = temp.value;
rear = saveTemp;
}
break;
}
return value;
}
void print() {
QueueNode temp = front;
while(temp != null) {
System.out.println("value: " + temp.value);
temp = temp.next;
}
}
}
```
1. 不是環狀對列不用將 front 指向 rear
2. 當取到最後一個 Data 時，raer = null
**--實做--**
> 
### 優先佇列
* **不必遵守 FIFO 的條件**
* 元素必須賦予優先權，按照優先權加入 Queue，取出資料時必須依**照優先權取出**
* **以輸入最高優先權是 Queue，以輸入最低優先權是 Stack**
## Appendix & FAQ
:::info
:::
###### tags: `資料結構`
Sign in with Wallet
Connect another wallet