栈和队列其实是一种特殊的线性表，他们是限定只能在表的一端或两端进行插入、删除元素，所以，这些被统称为限定性数据结构
栈
定义：
栈可以说是线性表的具体形式，仅允许在表尾进行插入删除操作，我们把允许进行插入删除操作的一端，称为栈顶，另一端称为栈底。
对于栈来说，最主要的操作就是插入和删除操作，插入操作称为，入栈或进栈，删除操作称为，出栈或退栈。由于只能在栈顶进行插入和删除操作，所以栈有一个特点就是栈里的元素一般都是是先进后出（后进先出），就好像手枪的弹夹，最先压进去的子弹，最后才打出来。
栈的基本操作：
- InitStack(S): 构造一个空栈
- ClearStack(S): 将栈S清为一个空栈
- EmptyStack(S): 判断栈S是否为空
- LengthStack(S): 求栈S的长度（栈中元素的个数）
- GetTop(S,e): 获取栈顶元素
- Push(S,e): 入栈操作
- Pop(S,e): 出栈操作
因为栈的本质是一个线性表，所以栈也分为顺序栈和链栈
栈的顺序存储结构的类型定义
#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE]; //用数组来模拟顺序栈,下标从零开始
int top; //栈顶的指针，也就是栈顶的位置下标
}SeqStack;
栈的顺序存储结构的具体操作
#define OK 1
#define ERROR 0
typedef int Status;
Status InitStack(SeqStack *S)
{
S->top = -1; //因为数组下标从零开始，所以-1为空
return OK;
}
Status ClearStack(SeqStack *S)
{
S->top = -1;
return OK;
}
int EmptyStack(SeqStack S)
{
if(S.top==-1)
return 1;
else
return 0;
}
int LengthStack(SeqStack S)
{
return S.top+1;
}
Status GetTop(SeqStack S,ElemType *e)
{
if(EmptyStack(S)) //栈为空
return ERROR;
*e = S.data[S.top];
return OK;
}
Status Push(SeqStack *S,ElemType e)
{
if(S->top == MAXSIZE-1) //栈满了
return ERROR;
else
{
S->top++;
S->data[S->top] = e;
}
return OK;
}
Status Pop(SeqStack *S,ElemType *e)
{
if(ElemType(S)) //栈为空
return ERROR;
*e = S->data[S->top];
S->top--;
return OK;
}
链栈
链栈其实就是利用单链表作为栈的存储结构，单链表的第一个结点为栈顶，最后一个结点为栈底。链栈可以有头结点也可以没有，不带头结点，栈顶指针就指向栈顶结点，带头结点就指向头结点。
栈的链式存储结构描述：
typedef struct node
{
ElemType data; //数据域
struct node *next; //指针域
}StackNode,*LinkStack;
基础操作
//这里只描述栈的三个重要操作，其他操作可与单链表进行类比
Status GetTop(LinkStack top,ElemType *e)
{
if(!top->next) //栈为空
return ERROR;
*e = top->next->data; //有头结点的栈
return OK;
}
Status Push(LinkStack top,e)
{
StackNode *p;
p = (StackNode*)malloc(sizeof(StackNode)); //为新结点开辟存储空间
s->data = e; //数据域赋值
s->next = top->next; //将s插入到栈顶
top->next = s;
return OK;
}
Status Pop(LinkStack top,*e)
{
if(!top->next) //空栈
return ERROR;
StackNode *p;
*e = top->next->data; //用e来返回栈顶元素
p = top->next;
top->next = p->next; //删除栈顶结点并更新栈顶
free(p); //释放空间
return OK;
}
