線性資料結構(Queue、Stack或Linked List) 與優先權佇列(Priority Queue)

資料結構會影響到程式的執行效率，解題過程中須想清楚，需要使用的資料結構，為何要使用此資料結構，以下介紹線性資料結構(Queue、Stack、Linked List)與優先權佇列(Priority Queue)不能算是線性資料結構，但功能與線性資料結構有些類似。

一、Queue(佇列)

Queue(佇列)是先進來的元素先出去(First In First Out，縮寫為FIFO)的資料結構，通常用於讓程式具有排隊功能，依序執行工作，例如：印表機同時間有多個檔案等待列印，在印表機內會有一個Queue(佇列)的功能，將準備列印的檔案暫存在Queue等待印表機提供列印服務，先送到印表機的檔案先印出來。實作Queue的部分，可以自行撰寫Queue程式，或透過第9章的標準樣板函式庫(STL)所提供的Queue函式庫，使用Queue函式庫實作程式不須知道內部程式如何實作，只要知道如何在Queue中新增與刪除資料。

(一)Queue使用array實作

(a)範例說明

請實作一個程式將數字1到4依序加入Queue，每加入一個數字後，顯示Queue目前所有元素值到螢幕。最後刪除最前面的元素，接著顯示Queue目前所有元素值到螢幕。

(b)預期程式執行結果

(c)範例程式如下

以下顯示上述程式從佇列qu中執行新增與刪除元素時，程式中front與back的變化，可以了解front與back的用途，front用於從Queue取出元素，back用於加入元素到Queue。

(二)Queue使用STL實作

(a)範例說明

請實作一個程式將數字1到4依序加入Queue，最後不斷刪除最前面的元素，直到Queue為空的為止，顯示每個被刪除的元素到螢幕。

(b)預期程式執行結果

(c)範例程式如下

(三)找出最後一個人

給定n個數字分別代表n個人的編號，請依序將這n個人的編號加入排隊隊伍中，若每次請最前面兩個人移動到隊伍最後，淘汰目前第一個人，再取出現在最前面兩個人到隊伍後方，接著淘汰目前第一個人，直到剩下一個人為止，顯示出移動的過程與淘汰的順序，最後顯示剩下人的編號，輸入的n值小於1000。。

輸入說明

輸入一個正整數n，表示有n個編號準備要輸入，接著下一行輸入n個數字。

輸出說明

數字移動的過程、淘汰的順序與顯示剩下人的編號。

輸入範例

1 3 5 4 2

輸出範例

1 3 5 4 2

將1加到最後

將3加到最後

將5刪除

將4加到最後

將2加到最後

將1刪除

將3加到最後

將4加到最後

將2刪除

將3加到最後

將4加到最後

將3刪除

剩餘最後一個號碼為4

(a)解題想法

本題從隊伍前方取出兩個編號，再依序加入到隊伍的最後，不會在隊伍中間進行插入，所以適合使用Queue來實作此程式。

(b)程式碼

(c)程式結果預覽

按下「執行->編譯並執行」，結果顯示在螢幕如下

二、Stack(堆疊)

Stack(堆疊)是後進來的元素先出去(Last In First Out，縮寫為LIFO)的資料結構，隱含在函式的遞迴呼叫，因為遞迴的過程中最後呼叫的函式要優先處理，系統會實作堆疊程式自動處理遞迴呼叫，不須自行撰寫堆疊，特定問題可能需要使用Stack(堆疊)進行解題，例如：程式的括弧配對檢查，右大括號配對最接近未使用的左大括號，將左大括號加進Stack(堆疊)中，一遇到右大括號就取出配對。實作Stack的部分，可以自行撰寫Stack程式，或透過第9章的標準樣板函式庫(STL)所提供的Stack函式庫，使用Stack函式庫實作程式不須知道內部程式如何實作，只要知道如何在Stack中新增與刪除資料。

(一)Stack使用array實作

(a)範例說明

