C++ stack implementation pop function not working

Question

I'm implementing a stack with a linked list for review. My pop function isn't working correctly. I created a test with the nodes in main doing the exact same thing my linkedList function is doing but I'm getting a segmentation fault ever time time. Here is the code.

#include <iostream>

struct Node{
  int data;
  Node* next;
};

class Stack{
  private:
    Node head;
    int size;
  public:
    Stack();
    ~Stack();
    int getSize();
    void push(int val);
    int pop();
    void printStack();
};

Stack::Stack(){
  head.data = 0;
  head.next = NULL;
}

Stack::~Stack(){
}

int Stack::getSize(){
  return size;
}

void Stack::push(int val){
  Node newNode;
  newNode.data = val;
  if(size == 0) newNode.next = NULL;
  else newNode.next = head.next;
  head.next = &newNode;
  size++;
}

int Stack::pop(){
  int returnVal = head.next->data;
  head.next = head.next->next;
  return returnVal;
}
}


int main(){
  Stack s;
  s.push(8);
  s.push(30);
  s.push(40);
  int value = s.pop();
  int value2 = s.pop(); //segmentation fault
  std::cout<<value<<"\n"<<value2<<"\n"; 


/* This works correctly
  Node head;
  head.data = 0;
  head.next = NULL;
  Node n1;
  n1.data = 5;
  n1.next = NULL;
  head.next = &n1;
  Node n2;
  n2.data = 8;
  n2.next = head.next;
  head.next = &n2;
  Node n3;
  n3.data = 30;
  n3.next = head.next;
  head.next = &n3;

  int value = head.next->data;
  std::cout << value << "\n";
  head.next = head.next->next;
  value = head.next->data;
  std::cout << value << "\n";
*/
  return 1;
}

Are you sure the segmentation fault occurs at the cout line and not when calling pop() ? — Tim Biegeleisen
– Tim Biegeleisen, Commented Jan 26, 2017 at 2:01
I'm sorry. Should've been more specific. It definitly happens at the SECOND call to pop() — user3736114
– user3736114, Commented Jan 26, 2017 at 2:02
As well as the actual answers, shouldn't pop adjust size? — John3136
– John3136, Commented Jan 26, 2017 at 2:06
Once you figure out how to make your manual Stack implementation work correctly, you should then update it to use the standard std::list class instead of a manual list, and then when you have that working correctly, chuck it all out and just use the standard C++ std::stack class instead. — Remy Lebeau
– Remy Lebeau, Commented Jan 26, 2017 at 2:28

Shaana · Accepted Answer · 2017-01-26 02:38:54Z

2

The problem is how you create the Node. In your case you create a local variable, which only exists within the scope of the function push(). You could use something like this.

void Stack::push(int val){
  Node* newNode = new Node;
  newNode->data = val;
  /* ... */ 
}

Edit: added a version of the stack (by no means complete)

#include <iostream>

struct Node{
  int data;
  Node* next;
};

class Stack {
  private:
    Node* head;
    int size;

  public:
    Stack();
    ~Stack();
    int getSize();
    void push(int val);
    int pop();
    void printStack();
};

Stack::Stack() : head(0), size(0)
{
}

Stack::~Stack(){
}

int Stack::getSize(){
  return size;
}

void Stack::push(int val){
  Node* newNode = new Node;
  newNode->data = val;
  newNode->next = head;

  head = newNode;
  size++;
}

int Stack::pop(){
    if(head != 0)
    {
        int val = head->data;

        Node* tmp = head;
        head = head->next;

        tmp->next = NULL;
        delete tmp;

        size--;

        return val;
    }
    else
    {
        return -1; // what happens if stack is empty ?      
    }
}

edited Jan 26, 2017 at 2:38

answered Jan 26, 2017 at 2:05

Shaana

3361 silver badge5 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

user3736114 Over a year ago

Thank you, will mark you as solution since you provided code to correct issue.

Tim Biegeleisen Over a year ago

I think there are other problems with the logic of push() and pop().

Remy Lebeau Over a year ago

The ~Stack() destructor needs to walk the list deleting any nodes that have not been popped yet, otherwise they will be leaked. You should also implement the Rule of three properly by adding a copy constructor and copy assignment operator

Shaana Over a year ago

I totally agree, but this is getting out of hands now. Just use std::stack if you want to do something real.

Sam Varshavchik · Accepted Answer · 2017-01-26 02:26:56Z

2

void Stack::push(int val){
  Node newNode;

newNode is declared to be a local object in automatic scope of the push() function.

Which means that when push() returns, this object is going to get automatically destroyed. That's what "automatic scope" means.

The code in push() attempts to insert this object into your stack, and assumes that this object will exist after push() returns. This, of course, isn't true, and this ends up corrupting memory, resulting in undefined behavior.

This is not how object lifetime and scope works, fundamentally, in C++.

edited Jan 26, 2017 at 2:26

answered Jan 26, 2017 at 2:06

Sam Varshavchik

119k6 gold badges109 silver badges164 bronze badges

Comments

Tim Biegeleisen · Accepted Answer · 2017-01-26 02:25:00Z

1

I think both your push() and pop() methods have problems. You can try using these versions:

// create new node, point it to current head, and then assign it as new head
void Stack::push(int val){
    Node* newNode = new Node;
    newNode->data = val;
    newNode->next = head;             // OK even if head == NULL
    head = newNode;
    size++;
}

// retrieve value from head (if it exists), pop the head and return the value
int Stack::pop(){
    if (head == NULL) return -1;     // -1 indicates empty stack
    int returnVal = head->data;      // get popped value
    Node* temp = &head;
    head = head->next;               // pop the top of the stack
    delete temp;
    size--;
    return returnVal;
}

edited Jan 26, 2017 at 2:25

answered Jan 26, 2017 at 2:07

Tim Biegeleisen

526k32 gold badges324 silver badges399 bronze badges

1 Comment

Sonalk Over a year ago

What is "head"? Is that the same thing as top?

templatetypedef · Accepted Answer · 2017-01-26 02:05:43Z

There's a problem in your code for push, actually:

void Stack::push(int val){
  Node newNode;
  newNode.data = val;
  if(size == 0) newNode.next = NULL;
  else newNode.next = head.next;
  head.next = &newNode;
  size++;
}

When you write

Node newNode;

you're declaring the Node object with automatic storage duration (you sometimes hear this called "on the stack"). This Node only exists as long as the push function is running, and as soon as the function returns the node ceases to exist. Trying to use that node later results in undefined behavior, which in practice could be anything from an outright crash to reading back garbage data.

To address this issue, you'll need to use dynamic allocation. Create the node using new Node and store a pointer to it. Objects created this way live until something explicitly destroys them, which means that they'll live after the push call finishes. You'll then need to adjust pop to deallocate the memory.

Collectives™ on Stack Overflow

C++ stack implementation pop function not working

4 Answers 4

4 Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related