当前位置:   article > 正文

链栈的基本操作(超详细)

链栈

目录

前言

一.链栈的定义 

二、链栈的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,因为我是不带头结点的单链表

  1. void initStack(LinkStack &s)
  2. {
  3. s=NULL;//不需要头节点
  4. }

3.2判断链栈是否为空 

当s==NULL时,栈为空,则返回1;否则,返回0 

  1. int stackEmpty(LinkStack s)
  2. {
  3. if(s==NULL)
  4. return 1;
  5. return 0;
  6. }

3.3求链栈的长度 

长度表示有多少个节点

  1. int stackLength(LinkStack s)
  2. {
  3. int sum=0;
  4. stackNode *temp=s;
  5. while(temp!=NULL)
  6. {
  7. sum++;
  8. temp=temp->next;
  9. }
  10. return sum;
  11. }

3.4 链栈的入栈

p是新节点

关键处在于当栈为空的时候,p就是第一个节点;而当栈不为空时,则让p的next指针指向s,而s更新到p节点,相当于还是让p作为第一个节点

  1. void push(LinkStack &s,int e)
  2. {
  3. stackNode *p=new stackNode;
  4. p->data=e;
  5. p->next=NULL;
  6. if(s==NULL)
  7. s=p;
  8. else
  9. {
  10. p->next=s;
  11. s=p;
  12. }
  13. }

3.4 链栈的出栈

当栈为空的时候,是无法弹出的

new一个p节点

而当栈不空时,则让p指向s的第一个节点,更新s,使s指向下一个节点,在删掉p

  1. void pop(LinkStack &s,int &e)
  2. {
  3. stackNode *p=new stackNode;
  4. if(s==NULL)
  5. {
  6. cout<<"栈为空,无法弹出"<<endl;
  7. }
  8. else
  9. {
  10. p=s;
  11. e=p->data;
  12. s=s->next;
  13. delete p;
  14. cout<<"成功弹出栈顶元素"<<endl;
  15. }
  16. }

3.5求栈顶元素 

 当栈不空时,返回第一个节点的数据

  1. int top(LinkStack s)
  2. {
  3. if(s==NULL)
  4. return -1;
  5. return s->data;
  6. }

3.6销毁栈

  1. void DestoryStack(LinkStack &S)
  2. {
  3. stackNode *p;
  4. while(S)
  5. {
  6. p=S;
  7. S=S->next;
  8. delete p;
  9. }
  10. S=NULL;
  11. cout<<"成功销毁"<<endl;
  12. }

四.链栈的具体实现 

  1. #include <iostream>
  2. using namespace std;
  3. //不带头节点的
  4. typedef struct LinkNode{
  5. int data;//数据域
  6. struct LinkNode *next;//指针域
  7. }stackNode,*LinkStack;
  8. void initStack(LinkStack &s)
  9. {
  10. s=NULL;//不需要头节点
  11. }
  12. int stackEmpty(LinkStack s)
  13. {
  14. if(s==NULL)
  15. return 1;
  16. return 0;
  17. }
  18. int stackLength(LinkStack s)
  19. {
  20. int sum=0;
  21. stackNode *temp=s;
  22. while(temp!=NULL)
  23. {
  24. sum++;
  25. temp=temp->next;
  26. }
  27. return sum;
  28. }
  29. void push(LinkStack &s,int e)
  30. {
  31. stackNode *p=new stackNode;
  32. p->data=e;
  33. p->next=NULL;
  34. if(s==NULL)
  35. s=p;
  36. else
  37. {
  38. p->next=s;
  39. s=p;
  40. }
  41. }
  42. void pop(LinkStack &s,int &e)
  43. {
  44. stackNode *p=new stackNode;
  45. if(s==NULL)
  46. {
  47. cout<<"栈为空,无法弹出"<<endl;
  48. }
  49. else
  50. {
  51. p=s;
  52. e=p->data;
  53. s=s->next;
  54. delete p;
  55. cout<<"成功弹出栈顶元素"<<endl;
  56. }
  57. }
  58. int top(LinkStack s)
  59. {
  60. if(s==NULL)
  61. return -1;
  62. return s->data;
  63. }
  64. //销毁栈
  65. //所有节点
  66. void DestoryStack(LinkStack &S)
  67. {
  68. stackNode *p;
  69. while(S)
  70. {
  71. p=S;
  72. S=S->next;
  73. delete p;
  74. }
  75. S=NULL;
  76. cout<<"成功销毁"<<endl;
  77. }
  78. void menu()
  79. {
  80. cout<<"**************************"<<endl;
  81. cout<<"1.初始化"<<endl;
  82. cout<<"2.判断栈是否为空"<<endl;
  83. cout<<"3.求栈的长度"<<endl;
  84. cout<<"4.销毁栈"<<endl;
  85. cout<<"5.入栈"<<endl;
  86. cout<<"6.出栈"<<endl;
  87. cout<<"7.求栈顶元素"<<endl;
  88. cout<<"8.退出"<<endl;
  89. cout<<"**************************"<<endl;
  90. }
  91. int main()
  92. {
  93. int choice;
  94. LinkStack s;
  95. int e1,e2;
  96. while(1)
  97. {
  98. menu();
  99. cin>>choice;
  100. switch(choice)
  101. {
  102. case 1:
  103. initStack(s);
  104. cout<<"初始化成功"<<endl;
  105. break;
  106. case 2:
  107. if(stackEmpty(s))
  108. cout<<"栈为空"<<endl;
  109. else
  110. cout<<"栈不为空"<<endl;
  111. break;
  112. case 3:
  113. cout<<"栈的长度为"<<stackLength(s)<<endl;
  114. break;
  115. case 4:
  116. DestoryStack(s);
  117. break;
  118. case 5:
  119. cout<<"请输入想要入栈的元素值:"<<endl;
  120. cin>>e1;
  121. push(s,e1);
  122. cout<<"入栈成功"<<endl;
  123. break;
  124. case 6:
  125. pop(s,e2);
  126. cout<<"弹出的元素为"<<e2<<endl;
  127. break;
  128. case 7:
  129. if(top(s)!=-1)
  130. cout<<"栈顶元素为"<<top(s)<<endl;
  131. else
  132. cout<<"栈为空"<<endl;
  133. break;
  134. case 8:
  135. cout<<"成功退出"<<endl;
  136. exit(0);
  137. default:
  138. cout<<"输入有误,请重新输入"<<endl;
  139. break;
  140. }
  141. }
  142. }

五.测试结果

        图一

 

        图二 

 

         图三

        图四

 

        图五

 

        图六

 

        图七

六、总结 

        栈是一种操作受限的线性表,虽然操作受限,但是与线性表有点类似,只不过栈的插入和删除都在表尾而已。我实现的链栈其实与不带头节点的链表有很大关系,各位也可以参考下链表来学习链栈。

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/444081
推荐阅读
相关标签
  

闽ICP备14008679号