C语言深入刨析数据结构之栈与链栈的设计与应用

一.栈的定义

栈是限定仅在表尾进行插入和删除操作的数据结构（受到限制的线性表）。

我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何元素为空栈。

二.栈的特点

后进先出

比如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;
	}
}

八.总结

对比顺序栈和链栈，如果栈的使用过程中元素变化不可预料，有时小，有时大，那么最好用链栈；反之，如果他的变化在可控范围之内建议使用顺序栈会更好点。

（小白一位，如有错误欢迎指正）