Made Easy Test Series:DS-Stack and Queue

Question

Consider a single array $A\left [ 0...........(n-1) \right ]$ is used to implement two stacks. Two stacks grows from opposite end of the array. Variable  $top_{1}$ and $top_{2}$ points to the location of the topmost elements in each of the stacks with initial values of $-1$ and $n$ respectively and $top_{1}<top_{2}$ always. If  certain push and pop operations are performed in either end, then which of the following represents the number of elements are present in the array at any time?

$A)n-top_{2}+top_{1}$

$B)n+1-top_{2}+top_{1}$

Answer 1

Ans is B

Initially the array must be empty that is, it must contain 0 number of elements. Now we are given that top 1 = -1 and top2= n

when no elements are inserted the 2 pointers remain in their same location, i.e. -1 and n

now putting these values in equation a and b  we get

a) n-top2+top1

= n-n+(-1)

= -1

b) n+1−top2+top1

 = n+1-n-1

=0

As we all know initially the elements in the array is 0. therefore b is the ans.. :)

Comments

Suppose take a situation

A stack contains $8$ elements

and it is array location $A\left [ 0,....,7 \right ]$

And Stack1 contains

$A\left [ 0 \right ]=x$,$A\left [ 1 \right ]=y$,$A\left [ 2 \right ]=z$

Stack2 contains

$A\left [ 5 \right ]=u$,$A\left [ 6 \right ]=v$, $A\left [ 7 \right ]=w$

Now apply the formula $B)$

According to formula

$n+1-top2+top1=8+1-5+2=6$

Now, that is not correct
right?

because, stack contains only 6 elements

---

Initially stack contains 0 element and i have used my test case for the same.. if i insert 2 elements now one from top1 and another from top2 the value of top1 becomes 0 and value of top2 becomes n-1

now putting these values in b) n+1−top2+top1 we get n+1-(n-1)+1 = 2 i.e. there are 2 elements in the array..

so it is clear that formula b is the right answer for ANY time..

---

yes, My bad

Got the logic.

In my example

There is top1 is in a[2], and top1 is in a[5]

So, gap between  in this array is 2 elements , i.e. a[3] and a[4].

But when we actually subtracting , we got 5-2=3 element 

To cancel out that extra 1 we  have to subtract it from (n+1) elements

And thus got total elements

Thanks .

Answer 2

Answer is B.

Comments

@sagar2405 explain plz