栈的抽象数据类型-数据结构

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define STACK_INIT_SIZE 100
  4 #define STACKINCREMENT 10
  5 
  6 typedef struct{
  7     int *base;
  8     int *top;
  9     int stacksize;
 10 }Sqstack;
 11 
 12 bool InitStack(Sqstack &s)
 13 {
 14     s.base = (int *)malloc(100*sizeof(int));
 15     if(s.base == NULL) return 0;
 16     s.top = s.base;
 17     s.stacksize = 100;
 18     return 1;
 19 } 
 20 
 21 bool Push(Sqstack &s,int e)
 22 {
 23     if(s.top - s.base >= s.stacksize)//满栈 
 24     {
 25         s.base = (int *)realloc(s.base,(s.stacksize + STACKINCREMENT)*sizeof(int));
 26         if(!s.base) exit(-1);
 27         s.top = s.base + s.stacksize;//必须重新设置栈顶，因为栈内存重新分配了，栈底也变了 
 28         s.stacksize += STACKINCREMENT;
 29     }
 30     *s.top++ = e;
 31     return 1;
 32 }
 33 
 34 bool Pop(Sqstack &s,int &e)
 35 {
 36    if(s.base == s.top) return 0;
 37    e = * --s.top;
 38    return 1;
 39 } 
 40 
 41 bool GetTop(Sqstack s,int &e)
 42 {
 43     if(s.base == s.top) return 0;
 44     e = *(s.top - 1);
 45     return 1;
 46 }
 47 
 48 bool StackEmpty(Sqstack s)
 49 {
 50     if(s.base == s.top) return 1;
 51     else return 0;
 52 }
 53 
 54 int StackLength(Sqstack s)
 55 {
 56     return (s.top - s.base);
 57 }
 58 
 59 void TraverStack(Sqstack &s)
 60 {
 61     int len = StackLength(s);
 62     for(int i = 0;i < len;i++)
 63     {
 64         cout << *(s.base + i) << " ";
 65     }
 66     cout << endl;
 67 }
 68 bool ClearStack(Sqstack &s)
 69 {
 70     int len = StackLength(s);
 71     for(int i = len;i > 0;i--)//保留了头结点 
 72     {
 73         free(s.base + i);
 74     }
 75     //并让尾指针等于首指针 
 76     s.top = s.base; 
 77     return 1;
 78 }
 79 
 80 bool DestroyStack(Sqstack &s)
 81 {
 82     int len = StackLength(s);
 83     for(int i = len;i >= 0;i--)
 84     {
 85         free(s.base + i);
 86     }
 87     return 1;
 88 }
 89 
 90 int main()
 91 {
 92     Sqstack s;
 93     InitStack(s);
 94     int a,b;
 95     for(int i = 1;i <= 5;i++)
 96     {
 97         Push(s,i);
 98     }
 99     TraverStack(s);
100     Push(s,6);
101     TraverStack(s);
102     
103     bool ok = GetTop(s,a);
104     if(ok)
105     {
106         cout << "e = " << a << endl;
107     }
108     ok = Pop(s,a);
109     if(ok)
110     {
111         cout << "e = " << a << endl;
112     }
113     TraverStack(s);
114     
115     DestroyStack(s);
116     TraverStack(s);
117     return 0;
118 }