深圳幻海软件技术有限公司 欢迎您！
更多

顺序栈的基本操作（超详细）

2023-06-25

cout endl base
目录前言一、顺序栈的定义二、顺序栈的c++语言结构描述表示三、顺序栈中基本操作的实现3.1顺序栈的初始化 3.2判断顺序栈是否为空3.3求顺序栈的长度3.4清空顺序栈3.5销毁顺序栈3.6顺序栈的入栈3.7顺序栈的出栈3.8求栈顶元素3.9遍历顺序栈  四、顺序栈的代码

目录

前言

一、顺序栈的定义

二、顺序栈的c++语言结构描述表示

三、顺序栈中基本操作的实现

3.1顺序栈的初始化 

3.2判断顺序栈是否为空

3.3求顺序栈的长度

3.4清空顺序栈

3.5销毁顺序栈

3.6顺序栈的入栈

3.7顺序栈的出栈

3.8求栈顶元素

3.9遍历顺序栈 

 四、顺序栈的代码实现

五、测试结果

五、总结

前言

本文参考王卓老师的数据结构视频和严蔚敏老师的《数据结构》

一、顺序栈的定义

栈：操作受限的线性表，限定仅在表尾进行插入和删除操作的线性表，即后进先出。这一端被称为栈顶，相对地，把另一端称为栈底。

顺序栈：用顺序结构存储的栈

例子：类似子弹压入弹夹，后放入的子弹可以先从弹夹弹出来。

特点：简单方便，但是容易溢出（上溢或者下溢）

二、顺序栈的c++语言结构描述表示

代码如下（示例）：

typedef struct sqstack{
    int *top;//栈顶指针
    int *base;//栈底指针
    int stackSize;//栈的最大容量 
}stack;

三、顺序栈中基本操作的实现

3.1顺序栈的初始化 

数组用c++的new来动态开辟

当内存不够的时候，也即是s.base为空，则直接结束

不为空的时候，则栈的栈顶指针与栈底指针都指向同一位置

代码如下（示例）：

  1. void initStack(stack &s)
  2. {
  3. s.base=new int[MaxSize];
  4. if(!s.base)exit(0);//内存分配失败，结束
  5. s.top=s.base;//初始的时候栈的top与base相等 
  6. s.stackSize=MaxSize;//栈的最大容量
  7. }

3.2判断顺序栈是否为空

栈顶指针与栈底指针都指向同一位置，即s.base==s.top的时候，则栈为空，返回1

否则，不为空，返回0

 代码如下（示例）：

  1. int isEmpty(stack s)
  2. {
  3. if(s.base==s.top)
  4. return 1;//表示为空，无元素
  5. return 0;//不为空
  6. }

3.3求顺序栈的长度

长度即为有多少个元素，可以用s.top-s.base

 代码如下（示例）：

  1. int stackLength(stack s)
  2. {
  3. return s.top-s.base;
  4. }

3.4清空顺序栈

当s.base不为空的时候，让s.top(栈顶指针)直接指向s.base（栈底）,则把所有的元素逻辑上清空了

而当s.base为空的时候，则栈已经被销毁了，无需清空

 代码如下（示例）：

  1. void CleanStack(stack &s)
  2. {
  3. if(s.base)
  4. {
  5. s.top=s.base;
  6. cout<<"成功清空"<<endl;
  7. }
  8. else
  9. cout<<"栈已经被销毁，无需清空"<<endl;
  10. }

3.5销毁顺序栈

从物理层次销毁

也即是用delete将整个s.base从内存中删除

 代码如下（示例）：

  1. void DestoryStack(stack &s)
  2. {
  3. if(s.base)
  4. {
  5. delete s.base;
  6. s.stackSize=0;
  7. s.base=NULL;
  8. s.top=NULL;
  9. cout<<"成功销毁"<<endl;
  10. }
  11. else
  12. cout<<"栈已经被销毁，无需销毁"<<endl;
  13. }

3.6顺序栈的入栈

首先判断栈是否已经满了，如果满了则无法入栈，否则可以入栈

 代码如下（示例）：

  1. void push(stack &s,int e)
  2. {
  3. if((s.top-s.base)==s.stackSize)
  4. cout<<"栈满了，无法添加新元素"<<endl;
  5. else
  6. {
  7. *(s.top)=e;
  8. s.top++;
  9. cout<<"添加成功"<<endl;
  10. }
  11. }

3.7顺序栈的出栈

首先判断栈是否为空，如果为空，则无法出栈，否则可以出栈 

  代码如下（示例）：

  1. void pop(stack &s,int &e)
  2. {
  3. if(isEmpty(s))
  4. {
  5. cout<<"栈为空，无法弹出"<<endl;
  6. }
  7. else
  8. {
  9. s.top--;
  10. e=*(s.top);
  11. cout<<"成功弹出"<<endl; 
  12. }
  13. }

3.8求栈顶元素

 先判断栈是否为空，为空则无法求栈顶元素，否则可以求栈顶元素

  代码如下（示例）：

  1. int top(stack s)
  2. {
  3. if(isEmpty(s))
  4. {
  5. cout<<"栈为空，没有栈顶元素"<<endl;
  6. return -1;
  7. }
  8. else
  9. {
  10. s.top--;
  11. return *(s.top);
  12. }
  13. }

3.9遍历顺序栈 

