---

特点：

• 先入先出
• 出入口只有一个（弹夹）

1. 顺序栈

1.1 定义

#include<stdio.h>
#include<stdlib.h> 
#define MaxSize 64
typedef int datatype;typedef struct 
{datatype data[MaxSize];int top;
}seqstack;

1.2 初始化

seqstack* InitStack(seqstack* s)
{s=(seqstack*)malloc(sizeof(seqstack));s->top=-1;return s;
}

1.3 入栈

int Push(seqstack *sstack,datatype x)//入栈； 
{if(sstack->top==MaxSize-1){printf("stack full!\n");return -1;}	sstack->top++;sstack->data[sstack->top]=x;return 1;
} 

1.4 出栈

int Pop(seqstack *sstack)//出栈；
{if(sstack->top==-1){printf("OVER->Top = %d",sstack->top);return -1;}printf("Pop %d\n",sstack->data[sstack->top]);sstack->top--;return 1;
}

2. 链栈（重点）

2.1 定义

typedef struct node
{datatype data;struct node * next;
}LinkStack;LinkStack *top;

2.2 入栈

LinkStack* Push(LinkStack* top,datatype x)
{LinkStack* p;p = (LinkStack)malloc(sizeof(LinkStack));p->data = x;p->next = top->next;top=p;return top;
}

2.3 出栈

LinkStack* Pop(LinkStack* top)
{LinkStack* q;if(!top){printf("Stack null!");return NULL;}q->top;top=top->next;free(q);return top;
}

记忆总结

1. 链栈数据是通过数组存放，但外层依旧是一个结构体（跟顺序表一样）
2. 栈满：top==MaxSize-1 为什么要减一？因为栈空时top=-1而非1，相当于错开了一位。为什么top不从1开始？方便利用top作为数组下标去索引数据
3. 入栈只需要将top++且top指向的位置赋为新值即可
4. 出栈只需要top–

---

1. 链栈就是只通过一个top指针连接、只进行头插法、头删除的单链表。