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?

Option 4 : pos ← N - 1

Concept:

Usually, the empty stack is initialized with value 0 and this value increments by 1 every time we push an element on to the stack.

The code for such a stack looks like this,

push (x)

                A ← x

                pos ← pos + 1 //the initial value is incremented by 1 as element is pushed onto the stack

end push

However, in the question, when push operation takes place, the value of variable is decremented by 1 (pos – 1).  Hence, initial value of pos will have to be N-1.

Explanation

For example, if we take an array with N = 4 to represent our stack. It will be A .

Now, in order to push four elements, say x, y, z, w

• First we will push at x index 3 which is 4 – 1
• Then, we will decrement pos and push y at index 2 and so on.

Note that, the pop operation is also behaving inversely here.

• In usual stack, pop would decrement value of pos.