【数据结构】 栈的基本操作

前端之家收集整理的这篇文章主要介绍了【数据结构】 栈的基本操作前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
  1. /*
  2. ===============================================================================================
  3. 栈的基本操作
  4. By~fanxingzju 2014-04-14
  5. 1.构造一个空栈Stack
  6. 2.销毁栈Stack
  7. 3.把Stack置为空栈
  8. 4.若栈Stack为空栈,则返回true,否则返回false
  9. 5.用length返回栈中元素的个数,即栈的长度
  10. 6.若栈不为空,则用elem返回Stack的栈顶元素,并返回true,否则返回false
  11. 7.向栈顶压入值为elem为新元素
  12. 8.若栈不为空,则删除S的栈顶元素,用elem返回其值,并返回true,否则返回false
  13.  
  14. ===============================================================================================
  15. 说明:
  16. 1.我在大部分函数添加了 “if (NULL == Stack.base)”的条件判断,但正常使用时,这段代码不是必须的,可以删除
  17. 2.在Push操作时,对于栈满的情况,进行了追加内存的操作。为了保证堆栈的顺序,引入了中间堆栈tempStack
  18. */
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21.  
  22. #define STACK_MAX_SIZE 10
  23. #define STACK_INCREMENT 3
  24. #define SElemType int
  25.  
  26. typedef struct SqStack
  27. {
  28. SElemType *base;
  29. SElemType *top;
  30. int stacksize;
  31. }SqStack;
  32.  
  33. //1.构造一个空栈Stack
  34. bool InitStack(SqStack &Stack)
  35. {
  36. Stack.base = new SElemType[STACK_MAX_SIZE];
  37. if (!Stack.base)
  38. {
  39. printf("InitStack()函数运行,内存分配失败\n");
  40. system("pause");
  41. exit(-1);
  42. }
  43. Stack.top = Stack.base;
  44. Stack.stacksize = STACK_MAX_SIZE;
  45. printf("InitStack()函数执行,空栈构造成功\n");
  46. return true;
  47. }
  48.  
  49. //2.销毁栈Stack
  50. bool DestoyStack(SqStack &Stack)
  51. {
  52. Stack.top = Stack.base;
  53. delete[] Stack.base;
  54. Stack.base = NULL;
  55. Stack.top = NULL;
  56. printf("DestoryStack()函数执行,栈销毁成功\n");
  57. return true;
  58. }
  59.  
  60. //3.把Stack置为空栈
  61. bool ClearStack(SqStack &Stack)
  62. {
  63. if (NULL == Stack.base)
  64. {
  65. printf("ClearStack()函数执行,栈不存在,无法清空\n");
  66. return false;
  67. }
  68. Stack.top = Stack.base;
  69. printf("ClearStack()函数执行,栈清空成功\n");
  70. return true;
  71. }
  72.  
  73. //4.若栈Stack为空栈,则返回true,否则返回false
  74. bool StackEmpty(SqStack Stack)
  75. {
  76. if (NULL == Stack.base)
  77. {
  78. printf("StackEmpty()函数执行,栈不存在!!\n");
  79. system("pause");
  80. exit(-1);
  81. }
  82. if (Stack.top == Stack.base)
  83. {
  84. printf("StackEmpty()函数执行,栈为空栈\n");
  85. return true;
  86. }
  87. printf("StackEmpty()函数执行,栈不为空\n");
  88. return false;
  89. }
  90.  
  91. //5.返回栈中元素的个数,即栈的长度
  92. bool StackLength(SqStack Stack,int &length)
  93. {
  94. if (NULL == Stack.base)
  95. {
  96. printf("StackLength()函数执行,栈不存在,返回长度失败\n");
  97. return false;
  98. }
  99. length = Stack.top - Stack.base;
  100. printf("Stacklength()函数执行,栈的长度为 %d \n",length);
  101. return true;
  102. }
  103.  
  104. //6.若栈不为空,则用elem返回Stack的栈顶元素,并返回true,否则返回false
  105. bool GetTopStack(SqStack Stack,SElemType &elem)
  106. {
  107. if (NULL == Stack.base)
  108. {
  109. printf("GetTop()函数执行,栈不存在,获取栈顶元素失败\n");
  110. return false;
  111. }
  112. if (Stack.base == Stack.top)
  113. {
  114. printf("GetTop()函数执行,栈为空,获取栈顶元素失败\n");
  115. return false;
  116. }
  117. elem = *(Stack.top - 1);
  118. printf("GetTop()函数执行,栈顶元素为: %d \n",elem);
  119. return true;
  120. }
  121.  
  122. //7.7.向栈顶压入值为elem为新元素
  123. bool PushStack(SqStack &Stack,SElemType elem)
  124. {
  125. if (NULL == Stack.base)
  126. {
  127. printf("PushStack()函数执行,栈不存在,向栈顶压入元素失败\n");
  128. system("pause");
  129. exit(-1);
  130. }
  131. if (Stack.top - Stack.base >= Stack.stacksize)
  132. {
  133. printf("PushStack()函数执行,原始栈已满,重新给栈分配更大的空间\n");
  134. SqStack tempStack,newStack;
  135. tempStack.base = new SElemType[Stack.stacksize];
  136. newStack.base = new SElemType[Stack.stacksize + STACK_INCREMENT];
  137. if ((!tempStack.base)||(!newStack.base))
  138. {
  139. printf("PushStack()函数运行,内存分配失败\n");
  140. system("pause");
  141. exit(-1);
  142. }
  143. tempStack.top = tempStack.base;
  144. tempStack.stacksize = Stack.stacksize;
  145. newStack.top = newStack.base;
  146. newStack.stacksize = Stack.stacksize + STACK_INCREMENT;
  147. while(Stack.top != Stack.base)
  148. {
  149. SElemType temp = *--Stack.top;
  150. *tempStack.top++ = temp;
  151. }
  152. while(tempStack.top != tempStack.base)
  153. {
  154. SElemType temp = *--tempStack.top;
  155. *newStack.top++ = temp;
  156. }
  157. delete[] Stack.base;
  158. delete[] tempStack.base;
  159. Stack = newStack;
  160. }
  161.  
  162. *Stack.top++ = elem;
  163. printf("PushStack()函数执行,元素 %d 压入栈顶成功\n",elem);
  164. return true;
  165. }
  166.  
  167. //8.若栈不为空,则删除S的栈顶元素,用elem返回其值,并返回true,否则返回false
  168. bool PopStack(SqStack &Stack,SElemType &elem)
  169. {
  170. if (NULL == Stack.base)
  171. {
  172. printf("PopStack()函数执行,栈不存在,弹出栈顶元素失败\n");
  173. system("pause");
  174. exit(-1);
  175. }
  176. if (Stack.base == Stack.top)
  177. {
  178. printf("PopStack()函数执行,栈为空,弹出栈顶元素失败\n");
  179. return false;
  180. }
  181. elem = *--Stack.top;
  182. printf("PopStack()函数执行,弹出栈顶元素成功,栈顶的元素为: %d \n",elem);
  183. return true;
  184. }
  185.  
  186. int main()
  187. {
  188. SqStack Stack;
  189. InitStack(Stack);
  190.  
  191. for (int i = 0; i != 30; ++i)
  192. {
  193. PushStack(Stack,i);
  194. }
  195. StackEmpty(Stack);
  196.  
  197. int length = 0;
  198. StackLength(Stack,length);
  199.  
  200. SElemType elem;
  201. GetTopStack(Stack,elem);
  202.  
  203. while(PopStack(Stack,elem))
  204. {
  205. //printf("PopStack()函数执行,弹出栈顶元素成功,栈顶的元素为: %d \n",elem);
  206. }
  207.  
  208. ClearStack(Stack);
  209. DestoyStack(Stack);
  210.  
  211. system("pause");
  212. return 0;
  213. }

猜你在找的数据结构相关文章