STACK in c program. pop operation not working

Question

Guys what is wrong with this program. I am having problems with pop operation, it shows an extra value even after stack is empty. ??

void initstack (struct stack * p, int maxSize) 

void push (struct stack * p, int item) 

int pop (struct stack * p) 

void display (struct stack p) 

 struct stack

{

   int * a;

   int top;

   int maxSize;

};

Note:using d above structure and functions are mandatory..

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct stack {
    int * a;
    int top;
    int maxSize;
};
void initstack(struct stack * p, int maxSize);
void push(struct stack * p, int item);
int pop(struct stack * p);
void display(struct stack p);
int StackIsEmpty(struct stack * p);
int StackIsFull(struct stack * p);
void printMenu();

int main()  {
    struct stack p;
    int data,ch, data1, m;
    printf("Enter the maximum size of the stack\n");
    scanf("%d",&m);
    initstack(&p,m);
    do {
    printMenu();    
    printf("Enter your choice\n");
    scanf("%d",&ch);
    switch(ch) {
      case 1:
        printf("Enter the element to be pushed\n");
        scanf("%d",&data);
        push(&p, data);
        break;
      case 2:
        data1 = pop(&p);
        if(data1 != -1000)
        printf("The popped element is %d\n",data1);
        break;
      case 3:
        printf("The contents of the stack are");
        display(p);
        printf("\n");
        break;
      default:
        exit(0);
    }
    } while(1);
    return 0;
}

void printMenu()
{
    printf("Choice 1 : Push\n");
    printf("Choice 2 : Pop\n");
    printf("Choice 3 : Display\n");
    printf("Any other choice : Exit\n");
}

void initstack(struct stack * p, int maxSize) {
    int *newContents;
  newContents=(int *)malloc(sizeof(int)*maxSize);
  p->a=newContents;
  p->maxSize=maxSize;
  p->top=-1; 
}

void push(struct stack * p, int item) {
    if(StackIsFull(p))
    {
      printf("Stack is full\n");
    }
  p->a[++p->top]=item;
}

void display(struct stack p) {
  int i;
  struct stack *b=&p;
  if(StackIsEmpty(b))
    printf(" {}");
  for(i=0;i<b->top;i++)
  {
    printf(" %d",b->a[i]);
  }
}

int pop(struct stack * p) {
    if(StackIsEmpty(p))
    {
      printf("Stack is empty\n");
      return -1000;
    }
  else
    return p->a[--p->top];
}

int StackIsEmpty(struct stack *p)
{
  return p->top == -1;          //p->top==-1;
}

int StackIsFull(struct stack *p)
{
  return p->top >= p->maxSize-1;
}

Please do not cast the result of malloc. That can hide errors. — fuz
– fuz, Commented Apr 27, 2015 at 14:32
Well, have you stepped through each line of code in the debugger? — OldProgrammer
– OldProgrammer, Commented Apr 27, 2015 at 14:33
removed malloc casting.. am getting no errors.. after stack gets empty if i try to pop i get 17 as result popped — Subin S V
– Subin S V, Commented Apr 27, 2015 at 14:35

John Bode · Accepted Answer · 2015-04-27 15:41:53Z

Let's look at your push and pop operations:

p->a[++p->top]=item; // push
p->a[--p->top];      // pop

Let's assume the stack is empty and top is -1. When you do a push, you increment top to 0 and write your element to p->a[0]. When you pop that element, you first decrement top back to -1, and then try to access the element p->a[-1].

This is a problem. Not only are you popping the wrong element, you're accessing an element outside the range of your array and invoking undefined behavior.

You need to change the stack pointer after you access the element you want, like so:

p->a[++p->top] = item; // push
item = p->a[p->top--]; // pop

For array-based stacks, it's actually a little more natural for the stack to grow "downwards", like so:

p->top = p->maxSize = maxSize; // init

if ( p->top )            // p->top != 0 means room left on the stack
  p->a[--p->top] = item; // push

if ( p->top < p->maxSize ) // p->top < p->maxSize means elements left on stack 
  return p->a[p->top++];   // pop

This way, you don't run the risk of accessing an element outside the range of the array. p->top will always be between 0 and maxSize - 1.

Finally, a style note:

You don't need to cast the result of malloc; it just adds visual clutter, and in some cases can suppress a useful diagnostic. You can clean it up by simply writing:

 /**
  * Whitespace is your friend.  Use it.
  */
 newContents = malloc( sizeof *newContents * maxSize );

sizeof *newContents is the same as sizeof (int); this way, if you ever decide to change the type of the stack array, you don't have to worry about changing the malloc call itself. Saves some maintenance headaches, reads a little easier.

Edit

Here's part of what's causing your headaches:

void push(struct stack * p, int item) {
    if(StackIsFull(p))
    {
      printf("Stack is full\n");
    }
    p->a[++p->top]=item; // DANGER WILL ROBINSON!
}

If the stack is full you print a warning, and then you push the element anyway.

You need an else branch in there

void push(struct stack * p, int item) 
{
  if(StackIsFull(p))
  {
    printf("Stack is full\n");
  }
  else
  {
    p->a[++p->top]=item;
  }
}

Subin S V · Accepted Answer · 2015-04-27 15:47:10Z

