資料結構使用Java 第8章 佇列(Queue).

Presentation on theme: "資料結構使用Java 第8章 佇列(Queue)."— Presentation transcript:

1 資料結構使用Java 第8章 佇列(Queue)

2 課程內容 佇列(Queue)的基本結構 佇列(Queue)的特性 佇列(Queue)的操作 佇列延伸的結構 佇列的應用
add, offer, remove, poll, element, peek 佇列延伸的結構 佇列的應用

3 佇列的基本結構 佇列的兩端都有開口。 元素可以從佇列的前端(front)離開，從佇列的後 端(rear)加入。

4 佇列的特性 「先進先出」(FIFO, First-In-First-Out)的模式
佇列並沒有像陣列一樣提供任何位置的元素隨機 存取使用的特性。

5 佇列的特性 先加入者在前、後加入者在後。 連續的元素之間不能留下空位 假如佇列滿了就無法再加入元素。

6 佇列的特性 移除元素必須從佇列中最先加入(位於最前端)的 元素開始移除。 一旦裡面清空了便無法再取出元素。

7 實作Queue 使用Java Collections Framework中的Queue類別 實作。
Queue在Java API架構中的位置： import java.util.*; 宣告Linked List物件 Queue<DT> 物件名 = new LinkedList<DT> (); Queue<String> que = new LinkedList<String>(); Queue為抽象概念無法實體化(instance)，所以採 用LinkedList來實作。

8 Queue的操作 Throws exception Returns special value Insert add(e) offer(e)
Remove remove() poll() Examine element() peek() 程式執行 停止 繼續執行

9 加入(add), 提供(offer) 即是新增元素，這是將元素加入佇列的唯一方法； 假如佇列不是滿的，就把元素從後方放入佇列。
例如：que.add(“first”); 若que已滿，則產生例外(Exception)。 例如：que.offer(“second”); 若que已滿，則回傳false值。 Throws exception Returns special value Insert add(e) offer(e) Remove remove() poll() Examine element() peek()

10 移除(remove), 獲得(poll) 即是刪除元素，並取得該元素的內容；
假如佇列不是空的，就把目前位於最前端的元素 移出佇列，同時探知該元素是什麼內容。 程式碼：物件名.remove(); 例如：que.remove(); 若que已空，則發生例外(Exception)。 例如：que.poll(); 若que已空，則回傳null值。 Throws exception Returns special value Insert add(e) offer(e) Remove remove() poll() Examine element() peek()

11 元素(element), 查看(peek) 即是讀取元素。 此動作不新增新元素，也不刪除現有元素。 程式碼：物件名.element();
例如：que.element(); 若que已空，則發生例外(Exception)。 例如：que.peek(); 若que已空，則回傳null值。 Throws exception Returns special value Insert add(e) offer(e) Remove remove() poll() Examine element() peek()

12 取得Queue中的所有元素 判斷Queue是否為空 若不為空則移除元素 重複步驟直到Queue為空 String value;
While((value=que.poll())!=null) System.out.println(value);

13 佇列延伸的結構 循環佇列(circular queue)
最多只能容納MaxQueueSize-1個元素。(因為 front所指的位置必須是空的。) 優點：front與rear的值不會一直增大。

14 佇列延伸的結構 雙向佇列(deque) 可以讓兩個queue同時在一塊空間裡成長。 若QRearA = QRearB，則代表空間已滿。

15 佇列的應用 : CPU的排程問題

16 優先佇列(priority queue)的觀念
優先佇列需要快速找到最高優先順序的元素 常用Heap的方法來協助。(後面章節再介紹)

17 佇列的應用 : 正反唸都一樣的字串 正反唸都一樣的字串，英文叫做Palindrome。 短字串容易判斷。長字串則用電腦判斷較快速。