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

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

九、你不能小看任何簡(jiǎn)單的東西

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

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

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

     對(duì)于堆棧這個(gè)類的成員函數(shù)（突然覺得專業(yè)名詞好多？其實(shí)你可以去學(xué)學(xué)C++），添加元素的專業(yè)叫法是push（壓），取出元素的專業(yè)叫法是pop(彈出),你可以想象那種前幾年流行過的一種存硬幣的圓柱狀物品，你可以把硬幣一個(gè)一個(gè)壓入那里面，然后彈出最上面的硬幣。除了這兩個(gè)，還可以有的是檢查堆棧是否為空，返回棧頂元素（不彈出）和返回堆棧大小，為了增加交互性和盡量簡(jiǎn)單，我的實(shí)現(xiàn)里加入了一個(gè)遍歷堆棧元素的成員函數(shù)（這個(gè)是不好的，違背了堆棧的原理）。那么好，先看看.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文件我的理解對(duì)于初學(xué)者可以將它看做一個(gè)索引，它讓你看看一個(gè)類里大概有什么東西?？赐晁饕?，下面看看他的內(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; 
 } 

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

     在大多數(shù)數(shù)據(jù)結(jié)構(gòu)書里面堆棧應(yīng)用舉例就是隨機(jī)生成多少個(gè)數(shù)，然后壓入，彈出，看看輸出結(jié)果是什么，我想的話，其實(shí)可以使用一個(gè)菜單，讓使用者每次選壓入還是彈出，然后觀看變化，所以我想了這樣兩個(gè)函數(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ǔ)上擴(kuò)展，那么主函數(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ù)做一些輔助工作，打印出選擇菜單，然后我們申請(qǐng)一個(gè)大小為20的堆棧，等待用戶的輸入，初始界面如下：

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

     可以看到3在2的上面，就像疊的盤子一樣，再?gòu)棾鲆粋€(gè)數(shù)試試。

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

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

【編輯推薦】