How do I get this Linked List Stack implementation to run in C++?

user_16692672 0
Viewed 100

I am trying to implement a Stack using a Linked List in C++. When I run my code, nothing is outputted to the console, but it compiles without errors. The problem seems to come from my pointer for the top node. I initially made the top node without a pointer, but that created problems of its own when I tried to initialize it as NULL.

Code:

#include <iostream>
using namespace std;
class Stack{

    class Node{
        int data;
        Node* prev;
        public:
            Node(int x){
                data=x;
            }
            void set_prev(Node nd){
                *prev=nd;
            }
            Node get_prev(){
                return *prev;
            }
            int get_data(){
                return data;
            }
    };

    Node* top = NULL;
    int count = 0;

    public:
        void push(int x){
            Node new_node(x);
            new_node.set_prev(*top);
            *top = new_node;
            count++;
            cout << "Pushing" << endl;
        }
        void pop(){
            if(!is_empty()){
                int data = (*top).get_data();
                *top = (*top).get_prev();
                count--;
                cout << "Popping" << endl;
            }else{
                cout << "Stack is empty." << endl;
            }
            
        }
        int peek(){
            return (*top).get_data();
        }

        int get_count(){
            return count;
        }

        bool is_empty(){
            return !count;
        }

};

int main(){
    Stack stk;
    stk.push(5);
    stk.push(13);
    cout << stk.peek() << endl;
}
stack c++
1 Answers

There are multiple, fundamental errors in the shown code related to how pointers and objects work in C++. It's not just one issue or error, all of these issues must be fixed before it works correctly.

Node* prev;

This is a pointer member of the Node class. Before using an object referenced by a pointer, the pointer must be set to point to a valid object.

There's nothing in the shown code that appears to set prev to point to any valid Node object.

void set_prev(Node nd){
            *prev=nd;
}

This assigns one object to the object referenced by the prev pointer. The prev pointer has never been initialized to point any object, anywhere. Therefore its value is uninitialized, random garbage. Assigning to an object that's referenced by a pointer which is random, uninitialized garbage is undefined behavior, and a near guaranteed crash.

It is clear, from examining the rest of the code, that the intent here is to pass a pointer to another Node object, rather than a Node object itself; then set the prev pointer to the passed-in pointer value.

        Node new_node(x);
        new_node.set_prev(*top);

So, over here, set_prev() should be called with a pointer to a new_node, rather than passing (a copy of) it to set_prev(). However, the problems are far from over. new_node is an object that's declared in automatic scope. After this function returns, new_node gets destroyed. Any existing pointer to it now points to a destroyed, no-longer valid object, and dereferencing it further results in undefined behavior, and another, very likely crash.

It is clear, based on the context, that the intent here is to instantiate a new Node object in dynamic scope, using the new keyword. Consequently, pop() is expected to delete them, as well.

This kind of a homework assignment is traditionally given after introducing the concept of dynamic scope, and using new and delete to create objects in dynamic scope. You should review your class notes, or textbook material, for more information on this topic, and additional details on how to properly, and correctly, create and destroy objects; and proper use of pointers.

user_39433120
Related