佇列(queue) Lai Ah Fur.

Presentation on theme: "佇列(queue) Lai Ah Fur."— Presentation transcript:

1 佇列(queue) Lai Ah Fur

2 Queue(非circular queue)
Q:array [o..n-1] of item; Procedure addqueue(item:items) Begin if rear==n then queuefull; rear=rear+1; q[rear]=item; end

3 Procedure delqueue(item:items)
Begin if rear==front then queueEmpty; front=front+1; item=q[front]; end

4 Drawback 遇到時,必須把array前端資料往前移,以空出多餘空間. Waste time!

5 Circular queue Procedure addqueue(item:items) Begin
rear=(rear+1) mod n; if rear==front then queuefull; q[rear]=item; end

6 Procedure delqueue(item:items)
Begin if rear==front then queueEmpty; front=(front+1) mod n; item=q[front]; end

7 Drawback front rear Empty 只能存放n-1個元素 ６ 8 2 15 11 10 front rear Full

8 Overcome”只能存放n-1個元素” Procedure addqueue(item:items) Begin
if flag then queuefull; else begin rear=(rear+1) mod n; q[rear]=item; if rear==front then flag=true; //if full end Procedure delqueue(item:items) if rear==front and not flag then queueEmpty; front=(front+1) mod n; item=q[front]; if flag then tag=false; //cancel empty End

9 first last last first first　last 6 (a) (b) Enqueue(6) (d) (e) ６ 8 4 2 15 11 10 (c) (f) Circular queue

10 Implement Queue by linked-list
public class QueueNode { public Object info; public QueueNode next = null; public QueueNode(Object el) { info = el; }

11 public class Queue { private QueueNode head, tail; public Queue() { head = tail = null; } public boolean isEmpty() { return head == null;

12 public void clear() { head = tail = null; } public Object firstEl() { return head.info; public void enqueue(Object el) { if (!isEmpty()) { tail.next = new QueueNode(el); tail = tail.next; else head = tail = new QueueNode(el); public Object dequeue() { // remove the head and return its info; if (!isEmpty()) { Object el = head.info; if (head == tail) else head = head.next; return el; else return null;

13 雙向dequeue 前、後端均可存取元素 亦可為circular dequeue

14 多重queue 多個queue同時放在一個一維array上 2個queue 1 n …… …… front1 rear2 front2

15 Q (J-1)th queue b b[i] f[i] .. Q-length f r[i] Jth queue Q-length:每 Queue所分配 部分陣列的長 度 r

16 Procedure add_multQ(I,x:integer)
Begin front=f[i]-b[i]; rear=r[i]-b[i]; rear=(rear+1) mod Q-length; If front==rear then Quesufull; Else begin q[rear+b[i]]=x; r[i]=rear+b[i]; End end f[i]存放ith queue之front指標,b[i]存放ith queue之base指標; r[i]存放ith queue之rear指標

17 Procedure del_multQ(I,x:integer)
Begin front=f[i]-b[i]; rear=r[i]-b[i]; If front==rear then Quesufull; Else begin front=(front+1)mod Q-length; x=q[front+b[i]]; f[i]=front+b[i]; End end

18 佇列(queue)的應用 佇列結構在計算機上的應用也相當廣泛，譬如：
job scheduling:計算機的作業系統裏，若所有的工作優先權(priority)都相同，則採用佇列(queue)來安排工作程序(job scheduling)，使其達到先到先做的特性。 計算機的模擬(simulation)，模擬是一種評估的技術，評估者建立一套電腦化系統評估模式，將真實情況藉由一種抽象模式，以分析、瞭解各種因素的影響，而在模擬的過程中，常有event-driven或time-driven的輸入訊號，由於其輸入時間不一，因此使用queue來反映真實的情況。 做為輸出入工作緩衝區(buffer)；例如spooling，是先將輸入資料寫在磁碟上，再輸入電腦處理，處理後的輸出資料亦先寫在磁碟上，再由列表機印出，也是採用佇列(queue)的特性來完成。 Graph之breadth first search