栈和队列（选择题）

栈中元素个数的计算 

栈的存储结构可以分为顺序存储和链式存储。顺序存储的栈称为顺序栈，链式存储的栈称为链栈。

（1）顺序栈

顺序栈：利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时

附设一个指针（top）指示当前栈顶位置。

栈空条件：顺序栈的数组下标如果从0开始，栈空的条件是top=-1。

栈满条件：顺序栈的数组下标如果从0开始，栈满的条件是top=maxsize（栈的最大容量）-1。

 

顺序栈的计算方法：如果bottom>=1，栈内的元素个数为|top-bottom|+1，如果bottom=top=0时，则表示栈空。(top表示栈顶指针,bottom表示栈底指针）

上溢：若顺序栈满栈时，再进行入栈操作，就会产生上溢。

下溢：若顺序栈栈空时，再进行出栈操作，就会产生下溢。

这道题的栈不同于一般的站我们一定要确定好栈底指针是啥。在利用公式求解。|20-50|+1=51。 

|1-30|+1=30 

设栈的顺序存储空间为S(1:m)，初始状态为top=0.现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为（不可能）

设栈的顺序存储空间为S(1:m)，初始状态为top=m+1.现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为（不可能）

（2）链栈

链栈：采用链式存储的栈称为链栈。

某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为（不确定）

链栈的优点是便于多个栈共享存储空间和提高其效率，并且链栈不存在栈满上溢的情况。

循环对列元素个数的计算

（队尾-队首+容量）%容量或(rear-front+maxsize)%maxsize

n=(25-25+50)%50=0 

n=(25-25+50)%50+2=2,一定要看清楚有插入了两个元素。  

本质还是没有变，要求最坏次数就是求还有多少元素。