从栈底开始遍历 

  代码如下（示例）：

  1. void traverse(stack s)
  2. {
  3. int length=stackLength(s);
  5. if(length>0)
  6. {
  7. cout<<"顺序栈的元素为:(从栈底开始遍历)"<<endl;
  8. for(int i=0;i<length;i++)
  9. cout<<s.base[i]<<" ";
  10. }
  11. else
  12. cout<<"顺序栈为空"<<endl;
  13. }

 四、顺序栈的代码实现

  1. #include <iostream>
  2. using namespace std;
  3. const int MaxSize=100;
  4. typedef struct sqstack{
  5. int *top;//栈顶指针
  6. int *base;//栈底指针
  7. int stackSize;//栈的最大容量 
  8. }stack;
  9. void initStack(stack &s)
  10. {
  11. s.base=new int[MaxSize];
  12. if(!s.base)exit(0);//内存分配失败，结束
  13. s.top=s.base;//初始的时候栈的top与base相等 
  14. s.stackSize=MaxSize;//栈的最大容量
  15. } 
  16. int isEmpty(stack s)
  17. {
  18. if(s.base==s.top)
  19. return 1;//表示为空，无元素
  20. return 0;//不为空
  21. } 
  22. int stackLength(stack s)
  23. {
  24. return s.top-s.base;
  25. }
  26. void CleanStack(stack &s)
  27. {
  28. if(s.base)
  29. {
  30. s.top=s.base;
  31. cout<<"成功清空"<<endl;
  32. }
  33. else
  34. cout<<"栈已经被销毁，无需清空"<<endl;
  35. }
  36. void DestoryStack(stack &s)
  37. {
  38. if(s.base)
  39. {
  40. delete s.base;
  41. s.stackSize=0;
  42. s.base=NULL;
  43. s.top=NULL;
  44. cout<<"成功销毁"<<endl;
  45. }
  46. else
  47. cout<<"栈已经被销毁，无需销毁"<<endl;
  48. }
  49. //入栈
  50. void push(stack &s,int e)
  51. {
  52. if((s.top-s.base)==s.stackSize)
  53. cout<<"栈满了，无法添加新元素"<<endl;
  54. else
  55. {
  56. *(s.top)=e;
  57. s.top++;
  58. cout<<"添加成功"<<endl;
  59. }
  60. } 
  61. //出栈
  62. void pop(stack &s,int &e)
  63. {
  64. if(isEmpty(s))
  65. {
  66. cout<<"栈为空，无法弹出"<<endl;
  67. }
  68. else
  69. {
  70. s.top--;
  71. e=*(s.top);
  72. cout<<"成功弹出"<<endl; 
  73. }
  74. } 
  75. int top(stack s)
  76. {
  77. if(isEmpty(s))
  78. {
  79. cout<<"栈为空，没有栈顶元素"<<endl;
  80. return -1;
  81. }
  82. else
  83. {
  84. s.top--;
  85. return *(s.top);
  86. }
  87. }
  88. void traverse(stack s)
  89. {
  90. int length=stackLength(s);
  92. if(length>0)
  93. {
  94. cout<<"顺序栈的元素为:(从栈底开始遍历)"<<endl;
  95. for(int i=0;i<length;i++)
  96. cout<<s.base[i]<<" ";
  97. }
  98. else
  99. cout<<"顺序栈为空"<<endl;
  100. } 
  101. void menu()
  102. {
  103. cout<<"**********************************"<<endl;
  104. cout<<"1.初始化"<<endl;
  105. cout<<"2.判断栈是否为空"<<endl;
  106. cout<<"3.求栈的长度"<<endl;
  107. cout<<"4.清空栈"<<endl;
  108. cout<<"5.销毁栈"<<endl;
  109. cout<<"6.入栈"<<endl;
  110. cout<<"7.出栈"<<endl;
  111. cout<<"8.求栈顶元素"<<endl;
  112. cout<<"9.遍历顺序栈"<<endl;
  113. cout<<"10.退出"<<endl;
  114. cout<<"**********************************"<<endl;
  115. }
  116. int main()
  117. {
  118. int choice;
  119. stack s;
  120. int e1,e2;
  121. while(1)
  122. {
  123. menu();
  124. cin>>choice;
  125. switch(choice)
  126. {
  127. case 1:
  128. initStack(s);
  129. cout<<"初始化成功"<<endl;
  130. break;
  131. case 2:
  132. if(isEmpty(s))
  133. cout<<"栈为空"<<endl;
  134. else
  135. cout<<"栈不为空"<<endl; 
  136. break;
  137. case 3:
  138. cout<<"栈的长度为"<<stackLength(s)<<endl;
  139. break;
  140. case 4:
  141. CleanStack(s);
  142. break;
  143. case 5:
  144. DestoryStack(s);
  145. break;
  146. case 6:
  147. cout<<"请输入想要入栈的元素值："<<endl;
  148. cin>>e1;
  149. push(s,e1);
  150. break;
  151. case 7:
  152. pop(s,e2);
  153. cout<<"弹出的元素为"<<e2<<endl;
  154. break;
  155. case 8:
  156. if(top(s)!=-1)
  157. cout<<"栈顶元素为"<<top(s)<<endl;
  158. break;
  159. case 9:
  160. traverse(s);
  161. cout<<endl;
  162. break;
  163. case 10:
  164. cout<<"成功退出"<<endl;
  165. exit(0);
  166. default:
  167. cout<<"输入有误，请重新输入"<<endl;
  168. break;
  169. }
  170. }
  171. }

五、测试结果

                                          图一

                                        图二 

                                        图三

 

                                        图四 

 

                                         图五

                                         图六

                                         图七

                                          图八

                                           图九

                                            图十

                                             图十一

六、总结

        栈是一种操作受限的线性表，虽然操作受限，但是与线性表有点类似，只不过栈的插入和删除都在表尾而已。而我在本文中实现的顺序栈有点类似顺序表。我们也需要注意到顺序栈虽然实现简单，但是其容易发生溢出，在栈满的时候，还要入栈，则会上溢，而在栈空的时候，还要出栈，则会下溢，针对这个问题，我将在下一篇文章的链栈解决这个问题。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览48400 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