栈的存储结构的实现(C/C++实现)

             1 #include "iostream.h" 2 #include <stdlib.h>
 3#define max 20
 4 typedef char elemtype;
 5 #include "stack.h" 6void main()
 7{
 8    stack s;
 9char x;
10     cout<<"(1)初始化栈s\n";
11    initstack(s);
12     cout<<"(2)栈为"<<(stackempty(s)?"空":"非空")<<endl;
13     cout<<"(3)依次输入字母序列,以‘#‘结束"<<endl;
14     cin>>x;
15while(x!=‘#‘)
16    {
17        push(s,x);
18         cin>>x;
19    }
20     cout<<"(4)栈为"<<(stackempty(s)?"空":"非空")<<endl;
21     cout<<"(5)栈长度stacklength(s):"<<stacklength(s)<<endl;
22     cout<<"(6a)栈顶元素gettop(s)为:"<<gettop(s)<<endl;
23     cout<<"(6b)栈顶元素gettop1(s,x)为:";
24    gettop1(s,x);
25     cout<<x<<endl;
26     cout<<"(7)从栈顶到栈底元素printstack(s):";
27    printstack(s);
28     cout<<"(8)出栈pop1(s,x)的元素为:";
29    pop1(s,x);
30     cout<<x<<endl;
31     cout<<"(9)出栈序列:";
32while(!stackempty(s))
33    {
34         cout<<pop(s)<<"";
35    }
36     cout<<endl;
37     cout<<"(10)栈为"<<(stackempty(s)?"空":"非空")<<endl;
38     cout<<"(11)依次进栈元素a,b,c\n";
39     push(s,‘a‘);
40     push(s,‘b‘);
41     push(s,‘c‘);
42     cout<<"(12)从栈顶到栈底元素printstack(s):";
43    printstack(s);
44     cout<<"(13)清空栈clearstack(s)\n";
45    clearstack(s);
46     cout<<"(14)栈为"<<(stackempty(s)?"空":"非空")<<endl;
47     cout<<"(15)销毁栈"<<endl;
48    destorystack(s);
49     cout<<"(17)销毁栈后调用push(s,e)和printstack(s)"<<endl;
50     push(s,‘e‘);
51    printstack(s);
52 }

              1
            struct
             stack

              2
            {

              3     elemtype *base;//存栈元素  4     elemtype *top;//栈顶指定器  5int stacksize;//栈的最大容量  6};
  7void initstack(stack &s)
  8{
  9//构造一个空栈s 10     s.base=new elemtype[max];//malloc()分配存储空间 11if(!s.base)
 12         exit(-2);//#define OVERFLOW -2  13     s.top=s.base;//空栈 14     s.stacksize=max;//栈的存储容量 15}
 16void clearstack(stack &s)
 17{
 18//清除栈s,使成为空栈 19     s.top=s.base;//空栈栈顶指针和栈底指针相等 20}
 21int stackempty(stack s)
 22{
 23//若栈s为空栈返回1,否则返回0 24if(s.top==s.base)
 25return1;//空栈返回1,非空返回0 26else 27return0;
 28}
 29int stacklength(stack s)
 30{
 31//返回栈的长度 32return s.top-s.base;
 33}
 34void push(stack &s,elemtype e)
 35{
 36//元素e进栈 37if(!s.base)//栈不存在的处理 38    {
 39         cout<<"栈不存在\n";
 40return;
 41    }
 42if(s.top-s.base>s.stacksize)//栈满的处理 43    {
 44         cout<<"栈已满!\n";
 45return;
 46    }
 47     *s.top=e;//元素e存进栈顶的位置 48     s.top++;//栈顶指针指向栈顶元素的下一个位置 49}
 50 elemtype pop(stack &s)
 51{
 52//栈s的栈顶元素出栈并返回 53if(s.base==s.top)
 54    {
 55         cout<<"栈空,不能出栈\n";
 56         exit(-2);
 57    }
 58else 59    {
 60         s.top--;//栈顶指针减1,下次进栈，会覆盖当前位置的值,相当于删除 61return *s.top;//返回栈顶元素的值 62    }
 63}
 64int pop1(stack &s,elemtype &e)
 65{
 66//栈s的栈顶元素出栈并返回 67if(s.base==s.top)
 68    {
 69         cout<<"栈空,不能出栈\n";
 70return0;
 71    }
 72else 73    {
 74         s.top--;//栈顶指针减1,下次进栈，会覆盖当前位置的值,相当于删除 75         e=*s.top;
 76return1;//返回栈顶元素的值 77    }
 78}
 79elemtype gettop(stack s)
 80{
 81//取栈s的当前栈顶元素并返回 82if(s.top==s.base)
 83    {
 84         cout<<"栈空,获取栈顶元素失败"<<endl;
 85         exit(-2);
 86    }
 87else 88return *(s.top-1);//top指针-1的位置才是栈顶元素所在的位置 89}
 90int gettop1(stack s,elemtype &e)
 91{
 92//取栈s的当前栈顶元素并返回 93if(s.top==s.base)
 94    {
 95         cout<<"栈空,获取栈顶元素失败"<<endl;
 96return0;
 97    }
 98else 99         e=*(s.top-1);
100return1;//top指针-1的位置才是栈顶元素所在的位置101}
102void printstack(stack s)
103{
104//输出栈中所有元素,但不出栈,不做任何修改105int i;
106for(i=s.top-s.base-1;i>=0;i--)//总共s.top-s.base个元素,下标范围就是[0...(s.top-s.base-1)]107         cout<<s.base[i]<<"";
108     cout<<endl;
109}
110void destorystack(stack &s)
111{
112//销毁栈113delete s.base;//销毁连续空间114     s.base=NULL;//指针赋空115     s.top=NULL;//指针赋空116     s.stacksize=0;//栈容量赋0117 }