目录
前言
一.链栈的定义
二、链栈的c++语言结构描述表示
三、链栈中基本操作的实现
3.1链栈的初始化
3.2判断链栈是否为空
3.3求链栈的长度
3.4 链栈的入栈
3.4 链栈的出栈
3.5求栈顶元素
3.6销毁栈
四.链栈的具体实现
五.测试结果
六、总结
前言
本文参考王卓老师的数据结构视频和严蔚敏老师的《数据结构》
一.链栈的定义
栈:操作受限的线性表,限定仅在表尾进行插入和删除操作的线性表,即后进先出。这一端被称为栈顶,相对地,把另一端称为栈底。
链栈:用链式结构存储的栈(我实际用的是不带头结点的单链表)
例子:类似子弹压入弹夹,后放入的子弹可以先从弹夹弹出来。
二、链栈的c++语言结构描述表示
代码如下(示例):
注意:我使用的是不带头节点的单链表
typedef struct LinkNode{
int data;//数据域
struct LinkNode *next;//指针域
}stackNode,*LinkStack;
三、链栈中基本操作的实现
3.1链栈的初始化
无需new,因为我是不带头结点的单链表
void initStack(LinkStack &s)
{
s=NULL;//不需要头节点
}
3.2判断链栈是否为空
当s==NULL时,栈为空,则返回1;否则,返回0
int stackEmpty(LinkStack s)
{
if(s==NULL)
return 1;
return 0;
}
3.3求链栈的长度
长度表示有多少个节点
int stackLength(LinkStack s)
{
int sum=0;
stackNode *temp=s;
while(temp!=NULL)
{
sum++;
temp=temp->next;
}
return sum;
}
3.4 链栈的入栈
p是新节点
关键处在于当栈为空的时候,p就是第一个节点;而当栈不为空时,则让p的next指针指向s,而s更新到p节点,相当于还是让p作为第一个节点
void push(LinkStack &s,int e)
{
stackNode *p=new stackNode;
p->data=e;
p->next=NULL;
if(s==NULL)
s=p;
else
{
p->next=s;
s=p;
}
}
3.4 链栈的出栈
当栈为空的时候,是无法弹出的
new一个p节点
而当栈不空时,则让p指向s的第一个节点,更新s,使s指向下一个节点,在删掉p
void pop(LinkStack &s,int &e)
{
stackNode *p=new stackNode;
if(s==NULL)
{
cout<<"栈为空,无法弹出"<<endl;
}
else
{
p=s;
e=p->data;
s=s->next;
delete p;
cout<<"成功弹出栈顶元素"<<endl;
}
}
3.5求栈顶元素
当栈不空时,返回第一个节点的数据
int top(LinkStack s)
{
if(s==NULL)
return -1;
return s->data;
}
3.6销毁栈
void DestoryStack(LinkStack &S)
{
stackNode *p;
while(S)
{
p=S;
S=S->next;
delete p;
}
S=NULL;
cout<<"成功销毁"<<endl;
}
四.链栈的具体实现
#include <iostream>
using namespace std;
//不带头节点的
typedef struct LinkNode{
int data;//数据域
struct LinkNode *next;//指针域
}stackNode,*LinkStack;
void initStack(LinkStack &s)
{
s=NULL;//不需要头节点
}
int stackEmpty(LinkStack s)
{
if(s==NULL)
return 1;
return 0;
}
int stackLength(LinkStack s)
{
int sum=0;
stackNode *temp=s;
while(temp!=NULL)
{
sum++;
temp=temp->next;
}
return sum;
}
void push(LinkStack &s,int e)
{
stackNode *p=new stackNode;
p->data=e;
p->next=NULL;
if(s==NULL)
s=p;
else
{
p->next=s;
s=p;
}
}
void pop(LinkStack &s,int &e)
{
stackNode *p=new stackNode;
if(s==NULL)
{
cout<<"栈为空,无法弹出"<<endl;
}
else
{
p=s;
e=p->data;
s=s->next;
delete p;
cout<<"成功弹出栈顶元素"<<endl;
}
}
int top(LinkStack s)
{
if(s==NULL)
return -1;
return s->data;
}
//销毁栈
//所有节点
void DestoryStack(LinkStack &S)
{
stackNode *p;
while(S)
{
p=S;
S=S->next;
delete p;
}
S=NULL;
cout<<"成功销毁"<<endl;
}
void menu()
{
cout<<"**************************"<<endl;
cout<<"1.初始化"<<endl;
cout<<"2.判断栈是否为空"<<endl;
cout<<"3.求栈的长度"<<endl;
cout<<"4.销毁栈"<<endl;
cout<<"5.入栈"<<endl;
cout<<"6.出栈"<<endl;
cout<<"7.求栈顶元素"<<endl;
cout<<"8.退出"<<endl;
cout<<"**************************"<<endl;
}
int main()
{
int choice;
LinkStack s;
int e1,e2;
while(1)
{
menu();
cin>>choice;
switch(choice)
{
case 1:
initStack(s);
cout<<"初始化成功"<<endl;
break;
case 2:
if(stackEmpty(s))
cout<<"栈为空"<<endl;
else
cout<<"栈不为空"<<endl;
break;
case 3:
cout<<"栈的长度为"<<stackLength(s)<<endl;
break;
case 4:
DestoryStack(s);
break;
case 5:
cout<<"请输入想要入栈的元素值:"<<endl;
cin>>e1;
push(s,e1);
cout<<"入栈成功"<<endl;
break;
case 6:
pop(s,e2);
cout<<"弹出的元素为"<<e2<<endl;
break;
case 7:
if(top(s)!=-1)
cout<<"栈顶元素为"<<top(s)<<endl;
else
cout<<"栈为空"<<endl;
break;
case 8:
cout<<"成功退出"<<endl;
exit(0);
default:
cout<<"输入有误,请重新输入"<<endl;
break;
}
}
}
五.测试结果
图一
图二
图三
图四
图五
图六
图七
六、总结
栈是一种操作受限的线性表,虽然操作受限,但是与线性表有点类似,只不过栈的插入和删除都在表尾而已。我实现的链栈其实与不带头节点的链表有很大关系,各位也可以参考下链表来学习链栈。文章来源:https://www.toymoban.com/news/detail-424714.html
文章来源地址https://www.toymoban.com/news/detail-424714.html
到了这里,关于链栈的基本操作(超详细)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!