学步园

链接堆栈就是采用一个线性链表实现一个堆栈结构，栈中每一个元素用一个链接点表示，同时设置一个指针变量top指出当前栈顶元素所在链接点的存储位置，当堆栈为空时，top == NULL。采用线性链表表示的堆栈不必设置头结点，链表第1个链接点就是栈顶元素所在的链接点，最先进入堆栈的元素就一定在链表末尾的那个结点，只要把线性链表第1个链接点的指针定义为栈顶指针，并且限定只能在链表前面进行插入，删除等操作，这个链表就成为链接堆栈，线性链表的堆栈类型描述如下：

/* 定义一个线性链表堆栈类型 */
typedef struct node {
	SElemType data;
	struct node *link;
}STNode, *STLink;

链接堆栈的基本算法描述如下，包括测试代码：

#include<stdio.h>
#include<stdlib.h>

/* 定义一个线性链表堆栈类型 */
typedef struct node {
	int data;
	struct node *link;
}STNode, *STLink;

/* 链接堆栈初始化 */
void initialLink( STLink *top ){
	*top = NULL;
}

/* 测试线性链表是否为空，为空返回1，否则返回0 */
int isEmptyLink( STLink top ){
	return top == NULL;
}

/* 取当前栈顶元素，操作成功返回1，否则返回0 */
int getTopElem( STLink top, int *item ){
	if( isEmptyLink( top ) )  /* 堆栈为空，操作失败，返回0 */
		return 0;
	else{
		*item = top->data;
		return 1;           /* 操作成功，栈顶元素放入item中，返回1 */
	}
}

/* 链接堆栈的插入 */
int pushLink( STLink *top, int item ){
	STLink p = ( STLink )malloc( sizeof( STNode ) );  /* 申请一个新的链接点 */
	if( p == NULL )
		return 0;                  /* 插入失败，返回0 */
	else{
		p->data = item;   /* 将插入元素送新结点的数据域 */
		p->link = *top;   /* 修改头结点指针，返回1 */
		*top = p;
		return 1;
	}
}

/* 链接堆栈的删除栈顶元素 */
int popLink( STLink *top, int *item ){
	STLink p;
	if( isEmptyLink( *top ) )  /* 堆栈为空，删除失败，返回0 */
		return 0;
	else{
		p = *top;
		*item = p->data;         /* 将栈顶元素数据域送入item中 */
		*top = ( *top )->link;   /* 修改栈顶指针 */
		free( p );               /* 释放被删除结点 */
		return 1;                /* 操作成功，返回1 */
	}
}

/* 打印堆栈信息，用于测试 */
void printLink( STLink top ){
	while( top != NULL ){
		printf( "%d\n", top->data );
		top = top->link;
	}
}

int main(){
	STLink tops;
	initialLink( &tops );
	pushLink( &tops, 4 );
	pushLink( &tops, 9 );
	pushLink( &tops, 1 );
	printLink( tops);
	printf( "the link is empty: %d\n", isEmptyLink( tops ) );
	
	int item;
	getTopElem( tops, &item );
	printf( "the top elem is %d\n", item );
	
	popLink( &tops, &item );
	printf( "the deleted elem is %d\n", item );
	
	popLink( &tops, &item );
	popLink( &tops, &item );
	printf( "the link is empty: %d\n", isEmptyLink( tops ) );

	return 0;
}