資料結構──堆疊

　　說到堆疊(Stack)，大家應該都不陌生吧！所謂的堆疊呢，其實就是一種資料結構。這種資料結構有一個特點，就是只能從一端進行存入(Push)或讀取(Pop)。堆疊運作的方式是先在記憶體中配置連續的記憶體，從位址的前端開始，採用「先進後出」(First In Last Out,FILO)的方法來存取。也就是說，存入的資料是一層層「疊」在之前的資料後，等到要讀取時，再從後「疊」的往先「疊」的資料讀取。

　　好好，我知道你聽得霧煞煞，我也解釋得滿頭大汗，舉例來說好了，現在我有一個可以容納一百層的堆疊，我先寫入了五個，現在堆疊是五層了，我再讀取了兩個，現在是三層了，我又存入了四個，現在是七層了。進行的三次存取用圖解就是這樣：

剛　　　第　　　第　　　第
開　　　一　　　二　　　三
始　　　次　　　次　　　次

　　　　　　　　　　　　壬
　　　　　　　　　　　　辛
　　　　戊　　　　　　　庚
　　　　丁　　　　　　　己
空　→　丙　→　丙　→　丙
　　　　乙　　　乙　　　乙
　　　　甲　　　甲　　　甲

甲到壬分別代表不同的資料。

好了！談完理論，來實作吧！以下是用Ｃ++的類別(class)寫的：


template<class TYPE,unsigned int SIZE>
class stack{

private:

TYPE array[SIZE];
unsigned int position;

public:

stack(){position=0;}

bool push(TYPE input){
if(position<SIZE){
*(array+position)=input;
position++;
return true;}
return false;}

TYPE pop(void){
if(position>0){
position--;
return *(array+position);}
return false;}
};

我來解釋一下：
　　這個類別使用樣板(Template)，以達到可以應用在多種資料型態的目的。這個類別的成員變數(Member Variable)中，有一個陣列array，這個是用來配置一塊連續的記憶體，至於變數position，則是用來記錄堆疊中存了多少筆資料。成員函數(Member Function)push和pop中的判斷句是為了避免溢位(Overflow)用的，若是超過範圍則直接傳回假(false)，否則執行完畢後傳回真(true)。至於建構子(Constructor)所做的內容嘛，是讓堆疊的高度初始為零。

　　那麼，這個類別怎麼使用呢？

首先，宣告是一定要的：
stack<資料型態,堆疊大小> 堆疊變數名稱;
例如：
stack<int,1024> temp;


再來是存入一筆資料到堆疊中：
堆疊變數名稱.push(要寫入的資料);
例如：
temp.push(731);


當然啦，寫得進去也要讀的出來啊！讀取：
變數=堆疊變數名稱.pop();
例如：
int num;
num=temp.pop();


　　最後還要注意一下，若是堆疊滿了，寫入時會被忽略，並回傳false；若是堆疊空了，讀取時也是回傳false。

參考資料：維基百科

發文者：竹中軟研24^th教學