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

栈是限定仅在表尾进行插入或删除操作的线性表，表尾称为栈顶（top），表头称为栈底（bottom）。栈的最主要特点就是“先进后出”（FILO），或“后进先出”（LIFO）。用链式存储结构表示的栈称为“链栈”，链栈对应于链表

一.栈的定义

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

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

二.栈的特点

后进先出

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

八.总结

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

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

到此这篇关于C语言深入刨析数据结构之栈与链栈的设计与应用的文章就介绍到这了,更多相关C语言栈与链栈内容请搜索编程学习网以前的文章希望大家以后多多支持编程学习网！