CODEWITHSUNDEEP
c
choijam
choijam

Reputation: 43

Why do we initialize top of the stack as -1?

Why do I have to initialize one of the stacks to -1? Where would top1 point to? 

int ar[SIZE];
int top1 = -1;
int top2 = SIZE;

void push_stack1 (int data)
{
  if (top1 < top2 - 1)
  {
    ar[++top1] = data;
  }
  else
  {
    printf ("Stack Full! Cannot Push\n");
  }
}

Upvotes: 0

Views: 4913

Answers (3)

Moinuddin Quadri
Moinuddin Quadri

Reputation: 48092

No, you wouldn't have to initialize top1 as -1 at all if your code would have been:

int ar[SIZE];
int top1 = 0;   // 0 `here`
int top2 = SIZE;

void push_stack1 (int data)
{
  //        v  conditional check with `<=` instead of `<`
  if (top1 <= top2 - 1)  // even better: `if (top1 < top2)`
  {
    ar[top1++] = data;
    //    ^  using "top1++" instead of "++top1"
  }
  else
  {
    printf ("Stack Full! Cannot Push\n");
  }
}

++something (also known as pre-increment) will increment the value of something, and then return the incremented value.

Whereas, something++ (also known as post-increment) will increment the value of something, but return the original value that something held before being incremented.

But you must note here that whether it is ++top1 or top1++, we are always passing 0 as the first index to ar because the 0 is the first index of any array/list in all the languages.

Upvotes: 3

Paul Ogilvie
Paul Ogilvie

Reputation: 25286

The difference is whether you let top1 point to the last used element or the first free element.

With -1 you let it point to the last used element.

With 0 you let it point to the first free element.

There is also symmetry in the use of pre-increment/decrement and post-increment/decrement.

Initializing to -1 implies ++top1 for push and top1-- for pop.

Initializing to 0 implies top1++ for push and --top1 for pop.

Upvotes: 3

user2736738
user2736738

Reputation: 30926

This is really odd that you started to think that in stack datastructure's implementation - you would have to initialize top with -1. Whick book said that? If any book did, at it's best it can mostly mean that the implementation they showed is following that.

Where would top1 point to? If you directly index into an array object, then yes it would likely try to access a memory which is out of the array bound, which is surely an undefined behavior(Arrays are 0-indexed in C ). But in every scenarios, we see implementation where top is increased first (in case top is initialized with -1)++top and then that value is used to index into array (For the very first time this will result in 0), which is precisely the case here. (Array is mentioned here because it seems that underlying data structure the code you showed uses that).

So top=-1 will initially mean that it is in a empty state and you can say no member is being added to the stack data structure. Here you could have initialized top with 0 also provided that you would have to change your push,pop or isEmpty() and other auxiliary functions associated with this data structure implementation accordingly, as needed.

Also you can check your other function's implementation to get the justification of top=-1 for the implementation with which you are working on.

Also if you are in doubt about what ++ does here and how is it significant - Look what C11 standard has to say about it (N1570Draft)

In section §6.5.3.1¶2

The value of the operand of the prefix ++ operator is incremented. The result is the new value of the operand after incrementation.

++top1 will result in the new incremented value which is 0 in case it was -1 earlier.

Upvotes: 1

Related Questions