八、數(shù)據(jù)結(jié)構(gòu)不一定很枯燥

正如我現(xiàn)在實習(xí)的公司的一個同事說的那樣，數(shù)據(jù)結(jié)構(gòu)是一本催眠的書，我想對于大多數(shù)人應(yīng)該是這樣的，當(dāng)然對我也是，看著一大堆的算法，結(jié)構(gòu)模型，不想睡覺那應(yīng)該可以歸結(jié)為geek一類的，但是呢，后來我找到了一個辦法，就是動手，我發(fā)現(xiàn)無論看的時候有多無聊，寫寫程序所帶來的那種興奮感和成就感現(xiàn)在已經(jīng)成為了支撐看完我一本書的精神動力，所以我想在我開始從堆棧到圖的過程中，我盡我所能讓所寫的程序有更大的互動性，由于我的目的是能夠讓一些初學(xué)者對于編程寫代碼更感興趣，而且我這水平也只能給初學(xué)者提供一點我以前學(xué)習(xí)的經(jīng)驗了，我本來想用MFC，用圖形化界面來增加交互性的，后來我發(fā)現(xiàn)對于一個沒有學(xué)過MFC的人，如果想很簡短的說清楚還是很難的，所以我只能盡我所能在DOS的黑屏下開發(fā)出一些交互性來了。我始終相信最簡單的東西才是最根本的，DOS界面雖然簡陋，沒有界面，更不可能有WPF這些技術(shù)做出來的更炫更好的界面，但是往往就是這種簡陋的界面才能更容易讓人去重視本質(zhì)和核心的東西。雖然說我是想能夠提供更多的交互性，但是畢竟本人水平有限，加上思維僵化，所以我盡我最大的努力好了。

