CODEWITHSUNDEEP
c++listpointerslinked-liststack
Moriz Büsing
Moriz Büsing

Reputation: 367

C++ stack using linked lists

I'm trying to implement a simple stack using linked lists. When I run the code below, I get

6
<some random integer>

I've been looking for my mistake for hours now without success. I guess there is an uninitalized Variable somewhere, but I can't seem to find it.

#include <iostream>

using namespace std;

class node {
    public:
        node operator = (const node&);
        node(int d,node* n): data(d), prev(n) {}
        node(){}
        node* prev;
        int data;
};

node node::operator = (const node &n) {
    node r(n.data, n.prev);
    return r;
}

class stack {
    public:
        stack();
        void push(int);
        int pop();
        bool empty();
    private:
        node* top;
};

stack::stack() {
    top = 0;
}

bool stack::empty() {
    return top == 0;
}

void stack::push(int x) {
    node n(x,top);
    top = &n;
}

int stack::pop() {
    if (!empty()) {
        node r = *top;
        //cout << "r.data: " << r.data << endl;
        top = top->prev;
        return r.data;
    }
    else {
        cout << "Stack empty!" << endl;
        return 0;
    }
}

int main() {
    stack a;
    a.push(5);
    a.push(6);
    cout << a.pop() << endl;
    cout << a.pop() << endl;
}

Now the thing that totally confuses me, is that when I uncomment the line

        //cout << "r.data: " << r.data << endl;

for testing purposes, the output changes to

r.data: 6
6
r.data: 6
6

Why would that happen?

Upvotes: 0

Views: 3920

Answers (3)

netjeff
netjeff

Reputation: 8099

Unless this is a programming assignment for a class, use std::stack provided with STL.

Upvotes: 3

Mislav Blažević
Mislav Blažević

Reputation: 268

void stack::push(int x) {
    node n(x,top);
    top = &n;
}

Problem with this function is that n has automatic storage duration, and is destroyed after function returns.

Instead, use dynamic allocation:

node* n = new node(x, top);

Upvotes: 0

Some programmer dude
Some programmer dude

Reputation: 409136

This code is wrong:

void stack::push(int x) {
    node n(x,top);
    top = &n;
}

Here you create a local variable, and then set top to point to that. But when the function returns then the local variable does not exists any more, and top points to some memory that is not valid.

You need to create a new node on the heap with the new operator:

void stack::push(int x) {
    node* n = new node(x,top);
    top = n;
}

Of course, now you have to make sure the allocated nodes are free'd when your done. This should be done in a destructor in stack that pops all nodes, and in pop you need to use the delete operator to free the memory.

Upvotes: 5

Related Questions