数据结构（五）
这是数据结构的第5篇文章
那么上次讲到了排队的问题，因而处理类似牌堆一个接着一个的问题时，我们会使用数据结构——队列。
那么当我们处理的数据不是先入先出的情况呢？
举个例子：当我们打开网页，百度 --> 淘宝 --> 手机，我们想从手机页面返回百度页面时，是要经过淘宝页面的，这就是另外的一个顺序。即靠后打开的网页在返回的时候会先弹出。
这就是栈——后进先出。
概念
栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。——百度
不用什么解释了吧，已经很到位了。
更好的理解的话请看下图：
第an+1个元素入栈，假如他是最后进入的，那么他将会第一个出去。
栈的抽象
Status initLStack(LinkStack *s);//初始化
Status isEmptyLStack(LinkStack *s);//判断是否为空
Status getTopLStack(LinkStack *s,ElemType *e);//返回栈顶元素
Status destoryLStack(LinkStack *s);//销毁栈
Status LStackLength(LinkStack *s,int length);//返回栈的长度
Status pushLStack(LinkStack *s,ElemType datas);//压栈
Status popLStack(LinkStack *s,ElemType *datas);//弹栈
结构定义
这里同样也用链表来实现栈。
首先，明确一点：我们只是针对栈的一端进行操作，被操作的一端叫做栈顶，另外一段被称为栈底。
那么这里对每个节点而言。数据域data是必不可少的，因为栈的节点要存储内容。指针域呢，只用简单的一个指针即可。对整个栈而言，描述一个栈，只要知道栈顶指针和栈元素个数即可。因此，结构定义如下：
typedef struct StackNode
{
ElemType data;
struct StackNode *next;
}StackNode, *LinkStackPtr;
typedef struct LinkStack{
LinkStackPtr top; //栈顶指针
int count; //栈中元素个数
}LinkStack;
入栈
入栈的操作可以类比成链表添加节点的操作，数据写入数据域，再next指向上一个。
Status pushLStack(LinkStack *s,ElemType datas) //入栈
{
if(s == NULL) {printf("请初始化链栈!\n"); return ERROR;}
LinkStackPtr current = (LinkStackPtr)malloc(sizeof(StackNode));
current->data = datas;
current->next = s->top;
s->top = current;
s->count++;
return OK;
}
出栈
出栈的操作也很简单，因为栈的原理是后入先出，因此只需要遍历到链表的末端，把指向NULL的节点弹出去就行啦！
但这里的话还是老样子，要记住预防一些错误的发生，如：空栈。
Status popLStack(LinkStack *s,ElemType *datas) //出栈
{
if(s->top == NULL) {printf("空链栈不执行！\n"); return ERROR;}
LinkStackPtr current;
*datas = s->top->data;
current = s->top;
s->top = s->top->next;
free(current);
s->count--;
printf("出栈元素为：%d\n",*datas);
return OK;
}
初始化栈
初始化栈的操作可以跟初始化链表的操作类比，malloc一个新节点，指向NULL，数据与为0，即可。
Status initLStack(LinkStack *s) //初始化
{
s = (LinkStack*)malloc(sizeof(LinkStack));
s->top = NULL;
s->count = 0;
printf("成功初始化链栈!\n");
return OK;
}
销毁栈
使用while逐一弹出，free掉即可。
Status clearLStack(LinkStack *s) //销毁
{
if(s->top == NULL) {printf("空链栈不执行！\n"); return ERROR;}
LinkStackPtr current;
while(s->count)
{
s->count--;
current = s->top->next;
free(s->top);
s->top = current;
}
printf("清空成功！\n");
return OK;
}
栈的长度
直接返回count即可，特别简单。
Status LStackLength(LinkStack *s,int length) //检测链zhan长度
{
length = s->count;
printf("链栈长度为：%d\n",length);
return OK;
}
总结一下
1、后入先出。
2、操作只在一端。
3、只要知道栈的元素个数和首节点就可完全清楚一个栈。
4、不难。、
5、另外，如果使用数组完成栈，count先赋值0，节点赋值-1.