請實作一個程式將數字1到4依序加入Stack，每加入一個數字後，顯示Stack目前所有元素值到螢幕。最後刪除最上面的元素，接著顯示Stack目前所有元素值到螢幕。

(b)預期程式執行結果

(c)範例程式如下

以下顯示上述程式從堆疊st中執行新增與刪除元素時，程式中top的變化，可以了解top的用途。

(二)Stack使用STL實作

(a)範例說明

請實作一個程式將數字1到4依序加入Stack，依序取出每一個元素顯示在螢幕上，直到Stack空的為止。

(b)預期程式執行結果

(c)範例程式如下

(三)括弧的配對

給定由左大括弧({)或右大括弧(})所組成的字串，將此字串放在一行內，請判斷所有左大括號或右大括號能否配對成功，左大括號配對最接近的右大括號，左大括號在左，右大括號在右，若能全部配對成功，則顯示配對成功的數量，否則顯示「配對失敗」，字串長度小於1000個字元。

輸入說明

輸入一行由左大括弧({)或右大括弧(})所組成的字串，字串長度小於1000個字元。

輸出說明

若能全部配對成功，則顯示配對成功的數量，否則顯示「配對失敗」。

輸入範例

{{{}{}}{{}}}

輸出範例

共有6對的大括號

(a)解題想法

右大括號須找最接近的左大括號，使用堆疊Stack暫存左大括號，遇到右大括號，就取出堆疊內左大括號，遇到最後一個的右大括號，堆疊有剛好只剩一個左大括號，就配對成功，輸出配對的數量，否則輸出「配對失敗」。

(b)程式碼

(c)程式結果預覽

按下「執行->編譯並執行」，結果顯示在螢幕如下。

(四)後序運算

數學運算式為中序運算式，例如：「3+2*5-9」是中序運算式，因為運算子(+,-,*,/)介於數字的中間，若轉成後序運算式，則因為先乘除後加減，所以後序運算式為「3 2 5 * + 9 -」，運算子移到數字的後面，將中序運算式轉成後序運算式，就可以使用堆疊(Stack)進行運算。

運算原理如下：如果遇到數字就加入堆疊，遇到運算子(+,-,*,/)就從堆疊中取出兩個數字進行運算，結果回存堆疊，運算到後序運算式全部執行完成後，會剩下一個數字在堆疊內就是答案。

以「3 2 5 * + 9 -」為例，進行後序運算式與堆疊的關係。

輸入說明

輸入後序運算式。

輸出說明

輸出後續運算的結果。

輸入範例

3 2 5 * + 9 -

輸出範例

(a)解題想法

本題從使用堆疊(Stack)實作程式。

(b)程式碼

(c)程式結果預覽

按下「執行->編譯並執行」，結果顯示在螢幕如下。

三、Linked List(鏈結串列)

Linked List(鏈結串列)是將多筆資料以Pointer(指標)進行串接，使用Linked List的好處是可以在任何位置插入或刪除元素，陣列、佇列與堆疊不適合在中間位置插入或刪除元素，適合在兩端插入或刪除元素，但Linked List不能讀取指定位置的元素，只能從頭往後或從尾往前一個一個走到指定的位置才能讀取，而陣列可以使用索引值讀取陣列中指定位置的元素。陣列與Linked List都有其優缺點，寫程式時需要善加利用每種資料結構的優點，避開或減少使用其缺點。實作Linked List的部分，可以自行撰寫Linked List程式，或透過STL所提供的函式庫list功能進行撰寫。

(一)Linked List使用STL實作

(a)範例說明

請實作一個程式將數字1、2與4依序加入Linked List(鏈結串列)，每加入一個數字後，顯示Linked List目前所有元素值到螢幕。最後插入數字3在數字2的後面，接著顯示Linked List目前所有元素值到螢幕，再刪除數字2的元素，最後顯示Linked List目前所有元素值到螢幕。

(b)預期程式執行結果

(c)範例程式如下

