#5 資料結構 - Stack - part 1

還記得以前工作時曾有個一個經驗.有一天,我到同事的辦公室閒聊,聊著聊著他就跟我說他正在做一個新功能,當時我們正在做 Windows desktop應用程式,在這個程式裡面有一個編輯功能的頁面,讓使用者可以輸入產品的許多資料,而我同事正在做的就是為每個編輯動作留下記錄,好讓他可以做出 "undo" 的功能,而且要能一直 "undo" 下去.接著,他展現給我看他的成果,一切都運作的蠻好.接著,我就很好奇問他程式碼是怎麼寫的,接著他就展示相關的程式碼給我,他用了一個 .Net 的 DataTable,然後在這個 DataTable 裡建立了相關的欄位,如動作的序號,資料名稱,資料內容.因此,只要使用者一變動了某一個資料後,這個 DataTable 裡就會多了一筆資料,當使用者執行 "undo" 時,就會從這個 DataTable 裡尋找最大的序號,讀出該序號的資料並且更新 UI,然後將這筆資料從 DataTable 中刪除.如果這是你要做的功能,你會怎樣做呢?

聽完他的解釋之後,我滿臉的疑問馬上問他,你做了這麼多東西,你不覺得累嗎? 你為什麼不用 Stack 呢? 你知道什麼是 Stack 吧! (因為他是數學系畢業的,我怕他不知道什麼是 Stack) 其實,我倒也不怎麼在乎他如何去實做這功能,只是想到未來有一天我和他都會離開這份工作,總有一天這些程式碼都會交給後面的人繼續開發和維護,我常在想如何未來的工程師們看到這樣的實作方式,不知道他們容不容易懂.

其實,像這樣的功能很常遇到,用 Stack 就對了.人們常說 "凡走過必留下痕跡",而在軟體世界裡,用 Stack 來留下痕跡就相對地輕鬆.為什麼比較輕鬆呢? 原因很簡單,抽象上來說 Stack 只提供兩種方法,一個是 push (放物件進去),另一個 pop (把物件拿出來),而最後放進去的物件將會是第一個被拿出來的.以上述我那位同事的例子來說,如果他用 Stack,那麼他根本不用去管理序號,也不用在 DataTable 裡去尋找最大的序號,也不用做讀出來的資料在 DataTable 裡刪除,因為 Stack 都幫他做了這些工作.

如果你的工作是程式設計相關,我相信你一定知道什麼是 Stack,這一個基本的資料結構在各大平台與作業系統中都會提供,當然在 java 和 .net 平台也有.接下來,我們討論一下 Stack 是什麼做的? 如果你沒看過 Stack 的實做,先思考一下,如果今天你的工作是寫出一個 Stack,你打算怎麼做呢? Stack 最基本的要求就是可以寫入物件,也可以讀出物件,但是物件的寫入讀取順序一定要按照先進後出,也就是後進先出的方式來進行.因此,我們首先可以想像的是 Stack 一定像是一個容器一樣,因為它要可以容納物件,同時還要有一個管理的機制,好讓先寫入的物件在讀取出會被優先讀出去.如果你能想到這樣,就差不多完成了一半的思考.

待續...


Share: