栈的存储结构的实现(C/C++实现)详解编程语言

 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 }