Thanks guys, I fixed it.. works fine. thanks for all ur suggestions.

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct stack {
    int * a;
    int top;
    int maxSize;
};
void initstack(struct stack * p, int maxSize);
void push(struct stack * p, int item);
int pop(struct stack * p);
void display(struct stack p);
int StackIsEmpty(struct stack * p);
int StackIsFull(struct stack * p);
void printMenu();

int main()  {
    struct stack p;
    int data,ch, data1, m;
    printf("Enter the maximum size of the stack\n");
    scanf("%d",&m);
    initstack(&p,m);
    do {
    printMenu();    
    printf("Enter your choice\n");
    scanf("%d",&ch);
    switch(ch) {
      case 1:
        printf("Enter the element to be pushed\n");
        scanf("%d",&data);
        push(&p, data);
        break;
      case 2:
        data1 = pop(&p);
        if(data1 != -1000)
        printf("The popped element is %d\n",data1);
        break;
      case 3:
        printf("The contents of the stack are");
        display(p);
        printf("\n");
        break;
      default:
        exit(0);
    }
    } while(1);
    return 0;
}

void printMenu()
{
    printf("Choice 1 : Push\n");
    printf("Choice 2 : Pop\n");
    printf("Choice 3 : Display\n");
    printf("Any other choice : Exit\n");
}

void initstack(struct stack * p, int maxSize) {
    int *newContents;
  newContents=malloc(sizeof(int)*maxSize);
  p->a=newContents;
  p->maxSize=maxSize;
  p->top=-1; 
}

void push(struct stack * p, int item) {
    if(StackIsFull(p))
    {
      printf("Stack is full\n");
    }
    else
    {
    p->a[++p->top]=item;  //FIXED LINE, ELSE BLOCK ADDED
    }
}

void display(struct stack p) {
  int i;
  struct stack *b=&p;
  if(StackIsEmpty(b))
    printf(" {}");
  for(i=0;i<=b->top;i++)   //FIXED PREVIOUSLY for(i=0;i<b->top;i++)
  {
    printf(" %d",b->a[i]);
  }
}

int pop(struct stack * p) {
    if(StackIsEmpty(p))
    {
      printf("Stack is empty\n");
      return -1000;
    }
  else
    return p->a[p->top--];     //FIXED PREVIOUSLY p->a[--p->top];
}

int StackIsEmpty(struct stack *p)
{
  return p->top < 0;          //FIXED PREVIOUSLY p->top==-1;
}

int StackIsFull(struct stack *p)
{
  return p->top >= p->maxSize-1;
}

fuz · Accepted Answer · 2015-04-27 14:35:19Z

0

Your display logic is faulty. It has an off-by-one error and skips the topmost element.

answered Apr 27, 2015 at 14:35

fuz

94.7k27 gold badges216 silver badges391 bronze badges

5 Comments

Subin S V Over a year ago

please help me correct it bro... i am newbie to programming

fuz Over a year ago

@SubinSv Try fiddling around with the loop in the display function until it shows all stack entries. I assume you wrote this code yourself? Then you should be familiar with how it works.

Subin S V Over a year ago

as i told, am a newbie here. i took it from an internet source, and forked it with those mandatory functions..

fuz Over a year ago

@SubinSv It would help if you could do your homework on your own instead of copying something from the internet. You don't learn anything that way.

Subin S V Over a year ago

thank you bro,.. Actually am a php developer, and beginner in c. I was given this task by company as a part of training.. Thanks for helping me out.

fuz · Accepted Answer · 2015-04-27 14:37:56Z

0

return p->a[--p->top];

In this part I think you should first

int result =  p->a[p->top];

then

p->top --;
return result;

I had same issue and that helped me.

edited Apr 27, 2015 at 14:37

fuz

94.7k27 gold badges216 silver badges391 bronze badges

answered Apr 27, 2015 at 14:36

Anano

211 silver badge7 bronze badges

1 Comment

Subin S V Over a year ago

now also am facing issues... still it produces a new output

mcleod_ideafix · Accepted Answer · 2015-04-27 14:43:20Z

0

It hink the problem is related to push and pop functions. Both use preincrements, so the last item you push is not the first item you pop.

Your push does: first increment top, then store value in a[top]. So top is pointing to the newly pushed element.

Your pop does: first decrement top, then retrieve the value at a[top]. The value retrieved won't be the last pushed, but the previous-to-last. top keeps pointing at this very same value.

My suggestion: leave push as is, and change pop as this:

int pop(struct stack * p) {
    if(StackIsEmpty(p))
    {
      printf("Stack is empty\n");
      return -1000;
    }
  else
    return p->a[p->top--]; /* post-increment!! */
}

So, push will leave top pointing at the last pushed value. pop will retrieve this value, then decrement top, leaving it pointing at the next value to retrieve.

edited Apr 27, 2015 at 14:43

answered Apr 27, 2015 at 14:38

mcleod_ideafix

11.5k2 gold badges30 silver badges33 bronze badges

4 Comments

Subin S V Over a year ago

i tried this.. pushed 3 elements. 1 2 and 3.. when i pop i get 4 3 and 2

mcleod_ideafix Over a year ago

I've also fixed display function, to display the last element pushed.

Subin S V Over a year ago

fails for this input 3 1 1 1 2 1 3 1 4 3 2 2 2 2 3 4

John Bode Over a year ago

@SubinSv: You're still pushing an element when the stack is full - you need an else branch in your push function.

Collectives™ on Stack Overflow

STACK in c program. pop operation not working

5 Answers 5

Comments

Comments

5 Comments

1 Comment

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

5 Comments

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related