ISRO2020-72

Question

A stack is implemented with an array of $’A[0...N-1]’$ and a variable ‘$pos$’. The push and pop operations are defined by the following code.

push (x)
    A[pos] <- x
    pos <- pos -1
end push
pop()
    pos <- pos+1
    return A[pos]
end pop

Which of the following will initialize an empty stack with capacity $N$ for the above implementation​​​

• A. $pos \leftarrow -1$
• B. $pos\leftarrow 0$
• C. $pos\leftarrow 1$
• D. $pos\leftarrow N-1$

Comments

i think D is the ansewer

Answer 1

Answer D.

Stack is growing downwards, and on pushing an item, the top [pos] is decrementing by one, meaning the on the topmost position [pos] will be 0, or (N - 1 - (N - 1)], so the initial value of [pos] will be N - 1

Comments

@habedo007

if we try to perfom POP operation 1st then value of pos becomes N which will result in invalid array index.We should check if both operations can be done appropriately or not.

If we check for both the operations then none of the pos value is correct.

Please clear my doubt if i am wrong.

Answer 2

I think answer will be d) $pos\leftarrow N-1$

Because here the 1st element is added at the end first and we find that the pointer is decremented after it has added the element. So, here the pointer shouldhave been initiallized to N-1.

Answer 3

push (x)

A[pos] <- x

pos <- pos -1

end push

Look at the push operation. $x$ is pushed at pos, then pos is decremented.

This means if our array is $A[0,1,2,3]$ then in order to push four elements, we first we're pushing at index 3, then at index 2, then at index 1 and finally at index 0.

We have to initialize pos with the value equalling $N-1$

 

Option D