C語言實現數據結構-棧

01-25

棧是僅在表尾進行插入、刪除操作的線性表。即棧 S= (a1, a2, a3, ………,an-1, an)，其中表尾(即 an 端)稱為棧頂 /top，表頭(即 a1 端)稱為棧底/base。

由於只能在表尾進行操作，因此棧的運算規則就是「後進先出」(LIFO)

提起棧，最常見的用途就是調用函數了，例如JS裡面的執行棧，但是棧可以用於遞歸運算、簡化程序等等。

和線性表類似，棧也有兩種存儲結構——順序棧與鏈棧

棧的順序存儲結構——順序棧

順序棧的表示與實現

用C語言表示棧的順序結構

#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct{ SElemType *base; // 棧底指針（始終指向棧底） SElemType *top; // 棧頂指針 int stacksize; // 當前棧的最大容量} SqStack;

用下圖表示就是

其中: 1. s.base 始終指向棧底 2. s.top 始終指向棧頂元素的下一個位置 3. s.base = NULL 表示棧結構不存在 4. s.top = s.base 表示棧空 5. top-base = stacksize 表示棧滿

順序棧的基本操作

1. 初始化棧

Status initStack(SqStack *S){ S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base) return ERROR; S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;}

2. 棧判空

Status stackEmpty(SqStack* S) { return S.top == S.base;}

3. 判棧滿

Status stackFull(SqStack* S){ return ((S.top - S.base) == S.stacksize);}

4. 讀取棧頂元素

Status getTop(SqStack* S, ElemType e){ //返回棧S的棧頂元素,但棧頂指針保持不變 if(S.top == S.base) //棧為空 { printf("Stack is empty!"); return ERROR; } e = *(S.top-1); return OK;}

5. 入棧

Status push(SqStack* S, SElemType e){ if(S.top-S.base >= S.stacksize) //判滿 { //追加存儲空間 S.base = (ElemType*)realloc(S.base(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S.base) exit(OVERFLOW); //上溢 S.top = S.base+S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; //棧頂指針後移，賦值 return OK;}

6. 出棧

Status pop(SqStack* S, SElemType *e){ //將棧S的棧頂元素彈出並返回 if(S.top == S.base) { printf("Stack is empty!"); return ERROR; } e = s->top; s->top--; return OK;}

棧的鏈式存儲結構——鏈棧

棧的鏈式存儲結構,也稱為鏈棧，它是一種限制運算的鏈表，即規定鏈表中的插入和刪除運算只能在鏈表開頭進行。

鏈棧的表示與實現

用C語言表示棧的鏈式結構

typedef struct SNode { SElemType data; struct SNode *next; }SNode, *LinkStack

鏈棧的基本操作

1. 初始化棧

void iniStack(LinkStack* top){ top = (LinkStack*)malloc(sizeof(SNode)); top->next = NULL;}

2. 進棧

Status push(LinkStack* top, SElemType e){ LinkStack* q; q = (LinkStack*)malloc(sizeof(SNode)); if (!q) exit(OVERFLOW); //存儲分配失敗 q->data = e; q->next = top->next; top->next = q; return OK;}

3. 出棧

Status pop(LinkStack* top, SElemType e){ LinkStack* q; if (!top->next) return ERROR; e = top->next->data; //取出棧頂元素的值 q = top->next; //q指向棧頂元素 top->next = q->next; //刪除棧頂元素 free (q); //釋放棧頂元素所佔的空間 return OK;}

4.取棧頂元素

Status getTop(LinkStack* top, SElemType e) { if (!top->next) return ERROR; else { e = top->next->data; return OK; } }

棧的典型應用

棧的典型應用，包括數字轉換問題、括弧匹配問題、表達式求值、遞歸中的漢諾塔等等。

這裡用棧對表達式求值做一個很簡單的解釋。

編寫演算法，用棧實現表達式3 * (7 - 2)求值。一個算術表達式是由操作數(x，y，z…)和算符(*, /, +, -, (, ), #)組成。其中演算法規則是：1. 從左算到右; 2. 先乘除, 後加減; 3. 先括弧內, 後括弧外.

其中算符之間的優先順序如下圖

在這個問題中，演算法的思想是：

為了實現算符優先演算法，可以設定兩個工作棧，OPND—存放操作數或運算結果，OPTR—存放運算符號。

1) 首先置操作數棧OPND為空棧，表達式的起始符#為運算符棧OPTR的棧底元素；

2) 依次讀入表達式中的每個字元，若運算符是「#」且棧頂是「#」，結束計算，返回OPND棧頂值。如果是操作數，則push(OPND，操作數)，如果是運算符，則與OPTR棧頂元素進行比較，按優先順序進行操作。

演算法的實現，偽代碼形式。

OperandType eval() { initstack(&OPTR); //初始化OPTR棧 push(&OPTR, "#"); initstack(&OPND); c = getchar(); while (c != "#") || getTop(OPTR) != "#") { if (!in(c,op)) //如果c是操作數 { push(&OPND); c = getchar(); } else //c是一個運算符 { r=precede(getTop(OPTR), c); // 比較兩個運算符的優先順序 switch(r) { case "<": //棧頂元素優先順序低 push(&OPTR, c); c=getchar(); break; case "=": //脫括弧並接受下一字元 pop(&OPTR, &x); c=getchar(); break; case ">": //退棧並將運算結果入棧 pop(&OPTR,&op); pop(&OPND,&b); pop(&OPND,&a); value=operate(a, op, b) ; push(&OPND, value); break; } } } return(getTop(OPND)); }

用一張圖來表示這個過程就是

棧的另一個重要的用途就是遞歸，在這裡就不細說了，orz，我先歇會下次再說_(:D)∠)_。。。

歡迎批評指正！