王道数据结构栈实现

深碍√TFBOYSˉ_ 2022-10-03 00:43 226阅读 0赞 
  1. #include<cstdio>
  2. #define MaxSize 50
  3. typedef int ElemType;
  5. typedef struct { 
  6.     ElemType data[MaxSize];           //栈中存放元素
  7.     int top;                          //栈顶指针,初始赋为-1
  8. }SqStack;                              //
  10. /*栈初始化*/
  11. void InitStack(SqStack& S) { 
  12.     S.top = -1;             //初始化栈顶指针-1
  13. }
  15. /*判栈空*/
  16. bool StackEmpty(SqStack S) { 
  17.     return S.top == -1;
  18. }
  20. /*元素入栈*/
  21. bool Push(SqStack& S, ElemType x) { 
  22.     if (S.top == MaxSize - 1) {           //栈满，报错
  23.         return false;
  24.     }
  25.     S.data[++S.top] = x;                //指针先加1，再赋值
  26.     return true;
  27. }
  29. /*弹栈*/
  30. bool Pop(SqStack& S, ElemType& e) { 
  31.     if (StackEmpty(S)) {         //栈空，报错
  32.         return false;
  33.     }
  34.     e = S.data[S.top--];        //先出栈，指针再减一
  35.     return true;
  36. }
  38. /*读取栈顶元素*/
  39. bool GetTop(SqStack S, ElemType& e) { 
  40.     if (S.top == -1) {           //栈空，报错
  41.         return false;
  42.     }
  43.     e = S.data[S.top];          //获取栈顶元素
  44.     return true;
  45. }
  47. /*清空栈*/
  48. bool ClearStack(SqStack& S) { 
  49.     S.top = -1;
  50.     return true;
  51. }
  53. int main() { 
  54.     SqStack s;
  55.     ElemType e;
  56.     InitStack(s);
  58.     for (int i = 1; i < 10; i++) 
  59.         Push(s, i);
  61.     while (!StackEmpty(s)) { 
  62.         Pop(s, e);
  63.         printf("%d ", e);
  64.     }
  65.     return 0;
  66. }

上述代码为顺序栈的实现，比较简单。其中栈顶指针设为-1，也可以设置为0，两者在判空和入栈、弹栈操作时有细微变换，具体的代码也要根据具体的赋值而定。

此外，栈还有另一种结构，即链式存储结构。链栈的优点便于多个栈共享存储空间和提高其效率，且不存在顺序栈中存在的问题（栈上溢）。链栈采用单链表实现，并且所有的操作都是在单链表的表头操作完成。
其链式存储结构可描述为如下：

  1. typedef struct LinkNode{ 
  2.     ElemType data;         //数据域
  3.     struct LinkNode* next; //指针域
  4. }*LiStack;

发表评论

表情：
评论列表 （有 0 条评论，226人围观）

还没有评论，来说两句吧...

相关阅读

    相关 栈-Java实现栈数据结构

    1、栈的基本概念 栈（英语：stack）又称为堆栈或堆叠，栈作为一种数据结构，是一种只能在一端进行插入和删除 操作的特殊线性表。它按照先进后出的原则存储数据，先进入的

    红太狼红太狼/ 0 赞/ 90 阅读

    相关 （数据结构）栈讲解和栈实现

    栈的概念 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Las

    清疚清疚/ 0 赞/ 85 阅读