GATE OVERFLOW

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 top 2 (top < top 2) 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 = MAXSIZE / 2) and (top2 = MAXSIZE / 2 + 1)
B. top1 + top2 = MAXSIZE
C. (top1 = MAXSIZE / 2) or (top2 = MAXSIZE)
D. top1 = top2 - 1

ANSWER IS :--D
EXPLANATION :Since the stacks are growing from opposite ends, initially top1 = 1 and top2 = MAXSIZE. Now, to make the space usage
most efficient we should allow one stack to use the maximum possible space as long as other stack doesn't need it. So,
either of the stack can grow as long as there is space on the array and hence the condition must be top1 = top2 - 1;

HERE OPTION B ALSO SATISFING SAME REASON..WHY CANT ANSWER NOT B..?????

Comments

suppose, both stack start from both end.

When top1 pointing 1st index & top2 pointing (MAXSIZE-1)^th index then, a/c option B top1 + top2 = MAXSIZE

but, this is not the condition for “stack full”. Stack will still grow..

---

yes it right

---

Assume array of size 10.
Initially empty...
Top1=-1 & top2=11
Assume top1= 3 and top2=4 (stacks have 3 and 7elements respectively)
Clearly 3+4 != 10
But 3=4-1

This should explain why b is wrong

Answer 1

In initial consider A is empty and let its size is 15

since array is empty from both side so top1=0 and top2=16

summation of both will gave 16 which is not equal to maxsize.