in DS
1,770 views
3 votes
3 votes

A stack of size (1 to N) and the initial position of top pointer is 0.

Get (i, S) is a routine to get ith element from stack ‘S’ with respect to top.

Then, what is the underflow condition on stack to perform get() operation.

  • top – i < N

  • top – i + 1 ≤ N

  • top – i ≤ 0

  • top – i + 1 ≤ 0

in DS
1.8k views

4 Comments

take top =1 and i=1 still underflow but there's one element
0
0
so,how is option D correct here??
0
0
substitute the values and see it won't underflow
0
0

3 Answers

3 votes
3 votes

Option D is correct.

Take an example : 

Initially TOP = 0 and i = 0. 

we perform PUSH(S, 10), PUSH(S, 20), PUSH(S, 30), PUSH(S, 40), PUSH(S, 50), 

now TOP = 5 and i = 1 to 5.

[N = Number of Elements in Stack]

Case I : TOP - i < N

              5 - 5 < N

                0 < 5. ie. giving underflow but its not underflow because at i = 5 we have 10 present. [ A is Incorrect

Case II : TOP - i + 1 < N

              5 - 5 + 1 < N

                1 < 5. ie. giving underflow but its not underflow because at i = 5 we have 10 present. [ B is Incorrect

Case III : TOP - i <= 0

              5 - 5 <= 0

              0 <= 0. ie. giving underflow but its not underflow because at i = 5 we have 10 present. [ C is Incorrect

Case IV : TOP - i + 1 <= 0

              5 - 5 + 1 <= 0

              1 <= 0. ie. NO underflow

              5 - 6 + 1 <=0

              0 <= 0. Correct underflow.   Hence, D is correct answer.

1 vote
1 vote

Get (i, S) is a routine to get ith element from stack ‘S’ with respect to top.

The meaning of the above statement is we have to get the ith element from the stack by considering top as the first element.

For example , if top =4, and i=2 . we have to get the 2nd element from the stack by considering top as the 1st element.That means we have to perform pop() operation two times in order to get the 2nd element by considering top as the 1st element.This is the definition of the question.

It is easy to eliminate  first 2 options since we are not checking for overflow.

Consider this example. If top =4, then i>0 and i<=4. These values of i will not lead to underflow condition. If i>4 then there will be underflow.

Option c will not allow you to access 4th element from top if top=4.  But it is possible to access 4th element if top =4.

Option c says that top-i<=0 is the necessary condition for underflow which is completely false since we can able to access kth element if top=k.

So option D is the right option.if top=4 and we want access 4th element from top,option D assures that this access will not lead to underflow, since (4-4)+1>0

so option D is the right answer.

0 votes
0 votes
The subroutine affects $Top$ as follows -

$Get(i,S) : Top = Top - i$, where $i \in [0,N-1]$

Therefore underflow condition will be

$\implies Top-i < 0 \implies Top-i \leq -1 \implies Top-i +1\leq0$,

Therefore $D$ is the correct answer.