栈
栈是一种遵循先入后出逻辑的线性数据结构，是只能在表的一端进行插入和删除运算的线性表
进行插入和删除的一端的称为栈顶，另一端称为栈底
栈的操作规则是后进先出或者是先进后出
栈可以用数组或者链表实现，用数组实现的叫做顺序栈，用链表实现的叫做链栈
顺序栈
表示（数组）
在数组上实现时，栈底位置设置在数组的首位置，栈顶位置则是随着插入和删除而变化，可以用一个整形变量 top 来存放栈顶的位置，数据入栈或出栈时使 top 加1或减1
#define MAXSIZE 100
typedef int ElemType;
typedef struct SeqStack
{
ElemType data[MAXSIZE];
int top;
}SeqStack;
top：指向的是栈顶之上的第一个位置
当 top == 0 时，表示栈为空，当 top == MAXSIZE 时，表示栈满
初始化
void init(SeqStack* S)
{
int i = 0;
for (i = 0; i < MAXSIZE; i++)
{
S->data[i] = 0;
}
S->top = 0;
}
当然也没必要让 data 数组中的每个值都为0，但是一定要让 S->top = 0
也可以不必使用初始化函数，而在主函数中直接初始化
int main(void)
{
SeqStack S = { {0},0 };
//init(&S);
return 0;
}
判断栈是否空
int isEmpty(SeqStack* S)
{
if (S->top == 0)
{
return 1;
}
else
{
return 0;
}
}
判断栈是否满
int isFull(SeqStack* S)
{
if (S->top == MAXSIZE)
{
return 1;
}
else
{
return 0;
}
}
入栈
void push(SeqStack* S, ElemType x)
{
if (isFull(S) == 1)
{
return;
}
else
{
S->data[S->top] = x;
S->top++;
}
}
出栈
ElemType pop(SeqStack* S)
{
if (isEmpty(S) == 1)
{
printf("The SeqStack is full!\n");
return 0;
}
else
{
S->top--;
ElemType x = S->data[S->top];
return x;
}
}
当栈满时返回0是不严谨的，可以用 exit(0); 代替
访问栈顶元素
ElemType get_top(SeqStack* S)
{
if (isEmpty(S) == 1)
{
printf("The SeqStack is empty!\n");
return 0;
}
else
{
return S->data[S->top - 1];
}
}
当栈空时返回0是不严谨的，可以用 exit(0); 代替
表示（动态内存）
顺序栈也可以这么表示
#define MAXSIZE 100
typedef int ElemType;
typedef struct Stack {
ElemType* base;
ElemType* top;
int stacksize;
}SeqStack;
base指针：表示栈底元素在栈中的位置/地址
top指针：表示栈顶之上第一个元素的位置/地址
stacksize：表示栈的容量
当 top == base 时，表示栈空
当 top - base == MAXSIZE 时，表示栈满
初始化
void init(SeqStack* S)
{
S->base = (ElemType*)malloc(sizeof(ElemType) * (MAXSIZE + 1));
if (S->base == NULL)
{
return;
}
S->top = S->base;
S->stacksize = MAXSIZE;
}
分配空间的大小是 MAXSIZE + 1，因为 top 指针表示的是栈顶之上的第一个元素，当栈满时，也就是栈中的元素个数为 MAXSIZE 时，如果没有这么一个额外的空间，top 指向的地址就不确定
判断栈是否空
int isEmpty(SeqStack* S)
{
if (S->base == S->top)
{
return 1;
}
else
{
return 0;
}
}
判断栈是否满
int isFull(SeqStack* S)
{
if (S->top - S->base == S->stacksize)
{
return 1;
}
else
{
return 0;
}
}
入栈
void push(SeqStack* S, ElemType x)
{
if (isFull(S) == 1)
{
return;
}
else
{
*(S->top) = x;
S->top++;
}
}
出栈
ElemType pop(SeqStack* S)
{
if (isEmpty(S) == 1)
{
return 0;
}
else
{
S->top--;
return *(S->top);
}
}
当栈满时返回0是不严谨的，可以用 exit(0); 代替
访问栈顶元素
ElemType get_top(SeqStack* S)
{
if (isEmpty(S) == 1)
{
return 0;
}
else
{
return *(S->top - 1);
}
}
当栈空时返回0是不严谨的，可以用 exit(0); 代替
求栈中元素个数
int count(SeqStack* S)
{
int length = S->top - S->base;
return length;
}
清空栈
void clear(SeqStack* S)
{
S->top = S->base;
}
销毁栈
void destroy(SeqStack* S)
{
free(S->base);
S->stacksize = 0;
S->base = NULL;
S->top = NULL;
}
链栈
链栈是用链表实现的，所谓的链栈就是操作受限的链表。实现链表时，有带头结点的和不带头结点的，为了方便操作，采用带头结点的实现方式。然而在实现链栈时，我们采用不带头结点的实现方式。不过在下文中，仍有头结点表示链栈中的第一个元素。
使用链表实现栈时，将链表的头节点视为栈顶，尾节点视为栈底。
链栈的头指针指向头结点，也就是栈顶，用头指针来表示链栈
头指针指向空时，表示栈为空
入栈操作是让新结点的指针域指向头结点，再让头指针指向新结点（头插法）
表示
typedef struct StackNode
{
int data;
struct StackNode* next;
}StackNode, * LinkStack;
基于以上表示，在主函数中可以这样表示链栈的创建和初始化
int main(void)
{
LinkStack S = NULL;
return 0;
}
S 就是链栈的头指针，指向栈顶，当它指向 NULL 时，说明链栈为空
判断是否为空
int isEmpty(LinkStack S)
{
if (S == NULL)
{
return 1;
}
else
{
return 0;
}
}
入栈
LinkStack push(LinkStack S, int data)
{
StackNode* p = (StackNode*)malloc(sizeof(StackNode));
if (p == NULL)
{
return NULL;
}
p->data = data;
p->next = S;
S = p;
return S;
}
注意这里返回的类型是 LinkStack，一定要将指针的值返回到主函数去
出栈
LinkStack pop(LinkStack S, int* data)
{
StackNode* p = S;
*data = S->data;
S = S->next;
free(p);
p = NULL;
return S;
}
通过出栈函数，既要改变链栈的头指针指向，又要将栈上的元素返回，返回值可以解决第一个问题，而将函数的参数设为 int*，可以实现返回栈上的元素
取栈顶元素
int get_top(LinkStack S)
{
return S->data;
}