[数据结构与算法]栈的链表实现方式（C++版）

栈的链表实现也有两种,一种是带头结点的链表的实现方式，一种是不带头结点的链表的实现方式。

第一种:(带头结点的栈的实现方式)

基础代码:

#include<stdio.h>
#include<stdlib.h>
#define null NULL 
#define ElemType int
typedef struct LinkStack {
 	ElemType data;
	struct LinkStack *next;  
 }LinkStack; 

栈的初始化:

//初始化
bool initStack(LinkStack **head){
	*head = (LinkStack *)malloc(sizeof(LinkStack));
	if(*head == null){
		return false;
	}
	(*head)->next = null;
	return true;
}

判空：

//判空
bool isEmpty(LinkStack *head){
	return head->next == null;
}

入栈:

//入栈 Push
bool Push(LinkStack *head,ElemType e){
	LinkStack *s = (LinkStack *)malloc(sizeof(LinkStack));
	s->data = e;
	s->next=head->next;
	head->next=s;
	return true;
}

出栈:

//出栈 Pop
bool Pop(LinkStack *head,ElemType &x){
	//判栈空
	if(head->next == null){
		return false; 
	}
	LinkStack *q=head->next;
	x =q->data;
	head->next=q->next;
    free(q);
	return true;
}

获取栈顶元素：

//获取栈顶元素
bool GetTopElem(LinkStack *head,ElemType &x){
	//判空 
	if(head->next == null){
		return false; 
	}
	x=head->next->data;
	return true;
}

栈的删除:

//栈的删除(保留头结点)
bool DeleteStack(LinkStack *head){
	while(head->next!=null){
		LinkStack *q = head->next;
		head->next = q->next;
		free(q);
	}
}

栈的销毁：

//栈的销毁(连头结点一起删除)
bool DestoryStack(LinkStack **head){
	while((*head)->next != null){
		LinkStack *q = (*head)->next;
		(*head)->next = q->next;
		free(q);
	}
	free(*head);
	*head=null; //将main函数中的head指针置为null,避免其成为野指针。
}

栈的打印操作：

//栈的打印操作
void printStack(LinkStack *head){
	while(head->next!=null){
		ElemType data = head->next->data;
		printf("%d\n",data);
		head=head->next;
	}
}

?测试代码及结果：

int main(int argc, char *argv[])
{	 
	LinkStack *head = null;
	//初始化栈
	initStack(&head);
	//判断栈空
	bool flag = isEmpty(head);
	printf("%d\n",flag);	
	//打印栈 
	printStack(head); 
	//入栈
	Push(head,1);
	Push(head,2);
	Push(head,3);
	Push(head,4);
	Push(head,5); 
	//判断栈空
	bool flag1 = isEmpty(head);
	printf("%d\n",flag1); 	
	//打印栈
	printStack(head); 
	//出栈
	ElemType e;
    Pop(head,e);
    //打印栈
	printf("--------------\n");	
	printStack(head);
	Pop(head,e); 	
	printf("--------------\n");	
	printStack(head); 
	Push(head,8); 
	printf("--------------\n");	
	printStack(head); 
	GetTopElem(head,e);
	printf("栈顶元素是%d\n",e);	
	GetTopElem(head,e);
	printf("栈顶元素是%d\n",e);
	//判断栈空
	bool flag2 = isEmpty(head);
	printf("%d\n",flag2); 
	//清空栈 
	DeleteStack(head); 
	//判断栈空
	bool flag3 = isEmpty(head);
	printf("%d\n",flag3); 
	//销毁链表
	 DestoryStack(&head); 
	 if(head == null){
	 	printf("链表销毁成功\n");
 	} 
	return 0;
}

第二种(不带头结点的栈的实现方式):

栈的初始化：

//初始化
bool initStack(LinkStack **head){
	*head = null;
	return true;
}

判空:

//判空
bool isEmpty(LinkStack *head){
	return head==null;
}

入栈:(使用二级指针)

//入栈 Push    //得使用二级指针    //如果使用一级指针,会导致我们每次入栈的时候会在堆内存中创建一个结点,而这个结点随着Push函数调用结束,而长久驻留在堆内存中,这种方式会导致内存泄漏,而main函数中的head指针依然指向的null 
bool Push(LinkStack **head,ElemType e){
	LinkStack *s = (LinkStack *)malloc(sizeof(LinkStack));
	s->data = e;
	//入栈的第一个元素 
	if(*head == null){
	s->next = null;
	*head=s;
	}else{
	//入栈非第一个元素 
		s->next = *head;
		*head=s;		
	}
	return true;
}

出栈:(使用二级指针)

//出栈 Pop　　 //得用二级指针　  //使用一级指针会导致我们释放了q结点之后,main函数中的head指针依然指向q这块未知内存，导致head指针指向了未知位置,成为了野指针，程序不再受控。 
bool Pop(LinkStack **head,ElemType &x){
	//判栈空
	if(*head == null){
		return false; 
	}
	LinkStack *q=*head;
	x =q->data;
	*head=q->next;
	free(q);
	return true;
}

获取栈顶元素:

//获取栈顶元素
bool GetTopElem(LinkStack *head,ElemType &x){
	//判空 
	if(head == null){
		return false; 
	}
	x=head->data;
	return true;
}

栈的销毁:

//栈的销毁
bool DestoryStack(LinkStack **head){
	while(*head != null){
		LinkStack *q = *head;
		*head = q->next;
		free(q);
	}
}

栈的打印:

//栈的打印操作
void printStack(LinkStack *head){
	while(head != null){
		ElemType data = head->data;
		printf("%d\n",data);
		head=head->next;
	}
}

测试代码及结果：

int main(int argc, char *argv[])
{	 
	LinkStack *head;
	
	//初始化栈
	initStack(&head);
	//判断栈空
	bool flag1 = isEmpty(head);
	printf("%d\n",flag1);
	
	//入栈
	Push(&head,1);
	Push(&head,2);
	Push(&head,3);
	Push(&head,4);
	Push(&head,5); 
	
	//判断栈空
	bool flag2 = isEmpty(head);
	printf("%d\n",flag2); 	
	//打印栈
	printf("------------------\n");
	printStack(head); 
		
	//出栈
	ElemType e;
    Pop(&head,e);
    //打印栈
	printf("--------------\n");	
	printStack(head);
	Pop(&head,e); 	
	printf("--------------\n");	
	printStack(head); 
	Push(&head,8); 
	printf("--------------\n");
	printStack(head); 		
	
	//获取栈顶元素 
	GetTopElem(head,e);
	printf("栈顶元素是%d\n",e);	
	GetTopElem(head,e);
	printf("栈顶元素是%d\n",e);

	//判断栈空
	bool flag3 = isEmpty(head);
	printf("%d\n",flag3);  
	//销毁栈 
	DestoryStack(&head);
	
	//判断栈空
	bool flag4 = isEmpty(head);
	printf("%d\n",flag4);  
	 
	if(head == null){
	 	printf("栈销毁成功\n");
 	} 
	return 0;	
}

总结: 栈的链表实现方式中，带头结点的实现方式比不带头结点的实现方式简单、方便。（即第一种方式优于第二种方式）