栈的链式存储结构

栈的链式存储结构是指用一组任意的存储单元来存储栈中的数据元素，用这种链式存储结构存储的栈称为链栈（Link Stack）。链栈的结点结构与单链表的结点结构相同，由于栈的插入和删除操作仅限制在栈顶进行，所以可用不带头结点的单链表实现栈的链式存储结构以使链栈的操作运算更加方便。在链栈中，每一个结点表示栈中的一个元素，链表的头指针称为栈顶指针，如果设栈顶指针top是node类型的变量，则top指向栈顶结点（第一个结点）。

栈的链式存储结构定义如下：

	struct node /*链栈的结点类型*/
	{ ElemType data; /*链栈结点的数据域*/
	struct node *next; /*链栈结点的指针域*/
	};

struct node *top; /*top定义为指向结点类型的指针变量*/

一个链栈由栈顶指针top唯一确定。当top为空(NULL)时，表示该链栈为空栈；若链栈非空，则top指向栈顶结点。栈中元素的数据类型用ElemType表示，可根据需要指定其具体的类型。假设元素以a₁， a₂，a₃，…，a_n的顺序进栈，则a₁为栈底元素，a_n为栈顶元素，如图3-3所示。

链栈的基本操作

于链栈的结点是动态分配的，因此链栈只有空栈和非空栈这两种状态，不会出现栈满的情况。

假设在链栈中，top为node类型的全局变量。

（1）初始化栈

链栈初始化栈算法

	void InitStack()
	{
	top=NULL; /*将栈顶指针置空表示空栈*/
	}

（2）判栈空

链栈判栈空算法

	int StackEmpty()
	{
	if( top==NULL) return 1; /* 如果栈为空，则返回1 */
	else return 0; /* 否则返回0 */
	}

（3）进栈

进栈操作是在栈顶位置插入一个值为x的新元素。

算法要点：

（1）为待进栈元素x动态分配一个新结点p，并把x赋给新结点p的数据域；

（2）将新结点p的指针域指向原栈顶结点；

（3）使top指向新结点p,即使值为x的新结点p成为新的栈顶结点；

（4）函数返回新的栈顶指针。

链栈进栈算法

	void Push(ElemType x)
	{
	struct node *p;
	p=(struct node*)malloc(sizeof(struct node)); /*生成新结点*/
	p->data=x; /*给新结点p的数据域赋x值*/
	p->next=top; /*新结点p的指针域指向原栈顶结点*/
	top=p; /*修改栈顶指针，使之指向新结点*/
	}

（4）出栈

出栈运算是从栈中删除一个元素。当栈不空时，可通过修改栈顶指针达到元素删除的目的。

算法要点：

（1）检查栈是否为空，若为空，进行“下溢”错误处理；

（2）取栈顶元素保存在x中；

（3）栈顶指针指向前一个结点；

（4）函数返回新的栈顶指针。

链栈出栈算法

	ElemType Pop()
	{
	struct node *p; /* 定义指针变量p */
	int x; /* 定义一个变量x，用以存放出栈的元素 */
	if(top==NULL) { /* 检查链栈是否为空 */
	printf("栈下溢错误！\n");
	exit(1); /* 若栈空不能出栈，则退出运行 */
	}
	p=top; /* 用指针变量p暂存栈顶指针 */
	x=p ->data; /* 栈顶元素送x */
	top=top->next; /* 栈顶指针指向下一个结点 */
	free(p); /* 回收原栈顶结点 */
	return x; /* 返回原栈顶元素 */
	}

（5）取栈顶元素

链栈取栈顶元素算法

	ElemType GetTop()
	{
	if((top)==NULL) { /* 检查链栈是否为空 */
	printf("栈下溢错误！\n");
	exit(1); /* 若栈空不能出栈，则退出运行 */
	}
	return (top)->data; /* 若栈非空，则返回栈顶元素 */
	}