【栈】设栈的顺序存储空间为S(1,m),初始状态为top=m+1,则栈中元素个数为mtop+1个。

设栈的顺序存储空间为S(1,m),初始状态为top=m+1,则栈中元素个数为m-top+1个。

这道题容易被top=m+1给搞懵了,因为在咱们正常的思维中,这个栈应该是这样的:

那么top=m+1不是直接满栈溢出了吗?

所以这个栈肯定不是这样的,那还有种可能,就是这样:

咱们把m带入一个数,比如说4,那么栈底指针现在就在4号房,栈顶指针在5号房,如果一个人要入住,那么栈顶指针+1,它也变成4号房了,那么 入住人员个数=m-top+1=4-4+1=1。

再往里入住一个人,top指针到了3号房,栈底指针还在4号房没变,那么 入住人数=m-top+1=4-3+1=2.

这个栈顶指针可以一直减少,一直减少到1,这个栈就满了。

有的人可能有疑惑,这个栈顶指针还能移到栈底更底的地方?其实这就是定义一个空栈的写法,为啥栈顶=栈底不是一个空栈呢?

这就涉及到栈顶指针的定义了,栈顶指针一定是指向一个元素的,也就是说只要它出现在栈里,那么这个栈一定是有一个客户在入住的,所以想表明空栈的时候,栈顶指针就指向栈底更底的一个位置了。

原文地址:https://www.cnblogs.com/pandaNHF/p/15580539.html