参考学习：B站-逊哥带你学编程

栈的定义与实现

补充：

栈是限制插入和删除操作只能在一个位置进行的表，该位置是表的末端，叫作栈顶(top)。

对栈的基本操作有进栈(push)和出栈(Pop)，前者相当于插入后者则是删除最后插入的元素。

栈的顺序结构实现

#define MAXSIZE 100
typedef int ElemType;typedef struct
{ElemType data[MAXSIZE];int top;
}Stack;

栈的顺序结构-初始化

void initStack(Stack *S)
{S->top = -1;
}

栈的顺序结构-判断栈是否为空

int isEmpty(Stack *S)
{if(S->top == -1){printf("Stack is empty\n");return 1;}return 0;
}

栈的顺序结构-进栈/压栈

int push(Stack *S, ElemType e)
{if(S->top >= MAXSIZE-1){printf("Stack is full\n");return 0;}S->top++;S->data[S->top] = e;return 1;
}

栈的顺序结构-出栈

ElemType pop(Stack *S, ElemType *e)
{if(S->top == -1){printf("Stack is empty\n");return 0;}*e = S->data[S->top];S->top--;return 1;
}

栈的顺序结构-获取栈顶元素

int getTop(Stack *S, ElemType *e)
{if(S->top == -1){printf("Stack is empty\n");return 0;}*e = S->data[S->top];return 1;
}

栈的顺序结构-动态内存分配

typedef struct
{ElemType *data;int top;
}Stack;Stack *initStack()
{Stack *S = (Stack *)malloc(sizeof(Stack));S->data = (ElemType *)malloc(sizeof(ElemType)*MAXSIZE);S->top = -1;return S;
}

栈的链式结构实现

typedef int ElemType;typedef struct
{ElemType data;struct stack *next;
}Stack;

图示：

栈的链式结构实现-初始化

Stack *initStack()
{Stack *S = (Stack *)malloc(sizeof(Stack));S->data = 0;S->next = NULL;return S;
}

栈的链式结构实现-判断栈是否为空

int isEmpty(Stack *S)
{if(S->next == NULL){printf("Stack is empty\n");return 1;}return 0;
}

栈的链式结构实现-进栈/压栈

int push(Stack *S, ElemType e)
{Stack *p = (Stack *)malloc(sizeof(Stack));p->data = e;p->next = S->next;S->next = p;return 1;
}

栈的链式结构实现-出栈

int pop(Stack *S, ElemType *e)
{if(S->next == NULL){printf("Stack is empty\n");return 0;}Stack *p = S->next;*e = p->data;S->next = p->next;free(p);return 1;
}

栈的链式结构实现-获取栈顶元素

int getTop(Stack *S, ElemType *e)
{if(S->next == NULL){printf("Stack is empty\n");return 0;}*e = S->next->data;return 1;
}