栈的链式存储及基本操作

栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在栈顶进行。

先将练习结果贴下

相关C代码如下：

/*数据结构之栈*/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef int DataType;
/*定义栈的结构体类型*/
typedef struct NODE{
	DataType data;
	NODE * pNext;
}Node,* PNode;

typedef struct STACK{
	PNode pTop;
	PNode pBot;
}Stack,* PStack;

void  InitStack(PStack);  //初始化栈
bool isEmpty(PStack);  //判断栈是否为空
void Push(PStack,DataType val);  //进栈函数
bool Pop(PStack,DataType *x);  //出栈操作
DataType GetTop(PStack);  //取栈顶元素
void show_Stack(PStack);  //列出栈的内容

void main(){
	
	Stack S;
	DataType x;
	InitStack(&S);  //初始化栈
	Push(&S,3);     //元素3入栈
	Push(&S,4);     //元素4入栈
	Push(&S,100);   //元素100入栈
	Push(&S,200);   //元素200入栈
	Push(&S,2016);   //元素2016入栈
	show_Stack(&S);  //显示当前栈各个元素
	if(Pop(&S,&x)){   //出栈操作，并显示出栈的元素
		printf("出栈操作成功,当前出栈的元素是%d\n",x);
	}
	show_Stack(&S);
	printf("当前栈顶的元素是%d\n",GetTop(&S));   //显示栈顶元素
}

void InitStack(PStack pS){         //栈的初始化,
	pS->pBot=(PNode)malloc(sizeof(Node));    
	if(pS->pBot == NULL){
		printf("初始化栈失败");
		exit(-1);
	}else{
		pS->pTop =pS->pBot;
		pS->pBot->pNext=NULL;
	}
}

bool isEmpty(PStack pS){
	if(pS->pTop == pS->pBot){
		return true;
	}else{
		return false;
	}
}

/*进栈操作*/
void Push(PStack pS,int val){
	PNode pNew = (PNode)malloc(sizeof(Node));
	if(pNew == NULL){
		printf("程序内存分配失败");
		exit(-1);
	}else{
		pNew->data=val;
		pNew->pNext=pS->pTop;
		pS->pTop= pNew;
	}
}

/*出栈操作*/
bool Pop(PStack pS,DataType * x){
	if(isEmpty(pS)){
		printf("栈里面没有数据了.");
		return false;
	}else{
		PNode p=pS->pTop;
		*x=p->data;
		pS->pTop=p->pNext;
		free(p);
		return true;
	}
}

/*获取栈顶元素的值*/
DataType GetTop(PStack pS){
	if(isEmpty(pS)){
		printf("目前栈是空的,请稍后在试.");
		exit(-1);
	}else{
		PNode p=pS->pTop;
		return p->data;
	}
}

/*打印栈列表*/
void show_Stack(PStack pS){
	int cnt=0;
	PNode P = pS->pTop;
	printf("栈的列表信息如下:\n");
	while(P != pS->pBot){
			printf("%d ",P->data);
			P = P->pNext;
			cnt++;
		}
	printf("\n栈的长度是%d:\n",cnt);
}