資料結構會影響到程式的執行效率,須想清楚需要使用哪一種資料結構,為何使用此資料結構。以下介紹佇列(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為後序運算式的數字與運算子的總個數。