数据结构题:设栈S的初始状态为空,若元素a、b、c、d、e、f依次进栈,得到的出栈序列是b、d、c、f、e、a

则栈S的容量至少是________________
请问这类题应该则么做的,算法是怎么样的。

1楼答的挺对的,栈S的容量是3,既然知道了栈名S,要用到C/C++最好能用栈S的函数push、pop

S.push (a)
S.push (b)
S.pop()
S.push (c)
S.push (d)
S.pop()
S.pop()
S.push (e)
S.psuh (f)
S.pop()
S.pop()
S.pop()

你说容量是怎么计算出来的,其实你应该知道栈是先进后出的吧,每次push也就是压入只能一个元素,每次pop也就是弹出也是一个元素。栈就像下面画的结构似的,其实容量就是这样的“格子”的数量。

     b是第一个出栈,那怎样才能让b第一个出栈,而且压入顺序又是a,b,c,d,e,f呢?首先把a压入栈中,然后在将b压入栈中,这时凳答弹出b,那b就是第一个出栈的啦,这时栈中还有元素a,然后分析第二个出栈的,第二个出栈是d,那还是得先压入c,然后再压入d(这时候栈里有几个元素呢?是a,c,d对吧)然后d出栈,这时栈中还有a,c,然后分析第三个出栈的是c,然后弹出c(即c出栈),然后分析第四个出栈的是f,和上面一样的分析啊,要想f第四个出芦团栈,先压入e,再压入f,(这时栈中有3个元枣哗慧素,a,e,f)然后弹出f,(栈中还有两个元素a,e),弹出e,弹出a。记住弹出只能弹出栈顶元素。什么时候压入,什么时候弹出都是自己决定的啊,但是根据上面的分析,要想入栈顺序和出栈顺序都正确,就必须这样操作啊,呵呵,所以栈S的容量,就是你在这样的分析的过程中栈S所含元素最多是多少啊?所以就是3


则栈S的容汪滑毕量至少是让培3。

操困芹作依次为:
push a
push b
pop
push c
push d
pop
pop
push e
psuh f
pop
pop
pop