存档
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 }
运行结果如下：
