堆栈（Stack）：具有一定操作约束的线性表
只在一端（栈顶，Top）做 插入、删除
栈的顺序存储实现
1. 定义
#define MaxSize <存储数据元素的最大个数>
typedef struct SNode* Stack;
struct SNode {
ElementType Data[MaxSize];
int Top;
};
2. 入栈
void Push(Stack PtrS, ElementType item) {
if (PtrS->Top == MaxSize - 1) {
printf("堆栈满");
return;
}
else {
PtrS->Data[++(PtrS->Top)] = item;
return;
}
}
3. 出栈
ElementType Pop(Stack PtrS) {
if (PtrS->Top == -1) {
printf("堆栈空");
return ERROR;
}
else {
return PtrS->Data[(PtrS->Top)--];
}
}
栈的链式存储实现
1. 定义
#define MaxSize <存储数据元素的最大个数>
typedef struct SNode* Stack;
struct SNode {
ElementType Data;
Stack Next;
};
2. 创建
Stack CreateStack() {
Stack S;
S = (Stack)malloc(sizeof(struct SNode));
S->Next = NULL;//创建一个堆栈的头节
return S;
}
> 判断堆栈S是否为空
int IsEmpty(Stack S) {
return (S->Next == NULL);
}
3. 入栈
void Push(ElementType item, Stack S) {
Stack TmpCell;
TmpCell = (Stack)malloc(sizeof(struct SNode));
TmpCell->Data = item;
TmpCell->Next = S->Next;
S->Next = TmpCell;
}
4. 出栈
ElementType Pop(Stack S) {
Stack FirstCell;
ElementType TopElem;
if (IsEmpty(S)) {
printf("堆栈空");
return NULL;
}
else
{
FirstCell = S->Next;
S->Next = FirstCell->Next;
TopElem = FirstCell->Data;
free(FirstCell);
return TopElem;
}
}
