Question

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

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

Answer 1

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

Answer 2

则栈S的容量至少是3。

操作依次为：
push a
push b
pop
push c
push d
pop
pop
push e
psuh f
pop
pop
pop

追问

这个操作怎么算出来的，我怎么知道什么时候该压栈，什么时候该出栈。

追答

题目说：得到的出栈序列是 b、d、c、f、e、a。
第一个出栈的是 b，所以，push b 后就应该 pop；
然后出栈的是 d、c， 所以，push c、push d 后就应该 pop、pop；
依此类推。