Stacks

[grisha83]

Hello,
I was wondering why do we need to assign value of -1 to the top of the stack?
topOfStack = -1;
Thank you

[Grn Xtrm]

The top of the stack is -1 when the stack is empty. When you fill it using push(), the top will change. A return value of -1 lets the user know that the stack is empty.

[Mubo]

hi dear, let me try to say some about you question.

I think ur question is why stacks are assigned -1 when determining if they are empty();
i think , it is because the index position of -1 is the empty position of the stack. they follow the integer rule, which begins from 0 to n Numbers.So is useful to assign -1, so u can easily determine that there is no elements on the stack

[hardik.rajani]

Hello,
I was wondering why do we need to assign value of -1 to the top of the stack?
topOfStack = -1;
Thank you

No dear it is not compulsory to set topOfStack by -1.

But there is some tradition as well some concept for predefined. If you want to follow the tradition you should set it to -1. Else you can also set it 0. But if you sets it to 0 then you have to make relative changes to the traditional code of stack.

Just for advise don't go beyond the tradition if it is not essential. Because in future you may have to work with a big team at that time it will be hard for other. This is my own experience.

[verruckt24]

As hardik.rajani mentions there's is little programming "tradition" to this.

The concept of the Top of Stack is that the Top should always point to the uppermost/topmost element in the Stack.

Now to follow this concept, it would be a logical thing that you first need to increment the top counter by one so that it points to an empty position in the Stack (the new top) and then enter an element at this position, so again after the completion of this operation our view of the Stack is consistent of the Top pointing to a the topmost element.

This is in the case of the Array implementation of Stack, and since we know arrays have a beginning index as 0 we cannot have the top pointing to 0 as in that case it would wrongly be conveyed that there exists a single element in the Stack. So we keep the top pointed to something that is one position lower than 0 (-1) so that the operation of adding elements to the Stack performs as mentioned above:
1. Increment top by 1
2. Add element to top

The remove/pop operation proceeds this way:
1. Copy element at top position
2. Decrement top by 1
3 Return copied element.

Following this procedure we can be sure that if the top points to -1, the Stack must certainly be emtpy, thats the reason we check the top being equal to -1 for the "Stack Empty" condition.

To address the question whether the top can be made equal to 0 initially, then in this case we would have modify the add operation this way:
1. Put element at position top.
2. Increment top by 1.

But in this case, as you must certainly have gathered the top would never point to the topmost element but at a position one above the topmost element. While we can certainly work this way, by modifying our pop operation accordingly, one problem that such a method might cause to our implementation would be of memory.

To explain this, consider that whenever you reach the max size of the array the array capacity is doubled. Now in the latter implementation, the capacity would be doubled when there is still a position vacant, which has a possibility of not being filled at all.

There's one more way in which the latter implemenatation can be modified in a way such that the top still points to the topmost element.

1. If top == 0
1.1 Put element at top.
2. Else
2.1 Increment top by 1
2.2 Put element at top.

But then we would have lost the simplicity of the push/pop operations for absolutely no gains.

So it's found better (which I mentioned as programming "tradition") to keep the top at one position below the start position which is -1.

NOTE : This is in the case of an array implementation of the Stack, LinkedLists implementation will always have the top as null when the stack is empty.

[grisha83]

Thanks to everyone for explanations.