本次筆記内容：
2.2.1 什麼是堆棧
2.2.2 堆棧的順序存儲實作
2.2.3 堆棧的鍊式存儲實作
2.2.4 堆棧的應用：表達式求值
文章目錄
-
-
- 引：計算機如何進行表達式求值？
- 堆棧的抽象資料類型描述
- 棧的順序存儲實作
- 堆棧的鍊式存儲實作
- 表達式求值及其他應用
-
引：計算機如何進行表達式求值？
由兩類對象構成：
- 運算數，如2、3、4；
- 運算符号：如+、-、*、/。
- 不同的運算符号優先級不一樣。
中綴表達式：a+b*c-d/e
字尾表達式：abc*+de/-
例：62/3-42*+=?
遇到6、2、/，則6/2=3；
遇到3、-，則3-3=0；
遇到4、2、*，則4*2=8；
遇到+，則0+8=8。
計算政策：從左往右掃描，遇到數則存儲，遇到運算符号則将最近存儲兩個數計算 。
則需要一種後進先出的資料結構，就是堆棧。
T
(
N
)
=
O
(
N
)
T(N)=O(N)
T(N)=O(N)
堆棧的抽象資料類型描述
堆棧（Stack）：具有一定限制的線性表。
插入資料：入棧（Push）
删除資料：出棧（Pop）
先入後出：Last In First Out（LIFO）
在使用Push()或Pop()前，通常調用IsFull()判斷堆棧是否為滿或調用IsEmpty()判斷是否為空。
對于ABC入棧，不可能産生CAB的輸出。
棧的順序存儲實作
使用數組存儲。
#define MaxSize <儲存資料元素的最大個數>
typedef struct SNode *Stack;
struct SNode
{
ElementType Data[MaxSize];
int Top;
};
入棧：
void Push(Stack PtrS, ElementType item)
{
if (Ptrs->Top == MaxSize - 1)
{
printf("堆棧滿") : return;
}
else
{
PtrS->Data[++(PtrS->Top)] = item;
return;
}
}
出棧。
ElementType Pop(Stack PtrS)
{
if (PtrS->Top == -1)
{
printf("堆棧空");
return ERROR; // ERROR是ElementType的特殊值，标志錯誤
}
else
{
return (PtrS->Data[(PtrS->Top)--]);
}
}
堆棧的鍊式存儲實作
typedef struct SNode *Stack;
struct SNode
{
ElementType Data;
struct *Next;
};
Stack CreateStack()
{ /* 建構一個堆棧的頭結點，傳回指針 */
Stack S;
S = (Stack)malloc(sizeof(struct SNode));
S->Next = NULL;
return S;
}
表達式求值及其他應用
- 函數調用及遞歸實作
- 深度優先算法
- 回溯算法