Error in implementation of a stack with O(1) find-max/find-min?

0
votes

I have implemented several functions for the Stack ADT. I am trying to find the max and min values in O(1) time and I have augmented my stack structure to serve this purpose. This is my code:

 void mms_push(MMStack mms, int i) {

struct llnode *new = malloc(sizeof(struct llnode));
new->item = i;
if(mms->len!=0)
{
 new->next = mms->topnode;
 mms->topnode = new;
}
else 
{
 new->next = NULL;
 mms->topnode = new;
}

if (mms->len == 0)
{
mms->topnode->minc = i;
mms->topnode->maxc = i;}
else
{
  if(mms->topnode->maxc < i)
  {
      mms->topnode->maxc = i;
  }

  if(i<mms->topnode->minc)
  {
      mms->topnode->minc = i;
  }


mms->len++;}


int mms_pop(MMStack mms) {
  assert(mms);
  int ret = mms->topnode->item;
  struct llnode *backup = mms->topnode;
  mms->topnode = mms->topnode->next;
  mms->len--;


  free(backup);
  return ret;
}

My structures used are as below:

struct llnode
{

  int item;
  struct llnode *next;
  int minc;
  int maxc;
};

struct mmstack
{
  int len ;
  struct llnode *topnode;

};


typedef struct mmstack *MMStack;

I am not getting the correct value of max and min values. How do I correct the code so that I get the right value of max and min element in the stack?

Thanks in advance!

2
cdata-structuresstack
c or c++? my bet is c. - luk32
Q: What do you mean by "not correct value"??? - FoggyDay
@luk32 i am sorry for not mentioning its in c - user4672411
@FoggyDay these are the assertions i made(the last one is failing): mms_push(mms, 10); mms_push(mms, 5); mms_push(mms, 20); assert(mms_max(mms) == 20); assert(mms_min(mms) == 5); - user4672411
Check your pop function, shouldn't you update min and max there as well? In general getting the min and the max from a stack does not sound like a good idea; a stack is a LIFO ADT. - zakkak

2 Answers

1
votes

Take a look at this code:

if (mms->len == 0)
{
  mms->topnode->minc = i;
  mms->topnode->maxc = i;
}
else
{
  if(mms->topnode->maxc < i)
  {
      mms->topnode->maxc = i;
  }

  if(i<mms->topnode->minc)
  {
      mms->topnode->minc = i;
  }
}

Notice that in the else branch, you're reading the values of mms->topnode->minc and mms->topnode->maxc before you've initialized them. I think you meant to look at the values of mms->topnode->minc/maxc before you reassigned mms->topnode. To fix this, try doing something like this:

else
{
  mms->topnode->maxc = mms->topnode->next->maxc;
  mms->topnode->minc = mms->topnode->next->minc;

  if(mms->topnode->maxc < i)
  {
      mms->topnode->maxc = i;
  }

  if(i<mms->topnode->minc)
  {
      mms->topnode->minc = i;
  }
}

These extra two lines initialize the min and max values to the old max values before comparing against i, which should ensure that they get a value.

Hope this helps!

0
votes

You're doing things a bit backwards — comparing i to the values in the new, uninitialised node after you have inserted it in the stack.

It's easier to first prepare the new node completely, and then link it into the stack.

Assuming that an empty stack has a NULL topnode:

void mms_push(MMStack mms, int i) {
   struct llnode *new = malloc(sizeof(struct llnode));
   new->item = i;
   new->next = mms->topnode;
   if (!mms->topnode)
   {
       new->minc = i;
       new->maxc = i;
   }
   else
   {
      new->minc = min(mms->topnode->minc, i);
      new->maxc = max(mms->topnode->maxc, i);
   }
   mms->topnode = new;
   mms->len++;
}

I'm not sure if min and max are C99, but they're trivial to define.