順序棧的基本操作

通過(guò)菜單調(diào)用各個(gè)操作，測(cè)試點(diǎn)：

?沒(méi)有初始化前進(jìn)行其他操作，程序是否能控制?。?/p>

?初始化一個(gè)棧；

?判?？眨聊伙@示棧為空；

?3個(gè)數(shù)大棧，1、2、3;

?棧長(zhǎng)度，屏幕輸出3;

?取棧頂元素，再判棧至，然后再判棧長(zhǎng)度。讓學(xué)生知道取棧頂元素不改變棧中的內(nèi)容，棧頂指針不發(fā)生改變,

?出棧，再判棧長(zhǎng)度；

?銷毀棕，再做其他操作，判斷程序是否能控制；

?數(shù)制轉(zhuǎn)換，輸大：8,輸出：1000

問(wèn)題分析：

棧是將插入和刪除集中在一端進(jìn)行的線性結(jié)構(gòu)，表尾端稱為棧頂，表頭端稱為錢底,不含元素的棧稱為空棧.

順序棧是指利用JI質(zhì)序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧，利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素,用指針top指向棧頂元素所在位置

的下一位。

順序棧有以下基本操作：初始化棧、銷毀棧、將棧置空、入棧、出棧、判斷棧是否為空、刪除棧頂元素、求棧的長(zhǎng)度、輸出棧內(nèi)元素、創(chuàng)建

并初始化棧.

算法思想：

棧底指針base始終指向棧底的位置，當(dāng)base的值為NULL時(shí)，百世棧不存在；top為棧頂指針，其初值指向棧底，每當(dāng)元素入棧時(shí)，top指

針加1,刪馀棧頂元素時(shí)，top指針減1;當(dāng)棧為空時(shí)，top和base的值相等，都指向棧底；棧非空時(shí)，top始終指向棧頂元素的上一個(gè)位

置。

數(shù)制轉(zhuǎn)換的算法思想：

將十進(jìn)制裁轉(zhuǎn)換為n進(jìn)制數(shù)，可每次將數(shù)除n的余數(shù)人棧，然后數(shù)除以n,直到該數(shù)變?yōu)?,再講棧內(nèi)元素輸出，即可得至降專換為n進(jìn)制后的

數(shù)。

源代碼

1include<iostream>

2include<cmath>

4usrgnamespacestd;

*^defineMAXSIZE100

typedefintSEIemType;

7typedefstruct{

SEIemType'base;

SEIemType*top;

1ntstacksize;

1}SqStack;

12

13〃初始化棧

1：intlnitStack(SqStack&S)

15(

S.basenewSEIemTypefMAXSIZE];

17S.top-S.base;

1S.stacksize=MAXSIZE;

19*eturn1;

20}

〃判斷我XE臺(tái)內(nèi)工

一一boolStackEmptyfSqStackS)

23{

f(Shasp)returntniA：

25elsereturnfalse;

26}

27〃求順序棧的長(zhǎng)度

26intStackLengthfSqStackS)

29{

-eturnS.top-S.base;

31}

32〃清空順序棧

33intClearStack(SqStack&S)

34{

f(S.base)S.top=S.base;

36*eturn1;

37}

38〃銷毀順序棧

_intDestroyStack(SqStack&S)

40{

41f(S.base)

42{

43deleters.base:

44S.stacksize=O;

45S.base--S.top-NULL;

46)

47,otum1;

48)

49〃入棧

r}intPush(SqStack&S.SEIemTypee)

51{

f(S.top-S.baseS.stacksize)

53return0;

*S.top++=e;

55^turn1;

56}

57〃出棧

intPopfSqStack&S,SEIemType&e)

59{

6f(S.top==S.base)

61return0;

62e=*-S.top;

63-eturn1;

64}

65〃取棧頂元素

