栈(Stack)的链式实现详解----线性结构

前面已经学习了线性存储的线性表操作，即元素之间的1对1之间的关系，如线性表的顺序、链式的存储和表示，就是数据元素之间的线性的一个表现。

除了线性表，以线性存储的数据结构还有栈和队列、串、数组和广义表等。

今天主要为大家分享数据结构之中的很重要的一个数据结构，就是------>栈

怎样理解 “栈” 呢？

栈在我们的生活中应用的非常广泛，如平时我们炒菜做菜用的碟子，一般需要放的时候需要一个一个将盘子从下到上给放上去，而用的时候又需要从上到下一个一个给拿出使用。
又如我们所见的手枪的弹夹，我们对弹夹进行装子弹的时候需要一颗颗地将子弹从上到下地摁下去，子弹射出时又会从下到上一个个将子弹弹出去等等，艺术来源于生活嘛，哈哈，生活中有太多栈的应用的实例，大家理解即可。

总结起来栈的特征就是后进先出(LIFO)。
与之对应是队列的特征先进先出(FIFO)。

我们把从下往上进行增加元素的操作称为---->压栈操作
我们又把从上往下往外边减少元素称作为---->出栈操作

因为栈只能从栈顶操作，即增加删除只能从顶部操作，我们也把栈成为操作受限的线性表。

由于教材上已经有栈的顺序实现，虽然是伪代码(看着实在不习惯，哈哈)，然后我实现了栈的链式实现，提供给大家参考。

最后自己添加的以栈顶至栈底输出所有元素(采用辅助栈)实现的，如果有其它小伙伴有其它想法，欢迎评论留言讨论~

链式栈结构体的定义

简单的栈内元素定义和链式栈定义

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

//定义栈内存储的元素Student 
struct Student{
    	
	int id;				//学生id 
	int age;			//学生年龄 
	Student *next;		//指向下一元素的指针 
};


//定义以链式存储的数据栈 
typedef struct Node{
    	
	Student *base;		//定义栈底指针，用于指向栈底元素 
	Student *top;		//定义栈顶指针，用于指向栈顶元素, 它们初始化均为NULL 
}*Stack;

所有方法声明

int initStack(Stack &stack);						//初始化链表栈 
int clearStack(Stack &stack);						//清空栈内的所有数据 
int destroyStack(Stack &stack);						//销毁链表数据栈 
int stackEmpty(Stack &stack);						//判断链表栈是否为NULL 
int stackLength(Stack &stack);						//获取栈长的函数 
int getStackTop(Stack &stack, Student &student);		//获取栈顶元素 
int pushStack(Stack &stack, Student student);			//压栈操作，将一个元素压入栈中 
int popStack(Stack &stack, Student &student);			//出栈操作，将一个元素弹出栈，并以参数student返回 
void printStack(Stack &stack);						//以栈顶到栈底的形式输出栈内所有元素 
void stackTraverse(Stack &stack);					//以栈底到栈顶的形式输出栈内所有元素 

初始化栈操作

栈的初始化操作

//数据结构----初始化链式数据栈操作 
int initStack(Stack &stack)
{
    
	stack = (Node *)malloc(sizeof(Node));			//使用malloc函数动态为数据栈开辟空间 
	stack->base = NULL;					//栈底指针指向NULL 
	stack->top = NULL;					//栈顶指针指向NULL 
	
	return OK;					//返回建栈成功信息 
}

push压栈操作

push压栈操作，根据函数传递的参数将一个数据元素压入栈中

//数据结构----push压栈操作，将一个数据元素压入栈中 
int pushStack(Stack &stack, Student student)
{
    
	Student *student1 = (Student *)malloc(sizeof(Student));		//动态开辟一个元素空间 
	
	student1->id = student.id;				//信息收集，获取将压栈元素的id 
	student1->age = student.age;			//获取将压栈元素的age 
	
	if(stack->base == NULL)					//若栈底为NULL时，说明栈内还没有元素 
	{
    
		stack->base = student1;			//栈底指向该元素student1 
		stack->top = student1;			//栈顶指向该元素student1 
	}
	else									//否则 
	{
    
		stack->top->next = student1; 		//将元素student1压入栈中 
		stack->top = student1;				//栈顶指针指向新元素student1 
	}
	
	stack->top->next = NULL;		//设置下次待压入元素的地址暂为NULL(与链式线性表的增加元素有些许类似) 
	
	return OK;
}

pop出栈操作

出栈操作，将栈顶元素进行弹出 ，并通过函数参数的方式保存弹出的信息供返回

