顺序栈的基本操作及应用_采用顺序存储实现栈的初始化、销毁栈、求栈的长度、取栈顶元素、栈空、出栈、入栈

实验4、顺序栈的基本操作及应用
（1）实验目的
通过该实验，让学生掌握栈的相关基本概念，认识栈是插入和删除集中在一端进行的线性结构，掌握栈的“先入后出”操作特点。栈在进行各类操作时，栈底指针固定不动，掌握栈空、栈满的判断条件。
（2）实验内容
用顺序存储结构，实现教材定义的栈的基本操作，提供数制转换功能，将输入的十进制整数转换成二进制、八进制或十六进制。
（3）参考界面
菜单中包括以下功能：
1.初始化栈，2.销毁栈，3.清空栈，4.栈判空，5.求栈长度，6.获取栈顶元素，7.插入一个 元素，8.删除一个元素，9输出所有元素，10进制转换。
要求：自定义的函数中不允许出现提示语和输出语句。
（4）验收/测试用例
通过菜单调用各个操作，测试点：
没有初始化前进行其他操作，程序是否能控制住；
初始化一个栈；
判栈空，屏幕显示栈为空；
3个数入栈， 2、4、6；
栈长度，屏幕输出3；
取栈顶元素，再判栈空，然后再判栈长度。让学生知道取栈顶元素不改变栈中的内容，栈顶指针不发生改变；
出栈，再判栈长度和输出栈中内容；（多次出栈，直到栈为空；再出栈，是否提示栈为空）
销毁栈，再做其他操作，判断程序是否能控制；
数制转换，（允许用户输入想把十进制转换成几进制），然后灵活的转换成对应的进制。

#include<stdio.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

typedef int Status;

#define ok 0
#define error 1
#define shortcoming -1
#define question -2


#define Stack_Init_Size 100
#define StackIncreament 10


typedef int SElemType;

typedef struct SqStack {
	SElemType *top;
	SElemType *base;
	int stacksize;                 
}SqStack;

Status InitStack(SqStack &S);            //初始化栈 
Status DestroyStack(SqStack &S);               //销毁栈 
Status ClearStack(SqStack &S);               //清空栈 
Status GetEmpty(SqStack S);                  //判断栈是否为空 
Status GetLength(SqStack S);                //获取栈的长度 
Status GetTopElem(SqStack S,SElemType &e);             //获取栈顶元素 
Status InsertElem(SqStack &S, int &e);             //向栈中插入元素 
Status DeleteElem(SqStack &S);                 //删除栈中元素 
Status ShowElem(SqStack S);                //显示栈中所有元素 
Status BaseConversion(SqStack &S,int &i,int &j);                 //进制转换 

int menu() {
	cout<<"1，初始化一个栈"<<endl;
	cout<<"2，销毁栈"<<endl;
	cout<<"3，清空栈"<<endl;
	cout<<"4，栈判空"<<endl;
	cout<<"5，求栈的长度"<<endl;
	cout<<"6，获取栈顶元素"<<endl;
	cout<<"7，插入一个元素"<<endl;
	cout<<"8，删除一个元素"<<endl;
	cout<<"9，输出所有元素"<<endl; 
	cout<<"10，进制转换"<<endl;
	cout<<"输入一个负数，退出！"<<endl;
}

