[习题4-1]运算题。 1．有6 个元素A、B、C、D、E、F 依次进栈，允许任何时候出栈，能否得到下列的每个出栈序列，若能，给出栈操作的过程，若不能，简述其理由。 （1）CDBEFA （2）ABEDFC （3）DCEABF （4）BAEFCD 2．有4 个元素a,b,c,d 依次进栈，任何时候都可以出栈，请写出所有可能的出栈序列和所有不存在的序列。 3．用一维数组a[7]顺序储一个循环队列，队首和队尾指针分别用front 和rear 表示，当前队列中已有5 个元素：23，45，67，80，34，其中，23 为队首元素，front 的值为3，请画出对应的存储状态，当连续做4 次出队运算后，再让15，36，48 元素依次进队，请再次画出对应的存储状态。 4．用于顺序存储一个队列的数组的长度为N,队首和队尾指针分别为front 和rear,写出求此队列长度(即所含元素个数)的公式. 参考答案（从简） 1，(1)能: pu sh(S,A), pu sh(S,B), pu sh(S,C), pop(S), pu sh(S,D), pop(S), pop(S), pu sh(S,E), pop(S), pu sh(S,F), pop(S), pop(S). (2)能:pu sh(S,A), pop(S), pu sh(S,B), pop(S), pu sh(S,C), pu sh(S,D), pu sh(S,E), pop(S), pop(S), pu sh(S,F), pop(S), pop(S). (3)不能: 当E 出栈时，AB 必需在栈内，而后继A 出栈先于B，不符合后进先出原则。 (4)不能: 当F 出栈时，CD 必需在栈内，而后继C 出栈先于D，不符合后进先出原则。 2，所有可能的出栈序列: abcd; abdc; acbd; acdb; adcb; bacd; badc; bcad; bcda; bdca; cbad; cbda; cdba; dcba. 所有不存在的序列: adbc; bdac; cabd; cadb; cdab; dabc; dacb; dbac; dbca; dcab. 3， 0 1 2 3 4 5 6 ------------------------------------------------------------------ [80 34 23 45 67] ↑rear ↑front [ 34 15 36 48 ] ↑front ↑rear 4，队列长度L 的计算公式为： L = ( N+rear-front ) % N [ 说明： 当rear>front 时，L = rear - front = ( N+rear-front ) % N; 当rear
