棧的鏈式存儲及基本操作

棧的鏈式存儲結構稱為鏈棧，它是運算受限的單鏈表，其插入和刪除操作僅限制在棧頂進行。

先將練習結果貼下

相關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);
}