【原創】【自製系列】自製stack類型（泛型）
前言
自製類型的第三篇，stack類型。stack是指棧，其實我個人認為stack是最好寫的類型，沒有之一。關於queue類型需要涉及到循環隊列避免浪費記憶體，但是stack的插入刪除都是對於棧頂而言，比較好寫。
自製類型的主要目的，是為了練習數據結構，提高寫程式碼的能力。
常見函數
s.empty() 判斷棧s是否為空
s.size() 返回棧s的大小
s.push(a) 把a推入棧
s.pop() 彈出棧頂元素
s.top() 返回棧頂元素
泛型
我們在使用標準庫的stack，是這樣寫的：
stack<int> stk;
使用尖括弧指定類型，就是泛型的一種。如果把int改為char，甚至是結構體等，都可以。
最簡單的例子：
#include<iostream>
#include<vector>
using namespace std;
int main(){
int a=5,b=10;cout<<max(a,b);
float c=3.14,d=9.99;cout<<max(c,d);
char e='x',f='*';cout<<max(e,f);
}
這裡，max函數即可以處理int，又可以處理float,char類型的最大值。這就是泛型。max函數無論針對哪一個類型，操作都是相同的。因此，我們使用通用類型，讓函數不關注類型只關注具體的操作。
有人會問，其實使用函數重載不就能完成了嗎？但是，函數重載要重複寫好幾次，不方便。
泛型的函數，可以使用template關鍵字寫：
#include<iostream>
#include<vector>
using namespace std;
template<typename T>
T MAX(T a,T b){
if(a>b)return a;
else return b;
}
int main(){
int a=5,b=10;cout<<MAX(a,b);
float c=3.14,d=9.99;cout<<MAX(c,d);
char e='x',f='*';cout<<MAX(e,f);
}
template
執行的時候，編譯器會自動根據參數的類型，把T轉換為int,float等類型，進行計算。
注意，泛型的函數不會進行自動類型轉換，例如cout<<MAX('a',100);這個語句，如果使用的是泛型類型，會編譯錯誤，但是使用普通類型不會報錯，因為普通類型的函數會進行自動類型轉換。
泛型類的寫法：
template<typename T>
class Vector{
T *numbers;
};
（轉自我之前寫過的《自製vector類型》）
這樣，就可以像標準庫一樣定義了。
在類的函數中，對於參數和部分類變數，也需要把類型指定為T，在malloc和realloc的強制轉型中也是T*。
大體寫法
class Stack{
private:
T *Data;
int nData;
public:
Stack(){
Data=nullptr;
nData=0;
}
bool empty(){
if(nData==0)return true;
else return false;
}
int size(){
return nData;
}
void push(T a){
nData++;
if(Data==nullptr)Data=(T*)malloc(sizeof(T));
Data=(T*)realloc(Data,nData*sizeof(T));
Data[nData-1]=a;
}
void pop(){
if(nData==0)return;
nData--;
Data=(T*)realloc(Data,nData*sizeof(T));
}
T top(){
return Data[nData-1];
}
};
構造函數的寫法
將Data，nData初始化，變數的含義很簡單，不再多說。
empty
判斷棧的大小即可。如果大小為0，表示為空棧。
size
返回nData。
push
重頭戲
void push(T a){
nData++;
if(Data==nullptr)Data=(T*)malloc(sizeof(T));
Data=(T*)realloc(Data,nData*sizeof(T));
Data[nData-1]=a;
}
首先，把棧的大小加上1。然後，如果為空指針，就使用malloc分配（原來什麼都沒有），否則使用realloc分配。動態分配記憶體，可以節約記憶體空間。最後，把push的數值放入棧頂。
pop
pop的操作也很簡單。
void pop(){
if(nData==0)return;
nData--;
Data=(T*)realloc(Data,nData*sizeof(T));
}
pop操作需要對nData做特判，大小為零則直接退出，不然在分配時會出錯。
如果nData=0，那麼realloc的參數為0，相當於使用free(Data)。
top
返回棧頂元素Data[nData-1]。
