栈、“X”
表示出栈的栈序列操作）。
【解答】
（1）可能得到的出站车厢序列是：123、
132、213、231、321。
2不能得到435612的出站序列。
因
为
有
S1S2S3S4X4X3S5X5S6S6，此时按照“后进先出”的原则，
出栈的顺序必须为X2X1。
能得到135426的出站序列。
12
f因
为
有
S1X1S2S3X3S4S5X5X4X2X1。
3给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？【解答】（1）顺序栈（top用来存放栈顶元素的下标）
判断栈S空：如果Stop1表示栈空。判断栈S满：如果
StopStack_Size1表示栈满。2链栈（top为栈顶指针，指向当前
栈顶元素前面的头结点）判断栈空：如果top
extNULL表
示栈空。判断栈满：当系统没有可用空间时，申
请不到空间存放要进栈的元素，此时栈满。
4照四则运算加、减、乘、除和幂运算的优先惯例，画出对下列表达式求值时操作数栈和运算符栈的变化过程：ABCDE↑F【解答】
13
f5写一个算法，判断依次读入的一个以为结束
符的字母序列，是否形如‘序列1序列2’的
字符序列。序列1和序列2中都不含‘’，且
序列2是序列1的逆序列。例如，’abba’
是属于该模式的字符序列，而’1331’则不是。
【解答】算法如下：
i
tIsHuiWe


StackS
Charchtemp
I
itStackSPri
tf“
请输入字符序列：”
Chgetchar
Whilech
序
列1入栈
PushSchchgetchar
14
fdo判断序列2是否是序列1的逆序列
chgetcharPopStempifchtemp序列2不是序列1的逆序列
retur
FALSEpri
tf“
NO”
whilechIsEmptyS
ifchIsEmptySretur
TRUEpri
tf“
YES”
序列2是序列1的逆序列elseretur
FALSEpri
tf“
NO”
IsHuiWe
8要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】入队算法：
i
tE
terQueueSeqQueueQQueueEleme
tTypex
将元素x入队ifQfro
tQfro
ttag1
队满retur
FALSE
15
fifQfro
tQfro
ttag0x入队前队空，x入队后重新设置标志
tag1QelememtQrearxQrearQrear1MAXSIZE设置队尾指针Retur
TRUE
出队算法：i
tDeleteQueueSeqQueueQQueueEleme
tTypex删除队头元素，用x返回其值ifQfro
tQreartag0队空
retur
FALSExQeleme
tQfro
tQfro
tQfro
t1MAXSIZE重新设置队头指针ifQfro
tQreartag0队头元素出队后队列为空，重新设置标志域Retur
r