赞
踩
目录
本文参考王卓老师的数据结构视频和严蔚敏老师的《数据结构》
栈:操作受限的线性表,限定仅在表尾进行插入和删除操作的线性表,即后进先出。这一端被称为栈顶,相对地,把另一端称为栈底。
链栈:用链式结构存储的栈(我实际用的是不带头结点的单链表)
例子:类似子弹压入弹夹,后放入的子弹可以先从弹夹弹出来。
代码如下(示例):
注意:我使用的是不带头节点的单链表
typedef struct LinkNode{
int data;//数据域
struct LinkNode *next;//指针域
}stackNode,*LinkStack;
无需new,因为我是不带头结点的单链表
- void initStack(LinkStack &s)
- {
- s=NULL;//不需要头节点
- }
当s==NULL时,栈为空,则返回1;否则,返回0
- 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;
- }
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;
- }
- }
当栈为空的时候,是无法弹出的
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;
- }
- }
当栈不空时,返回第一个节点的数据
- 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;
- }
- #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;
- }
- }
- }
图一
图二
图三
图四
图五
图六
图七
栈是一种操作受限的线性表,虽然操作受限,但是与线性表有点类似,只不过栈的插入和删除都在表尾而已。我实现的链栈其实与不带头节点的链表有很大关系,各位也可以参考下链表来学习链栈。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。