这是数据结构的第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.