//数据结构----出栈操作，将栈顶元素进行弹出 
int popStack(Stack &stack, Student &student)
{
    
	Student *p = stack->base, *q;		//定义p指针暂时指向栈底元素 
	
	if(stackEmpty(stack)) return ERROR;		//若栈空则返回失败信息 
	
	if(stack->top == stack->base)		//若栈顶指针和栈底指针指向同一元素，表示栈内仅有一个元素 
	{
    
		student = *stack->top;			//以参数的形式保存栈顶元素并返回 
		free(stack->top);			//释放栈顶元素，进行出栈删除 
		stack->base = NULL;				 
		stack->top = NULL;			//栈底、顶指针再次指向NULL，代表暂无任何元素 
		return OK;					//返回成功信息 
	}
	
	while(p->next != stack->top)		//若栈内的元素 >= 2
	p = p->next;					//p指针从栈底循环上挪 ，直到p指向指向栈顶元素之下的元素 
	
	q = stack->top;					//q指针指向栈顶元素 
	student = *q;					//将栈顶元素赋值给参数student待返回 
	stack->top = p;						//栈顶指针下挪 
	stack->top->next = NULL;			//设置下次待压入元素的地址暂为NULL
	
	free(q);						//释放原栈顶指针 
	return OK;							//返回成功信息 
	
}

自顶向底打印所有元素

采用辅助栈的方式自栈顶至栈底的方式输出所有元素

//数据结构----自栈顶至栈底的方式输出所有元素 
void printStack(Stack &stack)
{
    
	int i = 0;
	Stack new_stack; 
	initStack(new_stack);		//定义一个新的栈，并且进行初始化 
	
	Student student;			//定义元素变量student 
	printf("自栈顶到栈底的数据元素排列:\n");
	
	
	//stack出栈顺序： A、B、C、D、E ----> 结果：stack栈空 
	//同时new_stack压栈顺序： A、B、C、D、E ----> 结果：new_stack已保存原stack栈 
	 
	while(!(stackEmpty(stack)))		//若原栈不为NULL，重复循环 
	{
    
		popStack(stack, student);  				 //出栈操作 
		printf("id = %d, age = %d.\n", student.id, student.age);	//信息输出 
		pushStack(new_stack, student);			 //压栈操作 
		i++;							// 计数器累加 
	}
	printf("共有数据 %d 条.\n\n", i);		   	//输出结果的个数 
	stack = new_stack;							//进行栈复制，原栈已恢复！ 
	return;						//返回 
}

自底向顶打印所有元素

//数据结构----自栈底至栈顶的方式输出所有元素 
void stackTraverse(Stack &stack)
{
    
	int i = 0;
	Student *student = stack->base;					//定义随机变量指针student指向栈底元素 
	printf("自栈底到栈顶的数据元素排列:\n");
	while(student != NULL)							//循环遍历输出 
	{
    
		printf("id = %d, age = %d.\n", student->id, student->age);
		student = student->next;				//指针随栈进行上挪输出下一元素 
		i++;								//计数器累加 
	}
	printf("共有数据 %d 条.\n\n", i);		//输出累加数据 
	return;
}

获取栈顶元素

获取链式栈的栈顶元素

//数据结构----获取栈顶元素 
int getStackTop(Stack &stack, Student &student)
{
    
	if(stack->top != NULL)					//若栈顶元素不为NULL 
	{
    
		student = *stack->top;				//将栈顶元素传递给参数变量 
		return OK;				//返回成功信息 
	}
	else return ERROR;			//否则返回失败信息 
}

获取链式栈的长度

//数据结构----测试栈长函数 
int stackLength(Stack &stack)
{
    
	Student *student = stack->base;			//定义随机变量元素指向栈底元素 
	int i = 0;
	while(student != NULL)					//循环遍历统计 
	{
    
		student = student->next;			//不断指向栈上层元素 
		i++;					//计数器累加 
	}
	
	return i;					//返回长度 
}

销毁栈、清空栈、判断栈空操作

//数据结构----销毁链式数据栈操作 
int destroyStack(Stack &stack)
{
    
	clearStack(stack);			//清空数据栈内的所有元素 
	free(stack);				//释放栈的地址空间内存 
	stack = NULL;				//设置栈指针为NULL，即销毁
	return OK;					//返回成功信息 
}


//数据结构----清理链式数据栈 
int clearStack(Stack &stack)
{
    
	Student student;						//定义临时元素变量Student 
	while(stack->base != NULL)				//当栈底指针不为NULL时，循环进行出栈操作 
	popStack(stack,student);			//元素出栈 
	
	if(stack->base == NULL) return OK;		//若栈底已为NULL，返回成功信息 
	else return ERROR;					//否则返回失败信息 
}



//数据结构----判断栈空函数 
int stackEmpty(Stack &stack)
{
    
	if(stack->base == NULL && stack->top == NULL)
		return TRUE;						//若栈底指针和栈顶指针指向NULL，返回true 
	else	
		return FALSE;						//否则返回false 
}

在这就不再写这些方法的测试代码了，小伙伴们可以自行参考交流，共同进步，最近也在学习高数和其它课程，可能会更新有点慢，哈哈，下次准备链式队列的实现，加油~