0

I am trying to implement a simple stack in C++ using a linked list, but I am completely stumped by the PUSH() function. I've been working on it all night and it's nearly driven me bonkers. It should insert an element at the top of the stack, but every way I've tried to implement is has had issues. An excerpt of my relevant code is as follows:

template <typename T>
struct NODE{
  T data;
  NODE<T> *next;
}

template <typename T>
void PUSH(T x, NODE<T> *S){
  NODE<T> *tmp = new NODE<T>;
  tmp->data = x;
  tmp->next = S;
  S = tmp;
}

int main(){
  NODE<int> *test = new NODE<int>;
  test->data = 111;
  test->next = NULL;
  PUSH(99, test);
  PUSH(88, test);
  std::cout << test->data << std::endl;
}

I would expect the last line to print 88, but instead it prints 111. When I try to access the next element, I get a segfault so clearly I must be doing something wrong. Maybe I'm just tired, but hopefully one of you could shine some light on where I'm messing up, it seems correct to me.

lazerpickle
  • 3
  • 1
  • 4
  • As a note: You should not use uppercase for class, function or variable names. If you use uppercase letters you might get conflicts with prepossessing macros and those conflicts are not easy to debug. For a single char name like `T` it is ok, but you should write `Node` or `node` and `push`, instead of `NODE` and `PUSH`. – t.niese Aug 09 '17 at 07:01
  • My naming is not usually this horrendous but I appreciate the feedback. – lazerpickle Aug 09 '17 at 07:08

1 Answers1

1
void PUSH(T x, NODE<T> *S)
{
}

You are passing S by value, so any changes you make to S inside PUSH will not be visible outside.So even though you are adding elements to your stack, but your top remains the first node (111).

You can either pass a pointer to pointer to S or a reference to S

void PUSH(T x, NODE<T> **S)
{
   NODE<T> *tmp = new NODE<T>;
   tmp->data = x;
   tmp->next = *S;
   *S = tmp;
}
Gaurav Sehgal
  • 7,422
  • 2
  • 18
  • 34
  • I suppose my understanding of pointers needs work then. So if passed by value, you can modify the data the pointer points to, but you can't make it point to a new memory address? – lazerpickle Aug 09 '17 at 07:22
  • @lazerpickle correct, because that would mean to change the value of pointer. – Gaurav Sehgal Aug 09 '17 at 07:39