文章目录

• 前言
• 一、链栈的定义
• 二、链栈的结构
• 三、链栈的常用操作
• 结语
• 附录

---

前言

        前面完成了栈结构中顺序栈的学习，下面开始对栈结构中的链栈进行学习。

一、链栈的定义

        栈是限定仅在表尾进行插人或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的，因此栈又称为后进先出的线性表，简称LIFO结构。而链栈就是使用链式结构来实现栈，链栈的空间可以是不连续分配。

二、链栈的结构

结构图

代码描述

#define ElemType int   //结点内数据类型//链栈的结点
typedef struct StackNode
{ElemType data;          //数据域struct StackNode *next; //指针域
}StackNode;typedef StackNode* LinkStack; //链栈指针

三、链栈的常用操作

初始化

//初始化栈
void InitStack(LinkStack *s)
{*s = NULL;
}

入栈

//入栈
void Push(LinkStack *s, ElemType x)
{//为栈结点分配空间StackNode *t = (StackNode*)malloc(sizeof(StackNode));assert(t != NULL);//将数据存入这个栈结点t->data = x;if(*s == NULL) //如果链栈里面的结点为空{*s = t;         //将链栈的指针指向这个结点t->next = NULL;}else  //如果栈里面已经有结点，直接进行头插{t->next = *s;//将新结点连接上之前的结点*s = t;//将栈指针指向最新的栈结点}
}

显示栈内数据

//显示链栈内的所以元素
void Show(LinkStack *s)
{StackNode *p = *s;//指向栈顶while(p != NULL)//向下搜索栈结点，如果找到则将其数据输出{printf("%dn",p->data);p = p->next;}printf("n");
}

出栈

//出栈（头删）
void Pop(LinkStack *s)
{StackNode *p = *s;//指向新的栈顶*s = p->next;//删除结点free(p);p = NULL;
}

判断栈是否为空

//判断栈是否为空
bool IsEmpty(LinkStack *s)
{//如果栈顶top的值等于0，则表示栈为空if(*s==NULL)return true;elsereturn false;
}

获取栈顶元素

//获取栈顶元素
bool GetTop(LinkStack *s, ElemType *v)
{//如果栈为空，则获取不了栈顶元素if(IsEmpty(s)){	printf("栈空间已空,不能取栈顶元素.n");return false;}//获取栈顶元素*v = (*s)->data;return true;
}

获取栈内元素个数

//获取栈内元素的个数
int Length(LinkStack *s)
{int len=0;StackNode *p = *s;while(p!=NULL){//不断下移查找元素个数p=p->next;  len++;}return len;
}

清空栈

//清空栈
void Clear(LinkStack *s)
{while(*s!=NULL){//只要栈内还有元素就出栈Pop(s);}
}

销毁栈

//销毁栈
void Destroy(LinkStack *s)
{//此处链栈当将栈清空，相当于销毁Clear(s);
}

结语

        对链栈的介绍就到这里，希望这篇文章能够给努力学习的你一些帮助。

附录

以下提供链栈的测试代码

LinkStack.h

#ifndef __LINKSTACK_H__
#define __LINKSTACK_H__#include<stdio.h>
#include<malloc.h>
#include<assert.h>#define ElemType int   //结点内数据类型//链栈的结点
typedef struct StackNode
{ElemType data;          //数据域struct StackNode *next; //指针域
}StackNode;typedef StackNode* LinkStack; //链栈指针void InitStack(LinkStack *s);
void Push(LinkStack *s, ElemType x);
void Show(LinkStack *s);
void Pop(LinkStack *s);
bool IsEmpty(LinkStack *s);
bool GetTop(LinkStack *s, ElemType *v);
int Length(LinkStack *s);
void Clear(LinkStack *s);
void Destroy(LinkStack *s);#endif //__LINKSTACK_H__

LinkStack.cpp

#include"LinkStack.h"//初始化栈
void InitStack(LinkStack *s)
{*s = NULL;
}//入栈
void Push(LinkStack *s, ElemType x)
{//为栈结点分配空间StackNode *t = (StackNode*)malloc(sizeof(StackNode));assert(t != NULL);//将数据存入这个栈结点t->data = x;if(*s == NULL) //如果链栈里面的结点为空{*s = t;         //将链栈的指针指向这个结点t->next = NULL;}else  //如果栈里面已经有结点，直接进行头插{t->next = *s;//将新结点连接上之前的结点*s = t;//将栈指针指向最新的栈结点}
}
//显示链栈内的所以元素
void Show(LinkStack *s)
{StackNode *p = *s;//指向栈顶while(p != NULL)//向下搜索栈结点，如果找到则将其数据输出{printf("%dn",p->data);p = p->next;}printf("n");
}//出栈（头删）
void Pop(LinkStack *s)
{StackNode *p = *s;//指向新的栈顶*s = p->next;//删除结点free(p);p = NULL;
}//判断栈是否为空
bool IsEmpty(LinkStack *s)
{//如果栈顶top的值等于0，则表示栈为空if(*s==NULL)return true;elsereturn false;
}//获取栈顶元素
bool GetTop(LinkStack *s, ElemType *v)
{//如果栈为空，则获取不了栈顶元素if(IsEmpty(s)){	printf("栈空间已空,不能取栈顶元素.n");return false;}//获取栈顶元素*v = (*s)->data;return true;
}//获取栈内元素的个数
int Length(LinkStack *s)
{int len=0;StackNode *p = *s;while(p!=NULL){//不断下移查找元素个数p=p->next;  len++;}return len;
}//清空栈
void Clear(LinkStack *s)
{while(*s!=NULL){//只要栈内还有元素就出栈Pop(s);}
}//销毁栈
void Destroy(LinkStack *s)
{//此处链栈当将栈清空，相当于销毁Clear(s);
}

Main.cpp

#include"LinkStack.h"void main()
{LinkStack st;InitStack(&st);for(int i=1; i<=5; ++i){Push(&st,i);}Show(&st);printf("栈长度：%dn",Length(&st));ElemType v;if(GetTop(&st, &v))printf("栈顶元素：%dnn",v);Pop(&st);Show(&st);Clear(&st);if(IsEmpty(&st))printf("truen");else printf("falsen");Destroy(&st);}