Embedded Files
資料結構會影響到程式的執行效率，須想清楚需要使用哪一種資料結構，為何使用此資料結構。以下介紹佇列(Queue)與堆疊(Stack)。
5-1佇列
佇列(Queue)是先進來的元素先出去(First In First Out，縮寫為FIFO)的資料結構，通常用於讓程式具有排隊功能，依序執行工作，例如：印表機同時間有多個檔案等待列印，在印表機內會有一個佇列功能，將準備列印的檔案暫存在佇列等待印表機提供列印服務，先送到印表機的檔案先印出來。實作佇列的部分，可以自行撰寫佇列程式，或透過Python所提供的串列(list)結構，使用串列(list)結構實作程式不須知道串列(list)結構如何實作，只要知道如何在串列(list)結構中新增與刪除資料。
5-1-1-自己實作佇列
(a)範例說明
請實作一個程式將數字1到4依序加入佇列，每加入一個數字後，顯示目前佇列所有元素值到螢幕。刪除最前面的元素，接著顯示目前佇列所有元素值到螢幕，直到佇列內所有元素被刪除。
(b)預期程式執行結果
(c)說明與程式如下
以下顯示上述程式從佇列q中執行新增與刪除元素時，程式中front與back的變化，可以了解front與back的用途，front用於從佇列q取出元素，back用於加入元素到佇列q。
Step1)開始佇列q是空的，設定front為-1，back也是-1。
對應程式如下。
self.front = -1
self.back = -1
Step2) 佇列q插入第一個元素1，back遞增1變成0，將元素1加入佇列q中back所指定的位置。
對應程式如下。
self.back = self.back + 1
self.data[self.back] = x
Step3) 佇列q插入第二個元素2，back遞增1變成1，將元素2加入佇列q中back所指定的位置。
Step4) 佇列q插入第三個元素3，back遞增1變成2，將元素3加入佇列q中back所指定的位置。
Step5) 佇列q插入第四個元素4，back遞增1變成3，將元素4加入佇列q中back所指定的位置。
Step6)從佇列q刪除最前面的元素，front改為0，數值1還是存在只是front往後移了一格，front指到的元素表示已經取出該元素且刪除該元素。
對應程式如下。
self.front = self.front + 1
return self.data[self.front]
佇列完整程式
第1到26行：定義類別Queue。
第2到6行：定義初始化方法(__init__)內宣告size用於儲存佇列的大小，data用於儲存佇列內元素，每個元素設定為0，總共有size個，設定front為-1，back為-1。
第7到8行：定義isFull方法，檢查佇列是否滿了，回傳back是否等於size-1。
第9到10行：定義isEmpty方法，檢查佇列是否空了，回傳back是否等於front。
第11行到第16行：定義enQueue方法，插入元素x到佇列，若方法isFull條件成立，則顯示「佇列已滿」(第12到13行)；否則先將back遞增1，再儲存數字x到串列data的back位置(第14到16行)。
第17行到第22行：定義deQueue方法，若方法isEmpty條件成立，則顯示「佇列是空的」(第18到19行)；否則先將self.front遞增1，再回傳串列data的front位置的數值(第20到22行)。
第23到26行：定義printQueue方法，印出佇列內的所有元素。
第24到25行：使用迴圈顯示data[front+1]到data[back]的所有元素。
第26行：顯示換行。
第27行：宣告q為五個元素的佇列。
第28到30行：使用迴圈與enQueue方法將數字1到5加入到佇列q，每加一個元素後就呼叫printQueue方法顯示目前佇列內所有元素到螢幕上。
第31到33行：使用迴圈執行5次，呼叫deQueue方法每次取出佇列q的第一個元素，取出一個元素後就呼叫printQueue方法顯示目前佇列內所有元素到螢幕上。
佇列目前隨著資料的新增與刪除後，已經儲存過的空間就無法使用，所以產生環狀佇列的概念，當環狀佇列到達儲存空間的最後一個位置後，若前方元素已經取出，就可以將資料儲存到第一個位置，繼續往後儲存直到滿了為止，以下介紹環狀佇列(Circular Queue)。
5-1-2 環狀佇列
(a)範例說明
實作一個程式將數字1到4依序加入環狀佇列，每加入一個數字後，顯示環狀佇列目前所有元素值到螢幕。刪除最前面加入的元素，接著顯示環狀佇列目前所有元素值到螢幕。
(b)預期程式執行結果
(c)說明與程式如下
以下顯示上述程式從環狀佇列q中執行新增與刪除元素時，程式中front與back的變化，可以了解front與back的用途，front用於從環狀佇列q取出元素，back用於加入元素到環狀佇列q。
Step1)開始環狀佇列q是空的，設定front為0，back也是0。
對應程式如下。
self.front = 0
self.back = 0
Step2) 環狀佇列q插入第一個元素1，將元素1加入環狀佇列中back所指定的位置，為了讓back的數值可以回到環狀佇列第一個位址，back遞增1後求除以環狀佇列大小的餘數，back等於1。
對應程式如下。
self.data[self.back] = x
self.back = (self.back + 1) % self.size
Step3)環狀佇列q插入第二個元素2，將元素2加入環狀佇列中back所指定的位置，為了讓back的數值可以回到環狀佇列第一個位址，back遞增1後求除以環狀佇列大小的餘數，back等於2。
Step4)環狀佇列q插入第三個元素3，將元素3加入環狀佇列中back所指定的位置，為了讓back的數值可以回到環狀佇列第一個位址，back遞增1後求除以環狀佇列大小的餘數，back等於3。
Step5)環狀佇列q插入第四個元素4，將元素4加入環狀佇列中back所指定的位置，為了讓back的數值可以回到環狀佇列第一個位址，back遞增1後求除以佇列大小的餘數，back等於4。
此時若環狀佇列q插入第五個元素5，會產生環狀佇列已經滿了的訊息，如此環狀佇列的最後一個儲存空間無法使用，不然環狀佇列空的與滿了的檢查條件都是front是否等於back，將無法判斷。
檢查環狀佇列是否為空與是否為滿的程式如下。
def isFull(self):
return self.front == ((self.back + 1) % self.size)
def isEmpty(self):
return self.back == self.front
Step6)從環狀佇列q刪除最前面的元素，front遞增1，數值1還是存在只是front往後移了一格，front指到的元素為目前存在環狀佇列的元素。為了讓front的數值可以回到環狀佇列第一個位址，front遞增1後求除以環狀佇列大小的餘數
對應程式如下。
item = self.data[self.front]
self.front = (self.front + 1) % self.size
return item
Step7) 環狀佇列q插入第五個元素5，將元素5加入環狀佇列中back所指定的位置，為了讓back的數值可以回到環狀佇列第一個位址，back遞增1後求除以佇列大小的餘數，back等於0，back指向環狀佇列的第一個元素。
環狀佇列完整程式
第1到34行：定義類別CirQueue。
第2到6行：定義初始化方法(__init__)內宣告size用於儲存環狀佇列的大小，data用於儲存環狀佇列內元素，每個元素設定為0，總共有size個，設定front為0，back為0。
第7到8行：定義isFull方法，檢查佇列是否滿了，回傳front是否等於back+1%size。
第9到10行：定義isEmpty方法，檢查佇列是否空了，回傳back是否等於front。
第11行到第16行：定義enQueue方法，插入元素x到環狀佇列，若方法isFull條件成立，則顯示「環狀佇列已滿」(第12到13行)；否則儲存數字x到環狀串列data的back位置，再將back遞增1，再除以size求餘數(第14到16行)。
第17行到第23行：定義deQueue方法，若方法isEmpty條件成立，則顯示「環狀佇列是空的」(第18到19行)；否則變數item指定到串列data的front位置的數值，將self.front遞增1，再除以size求餘數，回傳變數item (第20到23行)。
第24到34行：定義printQueue方法，印出環狀佇列內的所有元素。
第25到33行：若環狀佇列不是空的，則若back大於front，則印出環狀佇列出front到back-1的所有元素(第26到28行)，否則環狀佇列被拆成兩部分，印出front到size-1的所有元素，接著印出0到back-1的所有元素(第29到33行)，接著顯示換行(第34行)。
第35行：宣告q為五個元素的環狀佇列。
第36到38行：使用迴圈與enQueue方法將數字1到4加入到環狀佇列q，每加一個元素後就呼叫printQueue方法顯示目前環狀佇列內所有元素到螢幕上。
第39到41行：使用迴圈執行4次，呼叫deQueue方法每次取出環狀佇列q的第一個元素，取出一個元素後就呼叫printQueue方法顯示目前環狀佇列內所有元素到螢幕上。
5-1-3使用串列實作佇列
(a)範例說明
實作一個程式，將數字1到4依序加入佇列，最後不斷刪除最前面的元素，直到佇列為空的為止，顯示每個被刪除的元素到螢幕。
(b)預期程式執行結果
(c)程式如下
第1行：宣告qu為空串列。
第2到4行：使用迴圈在佇列qu中依序插入1、2、3與4，每插入一個數字，顯示佇列qu的每個元素到螢幕上。
第5到6行：使用for迴圈與方法pop依序取出第一個元素到螢幕上，並顯示佇列qu的剩餘所有元素到螢幕上。
5-1-4 找出最後一個人
(a)範例說明
給定n個數字分別代表n個人的編號，請依序將這n個人的編號加入排隊隊伍中，若每次請最前面兩個人移動到隊伍最後，淘汰目前第一個人，再取出現在最前面兩個人到隊伍後方，接著淘汰目前第一個人，直到剩下一個人為止，顯示出移動的過程與淘汰的順序，最後顯示剩下一個人的編號，輸入的n值小於1000。。
輸入說明
輸入一個正整數n，表示有n個編號準備要輸入，接著下一行輸入n個數字。
輸出說明
數字移動的過程、淘汰的順序與顯示剩下一個人的編號。
(b)預期程式執行結果
(c)說明與程式如下
本題從隊伍前方取出兩個編號，再依序加入到隊伍的最後，不會在隊伍中間進行插入，所以適合使用佇列來實作此程式。
第1行：宣告qu為空串列。
第2行：使用函式input輸入一個整數字串，整數字串經由函式int轉成整數，變數n參考到此整數。
第3行：使用函式input輸入n個數字，使用方法split進行分割，分割成串列，串列nums參考到此串列。
第4到5行：使用迴圈執行n次，依序取出串列nums的每一個元素加入到串列qu。
第6行到第14行： 使用while迴圈，當串列qu的個數大於1時，取出qu的第一個元素到變數x(第7行)。顯示「將x加到最後」(第8行)，將x加入到qu的最後(第9行)。取出qu的第一個元素到變數x (第10行)。顯示「將x加到最後」(第11行)，將x加入到qu的最後(第12行)。取出qu的第一個元素到變數x (第13行)。顯示「將x刪除」(第14行)。
第15行：顯示出最後一個號碼。
(d)程式效率分析
執行第6到14行程式碼，是程式執行效率的關鍵，此程式會不斷的從佇列qu刪除元素直到剩下一個元素為止，約執行3n次後會剩下一個元素，演算法效率大約為O(n)，n為輸入的編號個數。
5-2 堆疊(Stack)
堆疊(Stack)是後進來的元素先出去(Last In First Out，縮寫為LIFO)的資料結構，函式的遞迴呼叫使用系統堆疊進行處理，因為遞迴的過程中最後呼叫的函式要優先處理，系統會實作堆疊程式自動處理遞迴呼叫，不須自行撰寫堆疊。特定問題可能需要使用堆疊進行實作，例如：程式的括弧配對檢查，右大括號配對最接近未使用的左大括號，將左大括號加進堆疊中，一遇到右大括號就從堆疊中取出一個左大括號配對。實作堆疊的部分，可以自行撰寫堆疊程式，或使用串列(list)實作程式不須知道內部程式如何實作，只要知道如何在串列(list)中新增與刪除資料。
5-2-1-自己實作堆疊
(a)範例說明
實作一個程式，將數字1到4依序加入堆疊，每加入一個數字後，顯示堆疊目前所有元素到螢幕上。最後刪除最上面的元素，接著顯示堆疊目前所有元素到螢幕上。
(b)預期程式執行結果
以下顯示上述程式從堆疊st中執行新增與刪除元素時，程式中top的變化，可以了解top的用途。
Step1)開始堆疊st是空的，top為-1。
對應程式如下。
self.top = -1
Step2)堆疊st插入一個元素，top遞增1後，top改成0，將元素1插入堆疊st的top所指定的位置。
對應程式如下。
self.top = self.top + 1
self.data[self.top] = x
Step3)堆疊st插入一個元素，top遞增1後，top改成1，將元素2插入堆疊st的top所指定的位置。
Step4)堆疊st插入一個元素，top遞增1後，top改成2，將元素3插入堆疊st的top所指定的位置。
Step5) 堆疊st插入一個元素，top遞增1後，top改成3，將元素4插入堆疊st的top所指定的位置。
Step6)從堆疊st刪除最上面的元素，top遞減1後，top改成2，數值4還是存在，只是top往下移了一格。
對應程式如下。
item = self.data[self.top]
self.top = self.top - 1
return item
堆疊完整程式如下。
第1到26行：定義類別Stack。
第2到5行：定義初始化方法(__init__)內宣告size用於儲存堆疊的大小，data用於儲存堆疊內元素，每個元素設定為0，總共有size個，設定top為-1。
第6到7行：定義isFull方法，檢查堆疊是否滿了，回傳top是否等於size-1。
第8到9行：定義isEmpty方法，檢查堆疊是否空了，回傳top是否等於-1。
第10到15行：定義push方法，若呼叫方法isFull回傳True，表示堆疊滿了，不能再插入資料，顯示「堆疊已滿」(第11到12行)；否則先將top遞增1，再儲存數字x到串列data的top位置(第13到15行)。
第16行到第22行：定義pop方法，呼叫方法isEmpty回傳True，表示堆疊是空的，顯示「堆疊是空的」(第17到18行)；否則先回傳陣列data索引值為top的數值到變數item，再將top遞減1，最後回傳變數item(第19到22行)。
第23到26行：定義printStack函式，印出堆疊內所有元素。
第27行：宣告st為五個元素的堆疊。
第28到30行：使用迴圈依序插入1、2、3與4到堆疊st，每插入一個數字就顯示目前堆疊st所儲存的元素。
第31到33行：使用迴圈執行五次，刪除目前堆疊st最上面的元素(第32行)，刪除第一個元素後，顯示目前堆疊st所儲存的元素(第33行)。
5-2-2 使用串列實作堆疊
(a)範例說明
實作一個程式，將數字1到4依序加入堆疊，依序取出每一個元素顯示在螢幕上，直到堆疊為空的為止。
(b)預期程式執行結果
使用串列實作堆疊的完整程式
第1行：設定陣列st為空串列。
第2到4行：將1到5依序加入到陣列st，每加入一個數字，就呼叫print印出串列st。
第5到6行：使用迴圈執行5次，每次呼叫pop取出最後一個元素，接著印出串列st的剩餘元素。
5-2-3 括弧的配對
(a)範例說明
給定由左大括弧({)或右大括弧(})所組成的字串，將此字串放在一行內，請判斷所有左大括號或右大括號能否配對成功，左大括號配對最接近的右大括號，左大括號在左，右大括號在右，若能全部配對成功，則顯示配對成功的數量，否則顯示「配對失敗」，字串長度小於1000個字元。
輸入說明
輸入一行由左大括弧({)或右大括弧(})所組成的字串，字串長度小於1000個字元。
輸出說明
若能全部配對成功，則顯示配對成功的數量，否則顯示「配對失敗」。
(b)預期程式執行結果
(c)說明與程式
右大括號須找最接近的左大括號，使用堆疊暫存左大括號，遇到右大括號，就取出堆疊內左大括號，遇到最後一個的右大括號，堆疊有剛好只剩一個左大括號，就配對成功，輸出配對的數量，否則輸出「配對失敗」。
第1行：使用函式input輸入一行字串到變數s。
第2行：宣告st為串列。
第3行：宣告變數pair為0。
第4到13行：使用for迴圈，迴圈變數i由0到len(s) -1，每次遞增1，取出字串的每個元素。若s[i]等於「{」，加入到堆疊st(第5到6行)；若s[i]等於「}」(第7行)，接著判斷堆疊st的元素個數是否大於0，若是則堆疊st取出最上面的元素(一定是最接近的左大括號)與右大括號配對，變數pair遞增1(第8到10行)，否則pair設定為-1，表示配對失敗，終止迴圈(第11到13行)。
第14到17行：若堆疊st的元素個數等於0且pair大於等於0，則顯示「共有」pair「對的大括號」；否則顯示「配對失敗」。
(d)程式效率分析
執行第4到13行程式碼，是程式執行效率的關鍵，此程式需掃描所有字元一次，演算法效率大約為O(n)，n為輸入的左大括號與右大括號的字元長度。
5-2-4 後序運算
(a)範例說明
數學運算式為中序運算式，例如：「3+2*5-9」是中序運算式，因為運算子(+,-,*,/)介於數字的中間。若轉成後序運算式，則因為先乘除後加減，所以後序運算式為「3 2 5 * + 9 -」，運算子移到數字的後面，將中序運算式轉成後序運算式，就可以使用堆疊進行運算。
運算原理如下：如果遇到數字就加入堆疊，遇到運算子(+,-,*,/)就從堆疊中取出兩個數字進行運算，結果回存堆疊，運算到後序運算式全部執行完成後，會剩下一個數字在堆疊內就是答案。
輸入說明
輸入後序運算式。
輸出說明
輸出後續運算的結果。
(b)預期程式執行結果
(c)說明與程式
以「3 2 5 * + 9 -」為例，進行後序運算式與堆疊的關係，本題從使用堆疊實作程式。
Step1)依序將數字加入3、2與5加入堆疊中。
Step2)遇到「*」，將堆疊最上面的兩個元素5與2取出，2乘以5得到10後，將10加入堆疊中。
Step3)遇到「+」，將堆疊最上面的兩個元素10與3取出，3加上10得到13後，將13加入堆疊中。
Step4)遇到「9」，將9加入堆疊中。
Step5)遇到「-」，將堆疊最上面的兩個元素9與13取出，13減去9得到4後，將4加入堆疊中。
Step6)到此已經處理完後序運算式「3 2 5 * + 9 -」，堆疊只有一個數字4，4就後序運算式「3 2 5 * + 9 -」(轉成中序運算式為「3+2*5-9」)的答案。
第1行：使用函式input輸入一行字串，並使用函式split分割字串，儲存到串列s。
第2行：宣告st為串列。
第3到21行：使用迴圈依序取出串列s的每一個元素。
第4到7行：若s[i]等於「+」，從堆疊st取出最上面元素到x(第5行)，從堆疊st取出最上面元素到y(第6行)，連續取出兩個元素後，將y加上x的結果儲存到堆疊st的最上面(第7行) 。
第8到11行：否則若s[i]等於「-」，從堆疊st取出最上面元素到x(第9行)，從堆疊st取出最上面元素到y(第10行)，連續取出兩個元素後，將y減去x的結果儲存到堆疊st的最上面(第11行)。
第12到15行：否則若s[i]等於「*」，從堆疊st取出最上面元素到x(第13行)，從堆疊st取出最上面元素到y(第14行)，連續取出兩個元素後，將y乘以x的結果儲存到堆疊st的最上面(第15行)。
第16到19行：否則若s[i]等於「/」，從堆疊st取出最上面元素到x(第17行)，從堆疊st取出最上面元素到y(第18行)，連續取出兩個元素後，將y除以x的結果儲存到堆疊st的最上面(第19行)。
第20到21行：否則就是數字，s[i]回存到堆疊st的最上面(第21行)。
第22行：顯示堆疊st的最上面元素就是答案。
(d)程式效率分析
執行第3到21行程式碼，是程式執行效率的關鍵，此程式會不斷輸入後序運算式到堆疊內，直到後序運算是全部都處理過，演算法效率大約為O(n)，n為後序運算式的數字與運算子的總個數。
Page updated
Google Sites
Report abuse