当前位置:   article > 正文

栈的实现——链表和数组_c++栈的实现用单链表和数组哪个更好

c++栈的实现用单链表和数组哪个更好

C语言(打印函数采用的c++):

栈的链表实现—— 栈的初始化(创建||清空)、入栈、出栈(获取栈顶元素)
栈的数组实现——初始化、入栈、出栈、清空栈

参考资料:《数据结构与算法分析——C语言描述》 P46

一. 栈的链表实现

StackLinkList.cpp

[cpp]  view plain  copy
  在CODE上查看代码片 派生到我的代码片
  1. /* 
  2. 功能:栈的链表实现: 栈的初始化(创建||清空)、入栈、出栈(获取栈顶元素) 
  3. Date: 2015/01/23 
  4. Author : quinn 
  5. */  
  6. #include <iostream>  
  7. #include <stdlib.h>  
  8. using namespace std;  
  9. typedef int Item;  
  10. typedef struct Node Node;  
  11. typedef Node* Stack;  
  12. struct Node  
  13. {  
  14.     Item item;  
  15.     Node* next;  
  16. };  
  17. void StackPop(Stack s);  
  18. Stack StackInit(Stack s) //创建或清空(初始化)  
  19. {  
  20.     if (s == NULL) //创建  
  21.     {  
  22.         s = (Stack)malloc(sizeof(*s));  
  23.         s->next = NULL;  
  24.     }  
  25.     else //清空  
  26.         while(s->next != NULL)  
  27.             StackPop(s);  
  28.     cout << "初始化成功!" <<endl;  
  29.     return s;  
  30. }  
  31. void StackPush(Stack s, Item item) //入栈  
  32. {  
  33.     Node* tmpNode = (Node*)malloc(sizeof(*tmpNode));  
  34.     tmpNode->item = item;  
  35.     tmpNode->next = s->next;  
  36.     s->next = tmpNode;  
  37.     cout << "PUSH: " << item <<endl;  
  38. }  
  39. Item StackPopAndTop(Stack s) //出栈并返回栈顶元素值  
  40. {  
  41.     if (s->next == NULL)  
  42.     {  
  43.         cout << "空栈,POPAndTop失败" <<endl;  
  44.         return -1; //返回-1作警告  
  45.     }  
  46.     else  
  47.     {  
  48.         Node* firstNode = s->next;  
  49.         s->next = s->next->next;  
  50.         return firstNode->item;  
  51.     }  
  52. }  
  53. void StackPop(Stack s) //出栈  
  54. {  
  55.     if (s->next == NULL)  
  56.     {  
  57.         cout << "空栈,POP失败" <<endl;  
  58.     }  
  59.     else  
  60.     {  
  61.         Node* firstNode = s->next;  
  62.         s->next = s->next->next;  
  63.         free(firstNode);  
  64.     }  
  65. }  
  66. Item StackTop(Stack s) //仅获取栈顶元素  
  67. {  
  68.     if (s->next == NULL)  
  69.     {  
  70.         cout << "空栈,获取栈顶元素失败" <<endl;  
  71.     }  
  72.     return (s->next)->item;  
  73. }  
  74.   
  75. int main()  
  76. {  
  77.     Stack s = NULL;  
  78.     s = StackInit(s);  
  79.     for(int i = 0; i < 10; i++)  
  80.         StackPush(s, i);  
  81.     for(int i = 0; i < 5; i++)  
  82.         cout << StackPopAndTop(s) <<endl;  
  83.     StackInit(s);  
  84.     cout << StackPopAndTop(s) <<endl;  
  85.     system("pause");  
  86.     return 0;  
  87. }  
运行结果:


二. 栈的数组实现

StackArray.cpp
[cpp]  view plain  copy
  在CODE上查看代码片 派生到我的代码片
  1. /* 
  2. 功能:栈的数组实现——初始化、入栈、出栈、清空栈 
  3. 注: 定义栈为空时,栈顶index为 -1;栈满时,栈顶index为栈的长度-1 
  4. Date:2015/01/23 
  5. Author : quinn 
  6. */  
  7. #include <iostream>  
  8. #include "item.h"  
  9. #define STACK_SIZE 10 //认为设定栈的长度为10  
  10. #define FULL_STACK (STACK_SIZE - 1)  
  11. #define EMPTY_STACK (-1)  
  12. using namespace std;  
  13. typedef struct stack stack;  
  14. typedef int Item;  
  15. struct stack  
  16. {  
  17.     Item *stackItem;  
  18.     int stackTop;  
  19. };  
  20.   
  21. void Error(const char* str) //异常时输出提示  
  22. {  
  23.     cout << "Error: " << str << endl;  
  24. }  
  25. int IsFull(stack* s) //判断是否栈满  
  26. {  
  27.     if (s->stackTop == FULL_STACK)  
  28.         return 1;  
  29.     else  
  30.         return 0;  
  31. }  
  32. int IsEmpty(stack* s) //判断是否空栈  
  33. {  
  34.     if (s->stackTop == EMPTY_STACK)  
  35.         return 1;  
  36.     else  
  37.         return 0;  
  38. }  
  39.   
  40. stack* StackInit( stack* s, int maxN) //初始化栈空间  
  41. {  
  42.      s->stackTop = -1; //空栈初始化 Top = -1  
  43.      s->stackItem = (Item*)malloc(maxN * sizeof(Item)); //分配栈空间  
  44.      return s;  
  45. }  
  46. void StackMakeEmpty(stack* s) //清空栈  
  47. {  
  48.     if (!IsEmpty(s))  
  49.         s->stackTop = EMPTY_STACK;  
  50. }  
  51.   
  52. void StackPush(stack* s, Item item) //入栈  
  53. {  
  54.     if (!IsFull(s))  
  55.     {  
  56.         s->stackItem[++(s->stackTop)] = item;  
  57.         cout << "PUSH: " << item <<endl;  
  58.     }  
  59.     else  
  60.         Error("栈已满,push失败");  
  61. }  
  62. Item StackPop(stack *s) //出栈  
  63. {  
  64.     if (!IsEmpty(s))  
  65.     {  
  66.         return s->stackItem[(s->stackTop)--];  
  67.     }  
  68.     else  
  69.         Error("空栈,pop失败");  
  70. }  
  71.   
  72. int main()  
  73. {  
  74.     stack *s = (stack*)malloc(sizeof(*s));  
  75.     StackInit(s, STACK_SIZE);  
  76.     for (int i = 0; i < 11; i++)  
  77.     {  
  78.         StackPush(s, i);  
  79.     }  
  80.     cout << "POP: " << StackPop(s) << endl;  
  81.     cout << "POP: " << StackPop(s) << endl;  
  82.     StackPush(s, 20);  
  83.     cout << "POP: " << StackPop(s) << endl;  
  84.     StackMakeEmpty(s);  
  85.     StackPop(s);  
  86.     StackPush(s, 30);  
  87.     cout << "POP: " << StackPop(s) << endl;  
  88.     system("pause");  
  89.     return 0;  
  90. }  
运行结果:



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

闽ICP备14008679号