目录
- 一.栈的定义
- 二.栈的特点
- 三.栈的理解
- 四.链栈引入
- 五.链栈定义
- 六.链栈的结构体设计
- 七.链栈的基本操作
- 7.1链栈的初始化
- 7.2链栈判空
- 7.3链栈入栈
- 7.4链栈出栈
- 7.5取栈顶元素
- 八.总结
一.栈的定义
栈是限定仅在表尾进行插入和删除操作的数据结构（受到限制的线性表）。
我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何元素为空栈。
二.栈的特点
后进先出
比如word，浏览器网页等一系列软件中，都有撤销的操作，就是利用栈的这种方式来实现的，可能不同软件的代码不同，但是他们的原理是一样的均为：后进先出。
三.栈的理解
- 栈是一个线性表，有前驱后继关系，只不过这里的表尾指的是栈顶。
- 栈限制了线性表的插入和删除位置，这也导致栈底是固定的。
- 栈的插入操作，叫做进栈；可以理解为子弹入弹夹。
- 栈的删除操作，叫做出栈；可以理解为子弹出弹夹。
四.链栈引入
既然栈是属于线性表的一种，那么存储结构也就分为顺序存储和链式存储，这里我们着重讲解链式存储结构。
五.链栈定义
栈的链式存储结构，简称链栈。
对于栈来说，只在栈顶做插入和删除操作，由于单链表有头指针，栈顶指针也是必须的，那我们干脆就将头指针和栈顶指针合二为一，将栈顶放在单链表的头部。通常对于链栈是不需要头结点的。
对于链栈来说，一般不会存在栈满的情况，如果这种事情真的发生，那么此时的计算机操作系统也将会面临死机崩溃的情况，那就不单单是这个链栈是否溢出的问题了。对于链表来说，链表为空的表示是头结点指向空，那么对于链栈来讲，链栈为空就是栈顶指针指向空（top = NULL）。
六.链栈的结构体设计
代码如下：
// 链栈的存储结构
typedef struct StackNode
{
int data;
struct StackNode *next;
}StackNode,*LinkStack;
七.链栈的基本操作
对于链栈来说作为线性表的一种，操作也就那么几种，这里我们对以下几种操作进行详解：初始化，判断是否为空，入栈，出栈，取栈顶元素等。
7.1链栈的初始化
链栈的初始化可以理解为构造一个空栈，将栈顶指针top所指头结点的指针域置为NULL，因为此时栈中还没有数据元素。
代码如下：
LinkedStack Init_LinkedStack()
{
LinkedStack top = (LinkedStackNode *)malloc(sizeof(LinkedStackNode));
//栈顶指针变量
if(top != NULL)
{
top->next = NULL;
}
return top;
}
7.2链栈判空
判断链栈是否为空，只需要判断栈顶的指针域是否指向空，如果指向空则栈空，相反亦然。
bool LinkedStack_Empty(LinkedStack top)
{
if(top->next == NULL)//如果栈顶的指针域指向空，则栈空
{
return True;
}
else
{
return False;
}
7.3链栈入栈
入栈就是：
- 先对数据域进行赋值；
- 然后让新结点指向栈顶指针；
- 最后将栈顶指针交给新节点。
假设元素值为e的新节点是s，top为栈顶指针：
代码如下：
int Push(LinkedStack *s ,elemtype e)
{
LinkedStackNode s= (LinkedStackNode )malloc(sizeof(LinkedStackNode));
s->data=e;
s->next=s->top;//把当前的栈顶元素赋值给新结点的直接后继.
s->top=s;//把新节点s赋值给栈顶指针
s->cout++;
return 1;
}
7.4链栈出栈
出栈就是：
- 将要删除的元素的值交给临时变量，将栈顶指针交给临时节点；
- 将栈顶指针下移；最后释放临时节点（即完成删除）。
- 假设变量p用来存储要删除的栈顶结点，将栈顶指针向下移一位，最后释放p即可：
代码如下：
int Pop_LinkedStack(LinkedStack *s,elemtype *e)
{
LinkedStackNode *p;
if(stackempty(*s))
return error;
*e=s->top->data;
p=s->top; //将栈顶结点赋值给p
s->top=s->top->next;//使得栈顶结点指针下移一位，指向后一结点
free(p);//释放结点
s->count--;
return 1;
}
}
7.5取栈顶元素
读取栈顶元素，并返回其值，该操作与出栈的区别是栈顶元素并不删除，所以不用修改头结点的指针域即可。
int Get_LinkedStack(LinkedStack top,elemtype *x)
{
if(top->next == NULL)
{
return 0;
}
else
{
*x = top->next->data;
return 1;
}
}
八.总结
对比顺序栈和链栈，如果栈的使用过程中元素变化不可预料，有时小，有时大，那么最好用链栈；反之，如果他的变化在可控范围之内建议使用顺序栈会更好点。
（小白一位，如有错误欢迎指正）
评论(0)