1.2

Exercises

1、Add a method isFull() to FixedCapacityStackOfStrings.java.

     A：boolean isFull() { return N == a.length;}

2、Give the output printed by java Stack for the input

     it was - the best - of times - - - it was - the - -

    A：（考查 Stack的 LIFO机制）

        - 表示出队，一个横杠表示出栈一个元素，n个横杠表示出栈n个元素。

        因此，it was - 表明，it 和 was 入栈之后，遇到横杠，栈顶元素出栈：打印 was

        the best - 同理：打印 best，此时栈中还剩下 it the

        of time - - - 表明of time 入栈，遇到三个横杠，把栈顶的三个元素出栈：打印：time of the

        以此类推，打印结果为：was best times of the was the it，打印完栈中还有 it 这个元素。

3、Suppose that an intermixed(混合) sequence of (stack) push and pop operations are performed. The pushes push the integers 0 through 9 in order; the pops print out the return value. Which of the following sequence(s) could not occur?

(a)  4 3 2 1 0 9 8 7 6 5

(b)  4 6 8 7 5 3 2 9 0 1

(c)  2 5 6 7 4 8 9 3 1 0

(d)  4 3 2 1 0 5 6 7 8 9

(e)  1 2 3 4 5 6 9 8 7 0

(f)  0 4 6 5 3 8 1 7 2 9

(g)  1 4 7 9 8 6 5 3 0 2

(h)  2 1 4 3 6 5 8 7 9 0

A：（考查 Stack的LIFO机制）理解题目的关键是0~9输入的先后连续性。

(a)  4 3 2 1 0 9 8 7 6 5 

分析：4 3 2 1 0 表明 push 顺序为：0 1 2 3 4，然后都 pop 出来就成了 4 3 2 1 0；

9 8 7 6 5 同理，这里是 pop 完01234之后再入栈56789.

(b) 4 6 8 7 5 3 2 9 0 1

分析：先出4，此时栈中由上到下分别为 3 2 1 0；出 6 表明4出了之后插入 5 6之后6马上出栈，栈中为 5 3 2 1 0；87532出栈表明，出6之后插入78，接着出87532；再出9表明9入栈之后马上出栈，此时栈中剩下1 0，这是如果将其出栈，顺序为 1 0，而题目是0 1，违反了LIFO机制，b 不符合。

其余同理，自个儿分析去。答案为：b f g