1,798 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

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 votes
1 votes

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.

Related questions

2 votes
2 votes
1 answer
1
Lakshman Bhaiya asked Oct 22, 2018
3,909 views
A stack of size (1 to N) and the initial position of top pointer is 0.get(i,S) is aroutine to get ith element from stack 'S' with respect to top.then,what is the underflo...
0 votes
0 votes
1 answer
2
Abhrajyoti00 asked Oct 29, 2022
718 views
Can there be “Stack Overflow” in Linked list Implementation of stack? If Yes, how?