(二)可以插隊在任意位置

給定數字由1到n分別代表n個人的編號，請依照編號由小到大依序將這n個人加入排隊隊伍中，接著有m個指令，指令「s」服務目前最前面的人，輸出此人的編號，此人被服務完後會排到隊伍的最後，指令「p」表示將指定的人插入到隊伍中指定的位置，例如「p 100 2」，將編號100的人插入到隊伍第2個位置，輸入的n值小於200且m值小於100。

輸入說明

輸入一個正整數n與m，表示有n個人在排隊，有m個指令等待輸入，接下來有m行，每一行都是指令，若是指令「s」，顯示目前隊伍最前面的人的編號，指令「p d1 d2」後面會接兩個數字，將編號d1的人插入到隊伍中d2的位置。

輸出說明

遇到指令s時，輸出隊伍中最前面的人的編號。

輸入範例

100 10

p 100 2

p 50 1

p 75 1

p 56 1

輸出範例

100

(a)解題想法

本題因為要從隊伍中間取出元素，並將元素插入到隊伍中任何位置，所以不適合使用Array(陣列)或Queeu(佇列)，最好使用Linked List(鏈結串列)適合於資料結構中插入元素。

(b)程式碼

四、PriorityQueue(優先權佇列)

PriorityQueue(優先權佇列)會讓新增的資料由小到大排序好，或由大到小排序好，使用者可以快速取出最小或最大的元素，當儲存的資料會不斷新增或刪除，需要馬上調整找出最小或最大元素，就適合使用PriorityQueue(優先權佇列)儲存資料，使用結構Heap實作PriorityQueue(優先權佇列)，PriorityQueue(優先權佇列)不算是線性資料結構，因為結構Heap屬於樹狀結構(下一單元將介紹)，但操作上類似線性結構，提供插入、刪除元素與取出最上面的元素等功能，所以併入此單元一起說明。實作PriorityQueue的部分，可以自行撰寫PriorityQueue程式，或透過STL所提供的PriorityQueue功能進行撰寫，但因為篇幅關係就不自行撰寫PriorityQueue程式。

(一)PQueue使用STL(大的前面)

(a)範例說明

請實作一個程式將數字4、8、3、5與2依序加入PriorityQueue，大的元素排在最上面，最後不斷刪除最上面的元素，直到PriorityQueue為空的為止，依序顯示每個被刪除的元素到螢幕。

(b)預期程式執行結果

(c)範例程式如下

(二)PQueue使用STL(小的前面)

(a)範例說明

請實作一個程式將數字4、8、3、5與2依序加入PriorityQueue，改成小的元素排在最上面，最後不斷刪除最上面的元素，直到PriorityQueue為空的為止，依序顯示每個被刪除的元素到螢幕。

(b)預期程式執行結果

(c)範例程式如下

(三)找出因數只有3、5與7的數字

由小到大列出數字，該數字的因數只有數字3、5與7所組成，請列出前200個數字。

輸入說明

本範例不需要輸入資料。

輸出說明

輸出前200個因數只有3、5與7的數字，先顯示目前是第幾個，再顯示該數字。

輸入範例

本範例不需要輸入資料。

輸出範例(列出前20個)

1 3

2 5

3 7

4 9

5 15

6 21

7 25

8 27

9 35

10 45

11 49

12 63

13 75

14 81

15 105

16 125

17 135

18 147

19 175

20 189

(a)解題想法

本題先將1放入PriorityQueue，從PriorityQueue取出最小的數字，將它顯示出來，該取出數字的因數只有3、5與7符合題目需求，再將該數字分別乘以3、5與7，將這些相乘後的數字加入set，使用set幫忙紀錄乘以3、5與7的數字是否有重複，若重複出現過就不再加入PriorityQueue，沒有出現過就加入PriorityQueue，每次都需要取最小的元素，需要不斷新增元素，所以適合使用PriorityQueue來實作此程式。

(b)程式碼