九、你不能小看任何簡單的東西

      堆棧，稍微對數(shù)據(jù)結(jié)構(gòu)有點了解的人，都會覺得這個結(jié)構(gòu)太簡單了，其模型就是先進后出，可以想象成為一摞盤子，盤子一個疊一個的，在正常情況下，你會永遠(yuǎn)往上摞盤子并且從上面取盤子，這樣抽象出來的一個結(jié)構(gòu)大體可以稱之為堆棧。如果你玩過三國殺，你被樂不思蜀了，這時候閃電輪到了你的頭上，先判斷樂不思蜀還是閃電？根據(jù)規(guī)則是后來的先判，于是翻牌判斷閃電，然后樂不思蜀。這也就是一個堆棧啊！這個結(jié)構(gòu)廣泛的應(yīng)用于我們生活中，同時也廣泛的應(yīng)用于計算機中，電腦程序之所以能夠運行，如果沒有堆棧這個結(jié)構(gòu)是不行的，你寫的函數(shù)能夠正確的被調(diào)用，沒有堆棧的幫助也是不可以的。所以說，看起來不起眼的結(jié)構(gòu)往往最實用，雖然結(jié)合堆棧的算法相比使用圖進行的算法要簡單的多，但是就實際運用來說，人們總是會選那些簡單，實用，高效的東西。對堆棧的學(xué)習(xí)不僅僅是對數(shù)據(jù)結(jié)構(gòu)整個的一個啟蒙而且更是了解數(shù)據(jù)結(jié)構(gòu)到底在實際中有多大應(yīng)用的一個起點，大學(xué)學(xué)的幾門基礎(chǔ)課，我覺得如果你想成為一個工程師，那么你用到最多的三門課應(yīng)該是數(shù)據(jù)結(jié)構(gòu)，計算機網(wǎng)絡(luò)和操作系統(tǒng)。

      那么，如何實現(xiàn)這樣一個先進后出的結(jié)構(gòu)呢？首先，堆?？隙ㄊ且环N集合，一種具有特殊性質(zhì)的集合，那么很自然的想到利用數(shù)組來實現(xiàn)，比方說我們有一個20個長度的數(shù)組a，我們將第一個數(shù)放在索引為0的位置上，現(xiàn)在第二個數(shù)，我們將第一個數(shù)向后挪一位，挪到a[1],然后將新數(shù)放到a[0],依次類推，這樣取數(shù)的時候永遠(yuǎn)取a[0]的數(shù)，然后將后面的數(shù)前移，這樣就能達到一個先進去的數(shù)最后才能取到的目的。但是這種實現(xiàn)方案的最大的缺點是你每次都要移動數(shù)組，這對計算機所造成的開銷是非常大的，特別是對數(shù)組這樣一個效率很低的結(jié)構(gòu)（別小看數(shù)組，數(shù)組也是一種數(shù)據(jù)結(jié)構(gòu)）。那么，我們可不可以有所改進呢？可以很自然的想到如果我將每次新進來的元素都放在數(shù)組的末尾，也就是每次都在數(shù)組的最末尾添加元素，那樣對于插入操作的效率是最快的，那就將到來的數(shù)依次從0插入，如果需要取數(shù)的話，那么永遠(yuǎn)從最后一個數(shù)開始取，同時用一個變量標(biāo)示數(shù)組中實際有多少元素，無疑，這樣對于效率的提高是非常大的。還有沒有更大的效率的實現(xiàn)方式呢？當(dāng)然，使用指針，永遠(yuǎn)記住，指針是一個很好的工具，如果你所做的是大型的系統(tǒng)，那么良好的使用指針?biāo)鶐淼男实奶岣呤菚屇愀械襟@奇的一件事。對于使用指針實現(xiàn)的堆棧，我準(zhǔn)備下一節(jié)再寫。

      好，基本思路確定了，那么我們就開始寫了（這里我默認(rèn)你已經(jīng)懂得C++基本知識，不然你也不會看數(shù)據(jù)結(jié)構(gòu)了），但是我們還發(fā)現(xiàn)一個問題，如果使用數(shù)組，那么我怎么知道我要用的堆棧有多大？這個解決的辦法很多，第一個就是申明一個很大的數(shù)作為這個數(shù)組的大小，但是很大是多大？永遠(yuǎn)有比很大更大的數(shù)，更不用說這樣做導(dǎo)致的內(nèi)存浪費，可能在你平時編寫小程序的時候，你無法體會到內(nèi)存浪費對于一個程序員深深地痛，另外一個痛是內(nèi)存泄露，所以有些東西還是先培養(yǎng)出一種習(xí)慣比較好的。第二個就是使用指針動態(tài)申請數(shù)組的大小，這樣的話，我們需要一個含有參數(shù)的構(gòu)造函數(shù)（如果你不知道什么叫構(gòu)造函數(shù)的話，那么。。。那么。。。那么你可以關(guān)了這個界面，不過我的打算是把數(shù)據(jù)結(jié)構(gòu)寫完了，寫介紹基礎(chǔ)C++的文章，那個時候你可以再來看看），這個參數(shù)你要申明的數(shù)組的大小。

     對于堆棧這個類的成員函數(shù)（突然覺得專業(yè)名詞好多？其實你可以去學(xué)學(xué)C++），添加元素的專業(yè)叫法是push（壓），取出元素的專業(yè)叫法是pop(彈出),你可以想象那種前幾年流行過的一種存硬幣的圓柱狀物品，你可以把硬幣一個一個壓入那里面，然后彈出最上面的硬幣。除了這兩個，還可以有的是檢查堆棧是否為空，返回棧頂元素（不彈出）和返回堆棧大小，為了增加交互性和盡量簡單，我的實現(xiàn)里加入了一個遍歷堆棧元素的成員函數(shù)（這個是不好的，違背了堆棧的原理）。那么好，先看看.h文件。

#ifndef STACK_H 
 #define STACK_H 
 class Stack{ 
 public : 
     Stack(int size); 
     ~Stack(); 
  
     void Push(int ele); 
     int Pop(); 
     int Top(); 
     int GetValue(int Pos); 
     bool CheckEmpty(); 
     int GetCount(); 
  
 private: 
     int *stackArray; 
       
     int count; 
 }; 
 #endif 

      .h文件我的理解對于初學(xué)者可以將它看做一個索引，它讓你看看一個類里大概有什么東西?？赐晁饕旅婵纯此膬?nèi)容吧。