(intGetTop(SqStackS.SEIemType&e)

67{

f(S.top==S.base)return0;

69e?*(S.top-1);

70eturn1;

71}

72〃輸出棧內(nèi)元素

7jvoidprint(SqStackS)

74{

while(S.top'=S.base)

76{

77cout?*(S.top1);

78S.top;

79)

80}

81”創(chuàng)建并輸入棧元素

8.voidBulidStack(SqStack&S:intn)

83{

84while(n-)

85{

S.top11;

88)

89)

90〃輸出提示信息

91voidwelcome()

92(

93cout?.........................?endl;

94初始化為空棧"vvendl;

95coutvv"2.銷毀棧"<<endl;

96cout?"3.將棧置空"?endl;

97coukv"4.判斷棧是否為空棧"wendl;

98cout?"5.返回棧的長(zhǎng)度"?endl;

〈.求棧頂元素〈

QQcoutv"6~vendl;

.插入元素,并使其成為棧頂元素

100coutvv"7"wendl;

.刪除棧頂元素力返回其值

101coutv78"vvendl;

8utw"9.輸出棧內(nèi)元素"wendl；

102

。。01<<"10.創(chuàng)建并輸入棧元素"〈〈日前1;

1*w0w3

coutvv"l1.退HNendl;

104

〈.運(yùn)行數(shù)字轉(zhuǎn)換程序；

105coutv"l2"vvendl

coutvvwendl;

106

}

107

boollsLegal(SqStackS)

108

(

109

f(abs(S.topS.base)>MAXSIZE)

110

returnfalse;

111

112elseif(!S.base)

returnfalse;

113

else

114

returntrue;

115

118}

intmain()

117

(

118

SqStackS;

119

SEIemTypee;

120

ntn.mes;

121

//cout?*S.top?""^S.base;

122

〃return0;

123

welcoine(),

124

COUtvv"請(qǐng)輸入你的選擇>>“；

125

while(cin?n)

126

1J

127

switch(n)

128

{

129

case1:

130

mes=lnilStack(S);

131

if(mes)

132

coukv”初始化成功！"wendl;

133

break;

134

case2:

135

if(!lsLegal(S)){

130

coukv“棧未初始化！"?endl;

137

break;

138

}

139mesDestroyStack(S);

140if(mes)

141

coutvv”銷毀成功！"?endl;

142break;

143case3:

144

if(!lsLegal(S)){

145coukv"棧未初始化！"?endl;

146break;

147)

148mes-ClearStack(S);

149if(mes)

150coutvv"棧己置空！"wendl;

152break;

153case4:

154if(!lsLegal(S)){

155coutvv"棧未初始化！"wendl;

156break;

157}

158if(StackEmpty(S))

159coutvv"棧為空！"v<endl;

160else

161cout<<"非空!"?endl;

162break;

163case5:

164if(!lsLegal(S)){

165coutvv"棧未初始化！"wendl：

166break;

167)

168mes=StackLength(S);

coutvv"棧的長(zhǎng)度為："vvmes<<end;

169

break;

170

case6:

171

if(!lsLegal(S)){

172

coutvv”棧未初始化！"<<endl;

173

break;

174

)

175

mesGetTop(S.e);

176

if(mes)

177

coukv"棧頂元素為："?e?endI;

178

else

179

cout<<”償作失收！"?endl;

180break;

181

case7:

182if(!lsLegal(S)){

183coukv-棧未初始化！"?endl;

184break;

185)

186COUtvv"請(qǐng)輸入一個(gè)元素：-；

187cin?e;

188mesPush(S.e):

189if(mes)

190coutvv”入棧成功！-?endl;

191else

192coukv”操作失敗!"?endl;

193break;

194case8:

195if(!lsLegal(S)){

196coul<<“棧未初始化！"《endl;

197break;

198)

199mesPop(S,e);

200if(uies)

201coukv"棧頂元素為："?e?endI;

202else

203coukv”按作失??！"wendl;

204break;

205case9:

206if(!lsLegal(S)){

207coutvv"棧未初始化！"wendl;

208break;

209}

210print(S);

211cout?endl;

212break;

213case10:

2148Ukv”請(qǐng)輸入要初始化的元素個(gè)數(shù)：

215cin?mes;

2178utvv"請(qǐng)輸入"wmesvv"個(gè)元素:"?endl：

218BulidStack(S,mes);

219break;

220case11:

221return0;

222break;

223case12:

224couk-'渝入要轉(zhuǎn)換的數(shù)字：";

225cin?e;

226InitStack(S);

227while(e)

228(

229Push(S.e%2);

230e=2;

231}

232print(S);

233cout?endl;

234brea