Question

Consider a single array A[0.... n - 1] is used to implement two stacks. Two stacks grows from opposite ends of the array Variables top1 and top2 points to the location of the top most element in each of the stacks with initial values of -1 and n respectively and top1 < top2 always. If certain push and pop operations are performed at either end, then which of the following represents the number of elements are present in the array at any time?

• A. n -1 - top2 + top 1
• B. n + 1 - top 2 + top 1
• C. n - top 2 + top 1
• D. top 1 - top 2 + n

Answer 1

The correct option is B n + 1 - top 2 + top 1

Consider array representation of stacks:
-1 0 n-1 n

top1 =-1 represents no element in stack -1
top 2 = n represents no element in stack - 2
So, check option one by one when both stacks are empty :
(a) -1 -n+n = -1 not possible
(b) n-n+-1 = -1 not possible
(c) n+1 -n +(-1) = 0 only possible option
(d) n-1-n+(-1) = -2 not possible
Now consider for both stack has '2' elements each :

10

20

40

30

-1 0 1 2 3 .... n-4 n-3 n-2 n-1 n

Apply in option (c)

= n+1 -(n-2) + 1
=n+1 - n + 2 +1
= 4

So, option (c) is correct.