堆栈（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;}
}