Thread: Custom stack problems

  1. #1
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    169

    Custom stack problems

    Since a lot of people have been posting about Linked Lists and Stacks and Queues recently, I thought of paying visit to one of my old Stack programs (I have three more for Queues, Circular Queues and Trees). There seems to be some error with the DisplayStack () method. Everything looks fine to me but when I run the code, it crashes. If I comment out the call to DisplayStack, everything works well. I haven't looked at the code in quite sometime and nothing makes sense right now as it's pretty late here (5 am) and I need to hit the bed for a few hours. Hopefully, someone will be able to figure it out and I wouldn't need to think about this when I wake up.

    Code:
    template <typename T>
    class Stack
    {
    private:
    
        struct Object
        {
            T Data; Object* Next;
    
            Object (void)
                : Data (T()) ,
                  Next (nullptr)
            { }
        };
    
        Object* StackTop;
    
    public:
    
         Stack (void);
        ~Stack (void);
    
        void Push(T const& data);
    
        void Pop          (void)      ;
        void DisplayStack (void) const;
    
    };
    
    template <typename T> Stack<T>::Stack (void)
        : StackTop (nullptr)
    { }
    
    template <typename T> void Stack<T>::Push (T const& data)
    {
        Object* ptr = new Object; ptr->Data = data;
    
        if (StackTop == nullptr) StackTop = ptr;
    
        else
        {
            ptr->Next = StackTop;
            StackTop = ptr;
        }
    }
    
    template <typename T> void Stack<T>::Pop (void)
    {
        Object* temp = StackTop;
        StackTop = StackTop->Next;
        delete temp;
    }
    
    template <typename T> void Stack<T>::DisplayStack (void) const
    {
        Object* temp = StackTop;
    
        std::cout << std::endl << temp->Data << "<- Stack Top";
    
        while (temp != nullptr)
        {
            temp = temp->Next;
            std::cout << std::endl << temp->Data;
        }
    }
    
    template <typename T> Stack<T>::~Stack (void)
    {
        Object* temp = StackTop;
    
        while (temp != nullptr)
        {
            StackTop = StackTop->Next;
            delete temp;
            temp = StackTop;
        }
    }
    
    int main (void)
    {
        Stack <std::string> S;
    
        S.Push ("ABCD");
        S.Push ("EFGH");
        S.Push ("IJKL");
        S.Push ("MNOP");
    
        S.DisplayStack ();
    
        return 0;
    }
    There's a tonne more of other methods and operator overloads but I'm not adding all of them as thry were working pretty much fine the last time I ran it. Thanks, 'night.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,234
    * post moved to C++ programming forum *

    Zeus_: don't hijack other people's posts, and don't ask for help on a C++ program in the C programming forum.
    Last edited by laserlight; 4 Days Ago at 06:17 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Dec 2017
    Posts
    694
    You dereference the pointer before you check if it's null.

    BTW, don't put "void" in the parameters when a function takes nothing. Just leave the parentheses empty. In old C you had to do that, but you don't have to do that in C++.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,234
    Quote Originally Posted by Zeus_
    There seems to be some error with the DisplayStack () method.
    There are two oversights that I can see at a glance:
    • It assumes that the stack is not empty.
    • In the loop, it doesn't check that the node pointer is a null pointer before dereferencing it.


    A few other issues:
    • You unnecessarily require T to have a default constructor. If you had written Object's constructor to copy instead, T would not need a default constructor (although it would need a copy constructor). Personally, I would have named Object Node instead, since you're basically implementing the stack with a linked list. Actually, if Object's constructor were to also take the next pointer as an argument, you could implement Push in a single line:
      Code:
      template <typename T> void Stack<T>::Push (T const& data)
      {
          StackTop = new Object(data, StackTop);
      }
    • You might have merely omitted them, but you should also implement or disable the copy constructor and copy assignment operator, and it makes sense to implement the move constructor and move assignment operator.
    • Pop results in undefined behaviour if the stack is empty. If that is by design, then it is better to document it, either with an assertion or at least a comment. Otherwise, it should either throw an exception or be a no-op.
    • You might have merely omitted it, but you're using the version of Pop that just pops without returning the item. Therefore, you need some other way for the stack user to examine the top of the stack.


    It probably would also make sense to rename DisplayStack to just Display since it is clear that you're displaying a stack. Or maybe overload operator<< for ostream since this is kind of canonical debugging output.
    Last edited by laserlight; 4 Days Ago at 07:03 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    169
    There are two oversights that I can see at a glance:

    • It assumes that the stack is not empty.
    • In the loop, it doesn't check that the node pointer is a null pointer before dereferencing it.
    Yea..... I don't know why I never did that in any of my programs when I first wrote them, but I'll change them to not assume that the Stack/Queue/Tree/CircQueue is not empty. Actually, when I started reading about all the Object Oriented Programming Paradigms and stuff, I thought it'd be a good idea to implement everything in the OOP way and those were some of the primary programs I wrote for practice.

    You unnecessarily require T to have a default constructor. If you had written Object's constructor to copy instead, T would not need a default constructor (although it would need a copy constructor). Personally, I would have named Object Node instead, since you're basically implementing the stack with a linked list. Actually, if Object's constructor were to also take the next pointer as an argument, you could implement Push in a single line:
    Makes sense, I think I'll change the implementation to do exactly that.

    You might have merely omitted them, but you should also implement or disable the copy constructor and copy assignment operator, and it makes sense to implement the move constructor and move assignment operator.
    I had no idea what a move constructor was when I wrote the program, so I need to revisit my codes and change a few things. I have implemented the copy constructor and copy assignment operator which, now, seems like a really bad idea lol. Will implement the changes....

    Pop results in undefined behaviour if the stack is empty. If that is by design, then it is better to document it, either with an assertion or at least a comment. Otherwise, it should either throw an exception or be a no-op.
    Oh, yep, I'll fix that first as soon as I reach home. I'm starting to wonder all the changes I need to do in my other programs too, which I thought were working properly but I forgot implementing the edge case scenarios, and probably much more.

    You might have merely omitted it, but you're using the version of Pop that just pops without returning the item. Therefore, you need some other way for the stack user to examine the top of the stack.
    I've overloaded the [] operator to do just that.

    It probably would also make sense to rename DisplayStack to just Display since it is clear that you're displaying a stack. Or maybe overload operator<< for ostream since this is kind of canonical debugging output.
    Will do.

    You dereference the pointer before you check if it's null.

    BTW, don't put "void" in the parameters when a function takes nothing. Just leave the parentheses empty. In old C you had to do that, but you don't have to do that in C++.
    I think I need to rewrite all my programs (using Linked Lists) for the stupid negligence I showed when writing these. I'll implement the changes.

    Old habits die hard, I'm used to all the (void) in parentheses because our school teaches us on TurboC++ and they say you must specify it. I think I should suggest them to join this forum as @Salem suggested on the C Programming thread that's hot right now for Stack implementation. They're just teaching a bunch of old (some of which are bad) programming habits. Won't make a difference after a month because the next year batch have Python and Java as choices. C/C++ is not going to be taught any more and we were the last batch learning it.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using stack of stl with custom container.
    By +Azazel+ in forum C++ Programming
    Replies: 1
    Last Post: 09-15-2009, 10:29 AM
  2. Problems with a custom-made class
    By Kylecito in forum C++ Programming
    Replies: 9
    Last Post: 02-06-2006, 01:35 PM
  3. Problems with my custom string class
    By cunnus88 in forum C++ Programming
    Replies: 15
    Last Post: 11-15-2005, 08:21 PM
  4. problems overloading outstream for custom ADT
    By aciarlillo in forum C++ Programming
    Replies: 4
    Last Post: 04-05-2005, 09:28 AM
  5. [Linked Lists] Custom String Class Add Char problems
    By nickname_changed in forum C++ Programming
    Replies: 1
    Last Post: 07-23-2004, 10:15 PM