1.栈结构
定义：栈是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底，不含任何数据元素的栈为空栈。
栈是一个特殊的线性表，其栈元素具有线性关系，即前驱后继关系，仅可以在其表尾进行插入和删除操作，这里的
表尾指的就是栈顶top，而不是栈底。
栈的插入操作，叫做进栈，也称压栈，入栈。
栈的删除操作，叫做出栈，也称弹栈。
2.栈的顺序存储结构实现
既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，简称为顺序栈。
2、1 栈的结构定义
typedef struct {
SElemType data[MAXSIZE];
int top; // 用于栈顶指针
}SqStack;
2、2 初始化一个空栈
// 初始化创建一个空栈
Status InitStack(SqStack *S){
S->top = -1;
return OK;
}
2、3 进栈
// 入栈
Status PushStack(SqStack *S,SElemType e){
// 需要判断栈内是否还有空间
if (S->top == MAXSIZE-1) {
return ERROR;
}
S->top++;
S->data[S->top] = e;
return OK;
}
2、4 出栈
// 出栈
Status PopStack(SqStack *S,SElemType *e){
if (S->top < 0) {
return ERROR;
}
*e = S->data[S->top];
S->top--;
return OK;
}
2、5 置空
// 置空顺序栈
Status ClearStack(SqStack *S){
S->top = -1;
return OK;
}
2、6 获取栈的长度
// 获取长度
int GetStackLength(SqStack S){
return S.top+1;
}
3. 栈的链式存储结构实现
栈的链式存储结构，简称为链栈。对于链栈来说，基本不会存在，像顺序栈那样的，栈空间被占满的情况。
3、1 链栈的结构定义
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackNode;
typedef struct {
LinkStackNode top; // 链栈栈顶指针
int count; // 链栈结点个数长度
}LinkStackList;
3、2 初始化链栈
// 初始化链式栈
Status InitStackList(LinkStackList *S){
S->top = NULL;
S->count = 0;
return OK;
}
3、3 进栈
// 链式入栈
Status PushStackList(LinkStackList *S,SElemType e){
LinkStackNode temp = (LinkStackNode)malloc(sizeof(LinkStackNode));
temp->data = e; // 赋值
temp->next = S->top; // 要压入链表栈的栈顶位置，所以新进栈的结点next指向栈顶
S->top = temp; // 栈顶调整为新的结点
S->count++; // 栈长度加一
return OK;
}
3、4 出栈
// 链式出栈
Status PopStackList(LinkStackList *S,SElemType *e){
if (S->count==0) {
return ERROR;
}
LinkStackNode temp = S->top; // 拿到要删除的栈顶元素
*e = temp->data;
S->top = S->top->next; // 调整栈顶元素为next下一个
S->count--;
free(temp); // 释放要删除的元素给内存
return OK;
}
3、5 链栈的置空
// 链式栈置空
Status ClearStackList(LinkStackList *S){
if (S->count == 0) {
return ERROR;
}
LinkStackNode temp = S->top;
while (temp) {
LinkStackNode nextNode = temp->next;
free(temp); // 置空要把所有的元素都释放
temp = nextNode;
}
S->count = 0;
return OK;
}
4. 顺序栈和链栈的对比
- 顺序栈和链栈在时间复杂度上都是O(1)
- 对于空间性能，顺序栈需要实现确定一个固定的长度，可能会存在内存浪费的问题，但顺序栈在存取时定位很方便（top加或者top减）。
- 链栈中每个元素都有指针域，增加了内存开销，但对于栈的长度无限制。
如果栈的使用过程中元素变化不可预料，有时很大有时很小，则最好使用链栈，反之变化在可控范围内，使用顺序栈更好。
ps. 两栈共享空间，栈的应用：递归