---
title: 'Queue 佇列'
disqus: kyleAlien
---

Queue 佇列
===

## OverView of Content
如有引用參考請詳註出處，感謝 :smile_cat:

> **First in First out** 先進先出，只能從尾端取得資料

[TOC]

## 靜態 Queue

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()

    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 是解決靜態問題的好方法，**不受到資料大小限制，也不需移位**

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 個**資料，這樣**指標不會重疊**
> > 

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

**--實做--**
> 

### 雙向佇列
* **動態佇列**的應用
* 使用兩個指標，頭端跟尾端皆可 放&取 資料
> 

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: `資料結構`