Logical error in push operation in stack

Question

I am doing insert operation on stack as an array but my program is crashing on entering the first value.

typedef struct Stack
{
  int top;
  int elements[20];
}
stack;
stack *s;

void push(int x)
{
  s->top++;
  if(s->top<=19){
  s->elements[s->top]=x;}
  else
    puts("Overflow");
}

Sourav Ghosh · Accepted Answer · 2015-03-23T13:14:07.340

1

As per your present code, it looks like you're using s uninitialized. Use of unitialized memory invokes undefined behaviour which in turn may cause segmentation fault.

For safeguard from unitisalized s , you may want to modify your code like

void push(int x)
{
  if (s)         //check if `s` has been initialized.
  {
      s->top++;
      if(s->top<=19)
      {
          s->elements[s->top]=x;
      }
      else
          puts("Overflow");
  }
  else
      //abort, return error or something similar
}

NOTE:

Apart from the issue in hand here, there is one more hidden issue which will come forth as soon as you fix this issue.

In your push() function, you're incrementing the top value unconditionally. That means, even if the stack is full, your top value will increase and later it will cause in errorneous calculations.

You have to move the stack top increment part also under the value range checking.

edited Mar 23 '15 at 13:14

answered Mar 23 '15 at 12:59

Sourav Ghosh

133,132
16
183
261

that check `if (s)` is a bit tricky; it can be user freed `s`-and didn't set to NULL. Hence that check will be OK - actually it will be UB – Giorgi Moniava Mar 23 '15 at 13:33
@Giorgi Right, but _most_ of the time, adding a _simple_ null check can save you a lot of headache. :-) BTW, do you have any improvement proposal? – Sourav Ghosh Mar 23 '15 at 13:36
probably tell user to set pointer to NULL after freeing, otherwise that if statement will trigger UB: https://stackoverflow.com/questions/26704344/why-does-misra-c-state-that-a-copy-of-pointers-can-cause-a-memory-exception/26704747#26704747. Those if statements make sense if you can make sure that the fact that pointer isn't NULL means that pointer is valid - this can be further tricky given on Linux for example malloc may fail and return not null – Giorgi Moniava Mar 23 '15 at 13:40
@Giorgi I completely agree. The information above is very helpful, but IMHO, a little bit out of context in present scenario. We don't have any idea about the `free()`ing part implementation, do we? Nevertheless, thanks for the useful information. Hope it will help somebody. :-) – Sourav Ghosh Mar 23 '15 at 13:45
1

Yes you are right. Also it would not make sense to call `push` on freed `s`; but that check wouldn't save you either. Unless you set it to NULL after freeing. But then that malloc/Linux issue would be a separate issue – Giorgi Moniava Mar 23 '15 at 13:51

score 1 · Answer 2 · answered Mar 23 '15 at 13:09

It seems you simply defined a pointer of type struct Stack but not allocated the stack itself

stack *s;

Thus s is equal to NULL. At least you should allocate the stack itself. For example

stack *s;

//...
s = malloc( sizeof( struct Stack ) );

But in any case there is no any need to define a pointer. You could define the stack itself. For example

stack s;

Aldo you need to set an initial value of data member top. I think you could initialize it with -1.

Also function insert itself is invalid.

void push(int x)
{
  s->top++;
  if(s->top<=19){
  s->elements[s->top]=x;}
  else
    puts("Overflow");
}

Each time the function is called it increases data member top even if it points already beyond the array. The valid function could look like

void push(int x)
{
   if ( s->top + 1 < 20)
   {
      s->elements[++s->top] = x;
   }
   else
   [
       puts("Overflow");
   }
}

Logical error in push operation in stack

2 Answers2