特点：

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

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->next;
	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指针连接、只进行头插法、头删除的单链表。