int main() {
	SqStack S;
	S.base = NULL;
//	S.top = NULL; 
	menu();
	int i;
	while (true) {
		cout<<"请选择程序:"; 
		cin>>i;
		if (i < 0) {
			cout<<"程序已退出！"<<endl;
			break;
		} else {
			if (i == 0 || i > 10) {
				cout<<"程序选择错误，请重新选择！"<<endl;
			} else {
				switch(i) {
					case 1:{
						if (InitStack(S) == ok) {
							cout<<"栈初始化成功！"<<endl;
						} else {
							cout<<"栈初始化失败！"<<endl;
						}
						break;
					}
					case 2:{
						if (S.base) {
							if (DestroyStack(S) == ok) {
								cout<<"栈已被销毁！"<<endl;
							} else {
								cout<<"栈销毁失败！"<<endl;
							}
						} else {
							cout<<"栈不存在！"<<endl;
						}
						break;
					}
					case 3:{
						if (S.base) {
							if (ClearStack(S) == ok) {
								cout<<"栈已清空！"<<endl;
							} else {
								cout<<"栈清空失败！"<<endl;
							}
						} else {
							cout<<"栈不存在！"<<endl;
						}
						break;
					}
					case 4:{
						if (S.base) {
							if (GetEmpty(S) == ok) {
								cout<<"栈为空！"<<endl;
							} else {
								cout<<"栈不为空！"<<endl;
							}
						} else {
							cout<<"栈不存在！"<<endl;
						}
						break;
					}
					case 5:{
						if (S.base) {
							cout<<"栈的长度为："<<GetLength(S)<<endl;
						} else {
							cout<<"栈不存在！"<<endl;
						}
						break;
					}
					case 6:{
						if (S.base) {
							if (GetLength(S) == 0) {
								cout<<"栈为空！无栈顶元素"<<endl;
							} else {
								SElemType e;
								if (GetTopElem(S,e) == ok) {
								cout<<"其栈顶元素为："<<e<<endl; 
							} else {
								cout<<"查询失败！"<<endl;
							}
							}
						} else {
							cout<<"栈不存在！"<<endl;
						}
						break;
					}
					case 7:{
						if (S.base) {
							int e;
							cout<<"请输入要插入的元素:";
							cin>>e;
							if (InsertElem(S,e) == ok) {
								cout<<"插入成功！"<<endl;
							} else {
								cout<<"插入失败！"<<endl;
							}
						} else {
							cout<<"栈不存在！"<<endl;
						}
						break;
					}
					case 8:{
						if (S.base) {
							if (S.base == S.top) {
								cout<<"栈已空，无法删除元素！"<<endl;
							} else {
								if (DeleteElem(S) == ok) {
									cout<<"元素删除成功！"<<endl; 
								} else {
									cout<<"元素删除失败！"<<endl;
								}
							}
						} else {
							cout<<"栈不存在！"<<endl;
						}
						break;
					}
					case 9:{
						if (S.base) {
							if (ShowElem(S) == ok) {
								cout<<"栈输出完毕"<<endl; 
							} else {
								cout<<"栈输出失败！"<<endl;
							}
						} else {
							cout<<"栈不存在！"<<endl;
						}
						break;
					}
					case 10:{
						int i;
						cout<<"请输入一个十进制数：";
						cin>>i;
						int j;
						cout<<"请问你想将其转化为几进制数？ ：";
						cin>>j;
						if (BaseConversion(S,i,j) == ok) {
							cout<<"其对应"<<j<<"进制数为：";
							cout<<ShowElem(S)<<endl;
						} else {
							cout<<"转换失败！"<<endl;
						}
						break;
					}
				}
			}
		}
	} 
}

Status InitStack(SqStack &S) {         //1,初始化栈 
	S.base = (SElemType*)malloc(Stack_Init_Size*sizeof(SElemType));
	if (S.base) {
		S.top = S.base;
		S.stacksize = Stack_Init_Size;
		return ok;
	} else {
		return error;
	}
}

Status DestroyStack(SqStack &S) {           //2,销毁栈 
	S.base = NULL;
	S.stacksize = 0;
	return ok;
}

Status ClearStack(SqStack &S) {            //3,清空栈 
	S.top = S.base;
	return ok;
}

Status GetEmpty(SqStack S) {              //4，判断栈是否为空 
	if (S.base == S.top) {
		return ok; 
	} else {
		return question;
	}
}
Status GetLength(SqStack S) {        //5,获取栈的长度 
		int i;
		i = S.top - S.base;
		return i;
}

Status GetTopElem(SqStack S,SElemType &e) {    //6，获取栈顶元素 
	e = *(S.top - 1);
	return ok;
}

Status InsertElem(SqStack &S, int &e) {         //7,向栈中插入元素 
	if (GetLength(S) == S.stacksize) {
		SElemType *Newbase = (SElemType*)realloc(S.base,(S.stacksize + StackIncreament)*sizeof(SElemType));
			if (Newbase) {
				S.top = Newbase + S.stacksize;
				S.stacksize+=StackIncreament;
			} else {
				return shortcoming;
			} 
	}
		*S.top++ = e;
		return ok;
}
 
Status DeleteElem(SqStack &S) {          //8,删除一个栈中元素 
	*S.top--;
	return ok;
}
 
Status ShowElem(SqStack S) {                //9，展示栈中所有元素 
	SElemType *p = S.top;
	while (p!=S.base) {
		p--;
		cout<<*p<<" ";
	}
 	return ok;
}
 
Status BaseConversion(SqStack &S,int &i,int &j) {            //10,进制转换 
	int m = i,e;
	if (InitStack(S) == ok) {
	while (m >= j) {
		e = m%j;
		if (InsertElem(S,e) == ok) {
			m = (m - e) / j;
		} else {
			return shortcoming;
		}
	}
} else {
	return question;
}
	e = m;
	if (InsertElem(S,e) == ok) {
		return ok;
	} else {
		return shortcoming;
	}
}

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317