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