数据结构-栈详解（类C语言版）
目錄
棧的定義
概念
棧的抽象數(shù)據(jù)類型定義
順序棧的基本操作
?存儲方式
順序棧的表示
順序棧的初始化
順序棧判斷是否為空
清空順序棧
?銷毀順序棧
順序棧的入棧
順序棧的出棧
?取順序棧的棧頂元素
鏈棧的基本操作
鏈棧的表示
鏈棧的初始化
判斷鏈棧是否為空
鏈棧的入棧
鏈棧的出棧
取棧頂元素
棧與遞歸
分治法求解遞歸問題算法的一般形式
尾遞歸轉(zhuǎn)變?yōu)檠h(huán)結(jié)構(gòu)
單向遞歸轉(zhuǎn)變?yōu)檠h(huán)結(jié)構(gòu)
棧的定義
概念
棧 (stack) 是限定僅在表尾進(jìn)行插入或刪除操作的線性表。 因此， 對棧來說， 表尾端有其特殊含義， 稱為棧頂 (top), 相應(yīng)地， 表頭端稱為棧底 (bottom)。 不含元素的空表稱為空棧。
棧又稱為后進(jìn)先出 (Last In First Out, LIFO) 的線性表。
棧的抽象數(shù)據(jù)類型定義
ADT Stack {
數(shù)據(jù)對象：
? ? ? ? D = {ai | ai?∈ElemSet , i = 1,2,...,n,n≥0 }
數(shù)據(jù)關(guān)系：
? ? ? ? R1 = { <ai-1, ai > | ai-1, ai ∈ D, i=2,...,n }
? ? ? ? 約定an端為棧頂，a1端為棧底。
基本操作：初始化、進(jìn)棧、出棧、取棧頂元素等
}ADT Stack
順序棧的基本操作
?存儲方式
同一般線性表的順序存儲結(jié)構(gòu)完全相同。
利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。棧底一般在低地址端。
·?附設(shè)top指針，指示棧頂元素在順序棧中的位置。
·?另設(shè)base指針，指示棧底元素在順序棧中的位置。
（但是，為了方便操作，通常top指示真正棧頂元素之上的下標(biāo)地址。）
·?另外，用stacksize表示棧可使用的最大容量。
?空棧：base==top是棧空標(biāo)志。
棧滿：top-base==stacksize。
?下圖所示棧中元素和棧指針之間的關(guān)系
順序棧的表示
#define MAXSIZE 100 typedef struct {SElemType *base; // 棧底指針SElemType *top; // 棧頂指針int stacksize; // 棧可用最大容量 } SqStack;順序棧的初始化
Status InitStack(SqStack &S) { // 構(gòu)造一個(gè)空棧S.base = new SElemType[MAXSIZE]; // 或S.base = (SElemType*)malloc(MAXSIZE*sizeof(SelemType));if (!S.base) exit(OVERFLOW); // 存儲分配失敗S.top = S.base; // 棧頂指針等于棧底指針S.stacksize = MAXSIZE;return OK; }順序棧判斷是否為空
棧頂指針等于棧底指針，就認(rèn)為順序棧為空
Status StackEmpty(SqStack S) {// 若棧為空，返回TRUE;否則返回FALSE if (S.top == S.base)return TRUE;elsereturn FALSE; }?
清空順序棧
清空順序棧就是將棧頂指針移到棧底指針。
Status ClearStack(SqStack S) {if(S.base) S.top = S.base;return OK; }?銷毀順序棧
Status DestroyStack(SqStack &S) {if(S.base) {delete S.base;S.stacksize = 0;S.base = S.top = NULL;}return OK; }順序棧的入棧
①?判斷是否棧滿，若滿則出錯(cuò)（上溢）。
②?元素e壓入棧頂。
③?棧頂指針加1。
Status Push(SqStack &S, SElemType e) {if(S.top - S.base == S.stacksize) // 棧滿return ERROR;*S.top++=e; // 可以分開寫，*S.top=e;S.top++;return OK; }順序棧的出棧
①?判斷是否棧空，若空則出錯(cuò)（下溢）。
②?獲取棧頂元素e。
③?棧頂指針減1。
Status Pop(SqStack &S, SElemType &e) {// 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERRORif(S.top == S.base) // 等價(jià)于if(StackEmpty(S))return ERROR;e = *--S.top; // 可分解為兩步--S.top; e = *S.top;return OK; }?取順序棧的棧頂元素
SElemType GetTop(SqStack S) {// 返回S的棧頂元素，不修改棧頂指針if(S.top != S.base) // 棧非空return *(S.top-1) // 返回棧頂元素的值，棧頂指針不變 }鏈棧的基本操作
鏈棧的表示
鏈棧是運(yùn)算受限的單鏈表，只能在鏈表頭部進(jìn)行操作。
·?鏈表的頭指針就是棧頂。
·?不需要頭結(jié)點(diǎn)。
·?基本不存在棧滿的情況。
·?空棧相當(dāng)于頭指針指向空。
·?插入和刪除僅在棧頂處執(zhí)行。
注意：鏈棧中的指針方向。
typedef struct StackNode {SElemType data;struct StackNode *next; } StackNode, *LinkStack; LinkStack S;鏈棧的初始化
void InitStack(LinkStack &S) {// 構(gòu)造一個(gè)空棧，棧頂指針置為空S=NULL;return OK; }判斷鏈棧是否為空
Status StackEmpty(LinkStack S) {if(S==NULL) return TRUE;else return FALSE; }鏈棧的入棧
Status Push(LinkStack &S, SElemType e) {p = new StackNode; // 生成新結(jié)點(diǎn)pp -> data = e; // 將新結(jié)點(diǎn)數(shù)據(jù)域置為ep -> next = S; // 將新結(jié)點(diǎn)插入棧頂S = p; // 修改棧頂指針return OK; }鏈棧的出棧
Status Pop(LinkStack &S, SElemType &e) {if (S == NULL) return ERROR;e = S -> data;p = S;S = S -> next;delete p;return OK; }取棧頂元素
SElemType GetTop(LinkStack S) {if (S != NULL)return S -> data; }棧與遞歸
分治法求解遞歸問題算法的一般形式
void p (參數(shù)表) {if(遞歸結(jié)束條件) 可直接求解步驟; ----- 基本項(xiàng)else p(較小的參數(shù)); -----歸納項(xiàng) }例如
long Fact(long n) {if(n == 0) return 1; // 基本項(xiàng)else return n * Fact(n-1); // 歸納項(xiàng) }尾遞歸轉(zhuǎn)變?yōu)檠h(huán)結(jié)構(gòu)
long Fact(long n) {if(n == 0) return 1;else return n * Fact(n-1); }以上遞歸可以寫成循環(huán)結(jié)構(gòu)
long Fact(long n) {t = 1;for(i = 1; i <= n; i++) t = t*i;return t; }單向遞歸轉(zhuǎn)變?yōu)檠h(huán)結(jié)構(gòu)
雖然有一處以上的遞歸調(diào)用語句，但各次遞歸調(diào)用語句的參數(shù)只和主調(diào)函數(shù)有關(guān)，相互之間參數(shù)無關(guān)，并且這些遞歸調(diào)用語句處于算法的最后。
long Fib(long n) { // Fibonacci數(shù)列if(n==1||n==2) return 1;else return Fib(n-1) + Fib(n-2); }?轉(zhuǎn)換為循環(huán)結(jié)構(gòu)
long Fib(long n) {if(n==1||n==2) return 1;else {t1 = 1; t2 = 1;for(i=3;i<=n;i++){t3=t1+t2;t1=t2;t2=t3;}return t3;} }總結(jié)
以上是生活随笔為你收集整理的数据结构-栈详解（类C语言版）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java加载一个来自项目之外的java文
- 下一篇： 数据结构-队列详解（类C语言版）