??本章我們介紹有關堆疊的知識，堆疊的重點在于順序存盤，鏈式存盤及其特點，
1.堆疊的基本概念
（1）堆疊的定義
??堆疊是只允許在一端進行插入和洗掉的線性表，有一個堆疊頂和堆疊底，堆疊頂是允許插入和洗掉的那一端，堆疊底是不允許插入和洗掉的那一端，如果一個堆疊不包括任何元素，就是一個空表也就是空堆疊，
??堆疊的特點是先進先出，
(2)堆疊的基本操作
??堆疊的基本操作包括下面六種：
??InitStack(&S)：初始化一個空堆疊S，
??StackEmpty(S)：判斷一個堆疊是否為空，
??Push(&S,x)：進堆疊，若堆疊未滿，則將x加入使其成為新堆疊頂，
??Pop(&S,&x)：出堆疊，若堆疊非空，則彈出堆疊頂元素，并用x回傳，
??GetTop(S,&x)：得到堆疊頂元素，若堆疊S非空，則用x回傳堆疊頂元素，
??DestoryStack(&S)：銷毀堆疊，并釋放堆疊S占用的存盤空間("&"表示參考呼叫)，
2.堆疊的順序存盤結構
??堆疊是一種特殊的線性表，有兩種存盤方式，這里先介紹順序存盤結構，
(1)順序堆疊的實作
??采用順序存盤的堆疊叫做順序堆疊，它用一組地址連續的存盤單元存放自堆疊底到堆疊頂的資料元素，同時附設一個指標top指示當前堆疊頂元素的位置，
??堆疊的順序存盤型別定義為：
#define MaxSize 50 //定義堆疊中元素的最大個數
typedef struct{
ElemType data[MaxSize]; //存放堆疊中的元素
int top; //堆疊頂指標
}SqStack
??要注意的是，初始時把堆疊頂指標S.top(S是SqStack的簡化)設定為-1或者0，堆疊頂元素為S.data[S.top]，
??進堆疊的時候，堆疊如果不滿，則先把堆疊頂指標加1，再把值送到堆疊頂元素位置，出堆疊的時候，堆疊如果非空，先取堆疊頂元素值，再將堆疊頂元素減1.
??如果初始時把堆疊頂指標S.top設定為-1，則判斷堆疊空的條件是S.top-1，堆疊滿的條件為S.topMaxSize-1，堆疊長是S.top+1，
??由于入堆疊操作受到陣列大小的限制，當對堆疊的最大使用空間估計不足的時候，有可能發生堆疊上溢，此時應該及時處理，避免出錯，
(2)順序堆疊的基本運算
??初始化順序堆疊
void InitStack(SqStack &S){
S.top = -1;
}
??堆疊空的判斷
bool StackEmpty(SqStack S){
if(S.top == -1)
return true;
else
return false;
}
??進堆疊
bool Push(SqStack &S,ElemType x){
if(S.top == MaxSize - 1)
return false;
S.data[++S.top] = x;
return true;
}
??出堆疊
bool Pop(SqStack &S,ElemType &x){
if(S.top == -1)
return false;
x = S.data[S.top--];
return true;
}
??讀堆疊頂元素
bool GetTop(SqStack S,ElemType &x){
if(S.top == -1)
return false;
x = S.data[S.top];
return true;
}
(3)順序堆疊的注意事項
??前面的順序堆疊的操作是在順序堆疊的堆疊頂指標S.top設定為-1時的演算法，如果把S.top設定為0，即top指向堆疊頂元素的下一個位置，則入堆疊操作變為S.data[S.top++] = x；出堆疊操作變為x = S.data[--S.top]，對應的堆疊空條件變為S.top = 0,堆疊滿條件為S.top = MaxSize，
3.堆疊的鏈式存盤結構
??采用鏈式存盤的堆疊稱為鏈堆疊，優點是便于多個堆疊共享存盤空間和提高其效率，且不存在堆疊滿上溢的情況，通常采用單鏈表實作，規定所有操作在單鏈表的表頭進行，相當于堆疊頂，這里設定鏈堆疊沒有頭結點，Lhead頭指標直接指向堆疊頂元素，站的鏈式存盤型別為：
typedef struct Linknode{
ElemType data;
struct Linknode *next;
}*LiStack;
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/656.html
標籤：其他
上一篇：D. Yet Another Problem On a Subsequence 決議(DP)
下一篇：二叉樹的遍歷遞回非遞回