Question

A single array A[1...MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (top1 < top2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for "stack full" is

• A. top1 + top2 = MAXSIZE
• B. (top1 = MAXSIZE/2) or (top2 = MAXSIZE)
• C. (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
• D. top1 = top2 - 1

Answer 1

The correct option is D top1 = top2 - 1

• When stack 1 contain 1 element and stack 2 contain 1 element then top1 = 1 and top2 = MAXSIZE - 1. Here top1 + top2 = MAXSIZE. Since both stack are not full. Hence no overflow. So false
• (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2 + 1) will true when both stack has n/2 element but space is not effectively used i.e. when stack 1 has no element and stack 2 has n - 1 elements then it will not detect overflow. So false
• top 1 = top2 - 1 is true, since it cover all cases when both stack are with full capacity, stack 1 is empty and stack 2 is full and vice-versa. Hence true