【数据结构】-链栈(无头结点)

逃离我推掉我的手 2023-02-28 05:25 52阅读 0赞

### 链栈-无头结点 ###

*  1.头文件及类型定义
 *  2.链栈类型定义
 *  3.函数声明
 *  4.基本操作
 *   *  4.1 初始化链栈
     *  4.2 判空
     *  4.3 入栈
     *  4.4 出栈
     *  4.5 读取栈顶元素
     *  4.6 main函数
 *  5.小结

# 1.头文件及类型定义 #

#include<stdio.h>
    #include<stdlib.h>
    #define ElemType int

# 2.链栈类型定义 #

typedef struct LinkStackNode {
        		//链栈类型定义
    	ElemType data;					//数据域
    	struct LinkStackNode* next;		//指针域
    }*LiStack;

# 3.函数声明 #

/*函数声明*/
    bool InitLinkStack(LiStack& S);			//1.初始化链栈
    bool LiStackEmpty(LiStack S);			//2.判空
    bool Push(LiStack& S, ElemType e);		//3.入栈
    bool Pop(LiStack& S, ElemType& e);		//4.出栈
    bool GetTop(LiStack S, ElemType& e);	//5.读取栈顶元素

# 4.基本操作 #

## 4.1 初始化链栈 ##

//1.初始化链栈(不带头结点)
    bool InitLinkStack(LiStack& S) {
        
    	S = NULL;		//链栈初始化为空，暂时没有任何结点
    	return true;
    }

## 4.2 判空 ##

//2.判空
    bool LiStackEmpty(LiStack S) {
        
    	return (S == NULL);
    }

## 4.3 入栈 ##

//3.入栈操作
    bool Push(LiStack& S, ElemType e) {
        
    	LiStack p = (LiStack)malloc(sizeof(LiStack));
    	if (p == NULL)
    		return false;	//内存分配失败
    	p->data = e;
    	p->next = S;
    	S = p;
    	return true;
    }

## 4.4 出栈 ##

//4.出栈操作
    bool Pop(LiStack& S, ElemType& e) {
        
    	if (S == NULL)
    		return false;	//栈空，报错
    	LiStack p = S;
    	e = p->data;
    	S = p->next;
    	free(p);
    	return true;
    }

## 4.5 读取栈顶元素 ##

//5.读取栈顶元素操作
    bool GetTop(LiStack S,ElemType& e) {
        
    	if (S == NULL)
    		return false;	//栈空，报错
    	e = S->data;
    	return true;
    }

## 4.6 main函数 ##

int main() {
        
    	LiStack S;		//声明一个链栈
    
    	/*1、初始化栈*/
    	InitLinkStack(S);
    
    	/*2、判空*/
    	if (LiStackEmpty(S))
    		printf("当前链栈为空！\n");
    	else
    		printf("当前链栈非空！\n");
    
    	/*3、入栈操作*/
    	ElemType e1;
    	printf("请输入入栈元素的值：");
    	scanf("%d", &e1);
    	if (Push(S, e1))
    		printf("新元素入栈成功！\n");
    	else
    		printf("栈已满,新元素入栈失败！\n");
    
    	
    	/*4、读取栈顶元素*/
    	ElemType e2 = -1;
    	if (GetTop(S, e2))
    		printf("读取栈顶元素成功，当前栈顶元素值为：%d\n", e2);
    	else
    		printf("栈已空，读取栈顶元素失败！\n");
    
    	/*5、出栈操作*/
    	ElemType e3 = -1;
    	if (Pop(S, e3))
    		printf("栈顶元素出栈成功，出栈元素值为：%d\n", e3);
    	else
    		printf("栈已空，栈顶元素出栈失败！\n");
    
    	/*6、读取栈顶元素*/
    	ElemType e4 = -1;
    	if (GetTop(S, e4))
    		printf("读取栈顶元素成功，当前栈顶元素值为：%d\n", e4);
    	else
    		printf("栈已空，读取栈顶元素失败！\n");
    
    	return 0;
    }

# 5.小结 #

1.  **关于链栈**  
    链栈本质上其实是操作受限的单链表,下列操作等价：  
    （1）*入栈操作* <–>*头插法* 。  
    （2）*出栈操作* <–> *指定结点的删除操作*(每次都是删除第一个结点)
2.  **链栈与顺序栈的相关说明**  
    同链表一样，链栈一般不存在栈满上溢的情况，而顺序栈同顺序表一样，存在栈满上溢的情况，且不便于结点的插入与删除。