Stack::Stack(int size) 
 { 
     stackArray=new int[size]; 
     for(int i=0;i<size;i++) stackArray[i]=0; 
     count=0; 
 } 
  
 Stack::~Stack() 
 { 
     delete []stackArray; 
 } 
  
 bool Stack::CheckEmpty() 
 { 
     return (count==0); 
 } 
  
 void Stack::Push(int ele) 
 { 
     stackArray[count]=ele; 
     ++count; 
 } 
  
 int Stack::Pop() 
 { 
     --count; 
     int result=stackArray[count]; 
     stackArray[count]=0; 
     return result; 
 } 
  
 int Stack::GetValue(int Pos) 
 {      
     return stackArray[count-Pos-1]; 
 } 
  
   
  
  
 int Stack::GetCount()  
 { 
     return count; 
 } 

     對于壓入我采用的是往數(shù)組的后面添加元素的方法，彈出是的話是將最后一個元素返回，然后設(shè)為0，同時堆棧的大小減一。同時，請大家注意，我的實現(xiàn)里面沒有加入一些對于錯誤情況的判斷，比如如果已經(jīng)沒有元素了，那么彈出是不允許的，如果元素已經(jīng)滿了，那么壓入也是不允許的，這個部分我真心是想留給初學(xué)者做個練習(xí)，當(dāng)然，如果你有興趣的話。還有就是目前實現(xiàn)的堆棧只能壓入整數(shù)，我沒有使用模板或者typedef是因為我想還是簡單點比較好。

     在大多數(shù)數(shù)據(jù)結(jié)構(gòu)書里面堆棧應(yīng)用舉例就是隨機生成多少個數(shù)，然后壓入，彈出，看看輸出結(jié)果是什么，我想的話，其實可以使用一個菜單，讓使用者每次選壓入還是彈出，然后觀看變化，所以我想了這樣兩個函數(shù)。

void printCube(int num) 
{ 
    cout<<"   "<<num<<"   "<<endl; 
    cout<<"*******"<<endl;  
} 
 
void menu() 
{ 
    cout<<"Please select one operation:"<<endl; 
    cout<<"1-Push"<<endl; 
    cout<<"2-Pop"<<endl; 
    cout<<"0-Quit"<<endl; 
} 

     當(dāng)然，你可以在我的基礎(chǔ)上擴展，那么主函數(shù)如下所示：

void main() 
 { 
         int order,input; 
     menu(); 
      int size=20; 
       Stack s(size); 
     while(cin>>order) 
     { 
       if(order==1) 
       { 
          cin>>input; 
          s.Push(input); 
       } 
       if(order==2) 
           s.Pop(); 
       if(order==0) 
           break; 
  
       for(int i=0;i<s.GetCount();i++) 
            printCube(s.GetValue(i)); 
     } 
   
     int i; 
     cin>>i; 
      
 } 

     首先，主函數(shù)做一些輔助工作，打印出選擇菜單，然后我們申請一個大小為20的堆棧，等待用戶的輸入，初始界面如下：

     有兩個命令，1是壓入，2是彈出，那么我們來試一試吧，我們連續(xù)壓入兩個數(shù)，按下1，然后再按一個數(shù)，效果如下：

     可以看到3在2的上面，就像疊的盤子一樣，再彈出一個數(shù)試試。

     可以看到堆棧中最上面的數(shù)已經(jīng)被彈出了，這就是一個簡單的堆棧，另外，后面的代碼越來越大，我想將代碼打包上傳，這樣下載完整的代碼包可以保證整體性，對初學(xué)者更有幫助，想問問大家我應(yīng)該往哪傳?。?/p>

原文鏈接：http://www.cnblogs.com/ZXYloveFR/archive/2012/09/29/2707999.html

【編輯推薦】