一、堆疊
堆疊和佇列可看作是特 殊的線性表，它們是 運算受限的線性表
定義：堆疊是只能在表的一端（表尾）進行 插入和洗掉的線性表
- 允許插入及洗掉的一端（表尾）稱為堆疊頂(Top)； .
- 另一端（表頭）稱為堆疊底(Bottom)， .
- 當表中沒有元素時稱為空堆疊
- 進堆疊——在堆疊頂插入一元素；
- 出堆疊——在堆疊頂洗掉一元素
特點：后進先出
堆疊中元素按a1，a2，a3，…an的次序進堆疊，出堆疊的第一個元素應 為堆疊頂元素，換句話說，堆疊的修改是按后進先出的原則進行的， 因此，堆疊稱為后進先出線性表（LIFO），
堆疊的用途：常用于暫時保存有待處理的資料，
堆疊的基本操作
- （1）初始化堆疊：InitStack(S);
- （2）判堆疊空：EmptyStack (S);
- （3）進堆疊：Push (S,x);
- （4）出堆疊：Pop (S);
- （5）取堆疊頂： GetTop(S);
堆疊的分類：按照順序結構存盤是順序堆疊、按照鏈式結果存盤是鏈堆疊
二、順序堆疊
順序堆疊—— 即堆疊的順序實作；
堆疊容量——堆疊中可存放的最大元素個數；
堆疊頂指標 top——指示當前堆疊頂元素在堆疊中的位置；
堆疊空——堆疊中無元素時，表示堆疊空；
堆疊滿——陣列空間已被占滿時，稱堆疊滿；
下溢——當堆疊空時，再要求作出堆疊運算，則稱“下溢”；
上溢——當堆疊滿時，再要求作進堆疊運算，則稱“上溢”，
1、順序堆疊的型別定義
const int maxsize=6;typedef struct seqstack { DataType data[maxsize]; int top;}SeqStk;
SeqStk *s ; 定義一順序堆疊s
約定堆疊的第1個元素存在data[1]中,則
s->top==0 代表順序堆疊s為空；
s->top==maxsize-1 代表順序堆疊s為滿
2、初始化：
int Initstack(SeqStk *stk){ stk->top=0; return 1;}
3、判堆疊空（堆疊空時回傳值為1，否則回傳值為0）
int EmptyStack(SeqStk *stk){ if(stk->top= =0) return 1; else return 0;}
4、進堆疊
int Push(SeqStk *stk, DataType x){ /*資料元素x進順序堆疊sq*/ if（stk->top==maxsize -1) /*判是否上溢*/ { error(“堆疊滿”);return 0;} /*上溢*/ else { stk->top++；/*修改堆疊頂指標，指向新堆疊頂*/ stk->data[stk->top]=x; /*元素x插入新堆疊頂中*/ return 1; } }}
5、出堆疊
int Pop(SeqStk *stk){ /*順序堆疊sq的堆疊頂元素退堆疊*/ if(stk->top==0) /*判是否下溢*/ { error(“堆疊空”);return 0;} /*下溢*/ else { stk->top-- ； /*修改堆疊頂指標，指向新堆疊頂*/ return 1; }}/*Pop*/
6、取堆疊頂元素
DataType GetTop(SeqStk *stk){if(EmptyStack(stk))return NULLData;elsereturn stk->data[stk->top];}
三、鏈堆疊
鏈堆疊的定義： 堆疊的鏈式存盤結構稱為鏈堆疊，它是運算受限的單鏈表， 插入和洗掉操作僅限制在表頭位置上進行，堆疊頂指標就是鏈 表的頭指標
1、初始化
void InitStack(LkStk *LS){ LS=(LkStk *)malloc(sizeof(LkStk)); LS->next=NULL;}
2、判堆疊空
int EmptyStack(LkStk *LS){ if(LS->next= =NULL) return 1; else return 0;}
3、進堆疊——在堆疊頂插入一元素x
void Push (LkStk *LS, DataType x){ LkStk *temp; temp= (LkStk *) malloc (sizeof (LkStk)); temp->data=https://www.cnblogs.com/jalja/p/x; temp->next=LS->next; LS->next=temp;}
4、出堆疊——在堆疊頂洗掉一元素，并回傳
int Pop (LkStk *LS){ LkStk *temp; if (!EmptyStack (LS)) { temp=LS->next; LS->next=temp->next; free(temp); return 1; } else return 0;}
5、取堆疊頂元素
DataType GetTop(LkStk *LS){ if (!EmptyStack(LS)) return LS->next->data; else return NULLData;}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/39828.html
標籤：架構設計
上一篇：高德億級流量接入層服務的演化之路