数据结构题:设栈S的初始状态为空,若元素a、b、c、d、e、f依次进栈,得到的出栈序列是b、d、c、f、e、a则栈S的容量至少是________________请问这类题应该则么做的,算法是怎么样的.
来源:学生作业帮助网 编辑:作业帮 时间:2024/11/14 20:55:23
数据结构题:设栈S的初始状态为空,若元素a、b、c、d、e、f依次进栈,得到的出栈序列是b、d、c、f、e、a则栈S的容量至少是________________请问这类题应该则么做的,算法是怎么样的.
数据结构题:设栈S的初始状态为空,若元素a、b、c、d、e、f依次进栈,得到的出栈序列是b、d、c、f、e、a
则栈S的容量至少是________________
请问这类题应该则么做的,算法是怎么样的.
数据结构题:设栈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