Thread: 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.

* 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.

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++.

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.

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.

This is my operator overload for retrieving the element data of the i'th element. It's probably very inefficient for accessing the millionth element or something like that. What do you guys think I should be returning if the call to Size () returns 0 in an if statement (Size is a function that returns the number of nodes)? Because if the Stack has no elements and I type something like "cout << S [0]", this code will crash. I don't want it to crash when I write code like that (in all Data Structure programs I've written). I can check if the number of nodes is 0 and if it is zero, what should I be returning for it to work fine but not display anything as expected?

Code:

template <typename T> T& Stack<T>::operator [] (int Position) const
{
    ObjectNode* CurrentNode = Top;

    if (Position < 0) Position = 0;
    else if (Position > (int)Nodes - 1) Position = (int)Nodes - 1;
    for (int i = 0; i < Position; i++)
        CurrentNode = CurrentNode->Next;
    return CurrentNode->Data;
}

EDIT:

Changed code to this so that -ve indices work differently (returning reverse order of stack elements)

Code:

template <typename T> T& Stack<T>::operator [] (int Position) const
{
    ObjectNode* CurrentNode = Top;

    if (Position < 0) Position = (1 - Position > Nodes) ? 0 : (Nodes + Position);
    else if (Position > (int)Nodes - 1) Position = (int)Nodes - 1;
    for (int i = 0; i < Position; i++)
        CurrentNode = CurrentNode->Next;
    return CurrentNode->Data;
}

Originally Posted by Zeus_

This is my operator overload for retrieving the element data of the i'th element. It's probably very inefficient for accessing the millionth element or something like that.

That probably makes it a bad idea: C++ programmers are likely primed to expect operator[] to have random (constant time) access for an index and at least logarithmic time access otherwise (e.g., std::map). Linear time complexity could result in people accidentally coming up with a quadratic time algorithm to say, examine all the stack elements in turn. A solution could be to provide begin() and end() iterators instead.

Alternatively, there's the argument that a stack conceptually only ever allows you to access the top of the stack, so perhaps you should not provide this at all, like std::stack.

Yeah, I figured. It's a bad idea. I'm modifying all my programs so that I can use them instead of the STL for practicing purposes and hobby projects. Thought it'd be a good idea to overload [] (I should probably make it a const reference return so that the data in the stack cannot be manipulated) but then the complexity is O(n) which just makes it worse for the hobby projects I have in mind. I'll add the begin () and end () iterators too when I find the time to code again (not a lot of time these days due to exams). I've added the move constructor and move assignment operator but should I remove the copy ctor and assignment operator or let that stay?

This is the code I've got till now.

TODO:
- Remove Copy Ctor and Copy Assignment Operator once I know the reason why it's bad (I'm taking a few random guesses but I'm definitely sure)
- Modify Clear () to use Disabled Nodes instead of de-allocating previously allocated memory. DisabledNodes will be all the ActiveNodes before call to Clear ().
- Add Top () iterator that returns a read (not write because you should be able to manipulate the stack only through push and pop) pointer pointing to the top of the stack initially. What should be my return type for a Top () iterator? I cannot make it const ObjectNode* because apart from my Stack nothing else knows what an ObjectNode is or am I wrong?
- Update and upload code for all other data structures and have them examined by you guys...
- Make a Parentheses Validator using this Stack

Are my move ctor and assignment operator written correctly? Same question for the copy ctor and assignment. Also, what else should I be adding that you guys think would be good?

Code:

template <typename T> class Stack
{
private:

    struct ObjectNode
    {
        T Data; ObjectNode* Next;

        ObjectNode (T const& data , ObjectNode* next)
            : Data (data) ,
              Next (next)
        { }
    };

    size_t ActiveNodes;
    //size_t DisabledNodes;
    ObjectNode* StackTop;

public:

     Stack (void);
     Stack (const Stack& Other);
     Stack (Stack&& Other);
    ~Stack (void);

    Stack& operator = (const Stack& Other);
    Stack& operator = (Stack&& Other);

    void Clear   (void);
    void Display (void) const;
    void Pop     (void);
    void Push    (const T& data);

    bool Empty (void) const;

    size_t Size (void) const;

    const T& At          (int Position) const;
    const T& operator [] (int Position) const;
};

template <typename T> Stack <T>::Stack (void)
    : ActiveNodes (0) ,
      StackTop (nullptr)
{ }

template <typename T> Stack <T>::Stack (const Stack& Other)
    : ActiveNodes (Other.ActiveNodes) ,
      StackTop (Other.StackTop)
{
    ObjectNode* CurrentNode = StackTop;
    ObjectNode* OtherCurrentNode = Other.StackTop;

    for (size_t i = 0; i < ActiveNodes; i++)
    {
        CurrentNode->Data = OtherCurrentNode->Data;
        CurrentNode->Next = OtherCurrentNode->Next;
        CurrentNode = CurrentNode->Next;
        OtherCurrentNode = OtherCurrentNode->Next;
    }
}

template <typename T> Stack <T>::Stack (Stack&& Other)
    : ActiveNodes (Other.ActiveNodes) ,
      StackTop (Other.StackTop)
{
    Other.ActiveNodes = 0;
    Other.StackTop = nullptr;
}

template <typename T> Stack <T>::~Stack (void)
{
    ObjectNode* CurrentNode = StackTop;

    while (CurrentNode != nullptr)
    {
        StackTop = StackTop->Next;
        delete CurrentNode;
        CurrentNode = StackTop;
    }
}

template <typename T> Stack <T>& Stack <T>::operator = (const Stack& Other)
{
    if (this != &Other)
    {
        ObjectNode* CurrentNode = StackTop;
        while (CurrentNode != nullptr)
        {
            StackTop = StackTop->Next;
            delete CurrentNode;
            CurrentNode = StackTop;
        }

        ActiveNodes = Other.ActiveNodes;
        StackTop = Other.StackTop;

        CurrentNode = StackTop;
        ObjectNode* OtherCurrentNode = Other.StackTop;

        for (size_t i = 0; i < ActiveNodes; i++)
        {
            CurrentNode->Data = OtherCurrentNode->Data;
            CurrentNode->Next = OtherCurrentNode->Next;
            CurrentNode = CurrentNode->Next;
            OtherCurrentNode = OtherCurrentNode->Next;
        }
    }
    return *this;
}

template <typename T> Stack <T>& Stack <T>::operator = (Stack&& Other)
{
    if (this != &Other)
    {
        ObjectNode* CurrentNode = StackTop;
        while (CurrentNode != nullptr)
        {
            StackTop = StackTop->Next;
            delete CurrentNode;
            CurrentNode = StackTop;
        }

        StackTop = Other.StackTop;
        ActiveNodes = Other.ActiveNodes;

        Other.ActiveNodes = 0;
        Other.StackTop = nullptr;
    }

    return *this;
}

template <typename T> void Stack <T>::Clear (void)
{
    ObjectNode* CurrentNode = StackTop;

    while (CurrentNode != nullptr)
    {
        StackTop = StackTop->Next;
        delete CurrentNode;
        CurrentNode = StackTop;
    }

    ActiveNodes = 0;
}

template <typename T> void Stack <T>::Display (void) const
{
    if (ActiveNodes == 0) return;

    ObjectNode* CurrentNode = StackTop;

    for (size_t i = 0; i < ActiveNodes; i++)
    {
        std::cout << std::endl << CurrentNode->Data;
        CurrentNode = CurrentNode->Next;
    }
}

template <typename T> void Stack <T>::Push (const T& data)
{
    StackTop = new ObjectNode (data , StackTop);
    ActiveNodes++;
}

template <typename T> void Stack <T>::Pop (void)
{
    if (ActiveNodes == 0) return;

    ObjectNode* CurretNode = StackTop;
    StackTop = StackTop->Next;
    delete CurretNode;
    ActiveNodes--;
}

template <typename T> size_t Stack <T>::Size (void) const
{ return ActiveNodes; }

template <typename T> bool Stack <T>::Empty (void) const
{ return (ActiveNodes > 0) ? false : true; }

template <typename T> const T& Stack <T>::At (int Position) const
{ return operator [] (Position); }

template <typename T> const T& Stack <T>::operator [] (int Position) const
{
    ObjectNode* CurrentNode = StackTop;

         if (Position < 0) Position = (1 - Position > (int)ActiveNodes) ? 0 : ((int)ActiveNodes + Position);
    else if (Position > (int)ActiveNodes - 1) Position = (int)ActiveNodes - 1;

    for (int i = 0; i < Position; i++)
        CurrentNode = CurrentNode->Next;
    return CurrentNode->Data;
}

Originally Posted by Zeus_

- Remove Copy Ctor and Copy Assignment Operator once I know the reason why it's bad (I'm taking a few random guesses but I'm definitely sure)

You don't need to remove them. Just because they might be relatively expensive doesn't mean no one will ever really want a copy.

Originally Posted by Zeus_

- Add Top () iterator that returns a read (not write because you should be able to manipulate the stack only through push and pop) pointer pointing to the top of the stack initially. What should be my return type for a Top () iterator? I cannot make it const ObjectNode* because apart from my Stack nothing else knows what an ObjectNode is or am I wrong?

Just return a const T&. There's no point returning an iterator unless you actually want to allow the caller to iterate, but if so you need to designate an end iterator.

Originally Posted by Zeus_

Are my move ctor and assignment operator written correctly?

Yes.

Originally Posted by Zeus_

Same question for the copy ctor and assignment.

Your copy constructor looks wrong: you cannot just copy over the StackTop pointer; you need to create a copy of the other stack, and that means using new in a loop to create the node copies and append them to a fresh linked list.

Your copy assignment operator has the same problem. After you fix it, note that your copy assignment would then only offer the basic exception guarantee: the stack will be in a valid state after the exception is thrown, but the data before the copy assignment attempt would be lost. If you want to offer the strong exception guarantee (an exception would not result in a change to the original state), then you need to copy before you destroy. It looks like this can be solved by using the copy constructor to make a local copy, then using move assignment... but it would be more efficient to stick to offering the basic exception guarantee and just reuse the storage for the nodes already allocated to copy over, and only allocate new storage when the other stack is larger.

Yep, I see the problem with the copy ctor and assignment operator now when I test it. Right now, it's pretty much doing what a typedef would do i.e. creating an alias. I'll fix that. Thanks for your input!

> Just return a const T&. There's no point returning an iterator unless you actually want to allow the caller to iterate, but if so you need to designate an end iterator.

Makes sense. Thinking of it, why would someone want to iterate over a stack anyway? Defeats the purpose of it being a stack. Plus, if you do need to access the i'th element there's the [] but no sensible programmer would use a stack as something like a vector, even though I've added that functionality for a O(n) expense.

How is the [] overloaded in the vector class in the STL? Is it similar to my implementation? (In it's implementation, it probably too is using linked lists right?) I could look at the header files and try and figure this out myself but my mom'll kill me if she doesn't find me studying my core subjects and so I need to wait until later at night when she's asleep.

Also, I think I'll add a try and catch block in [] overload and Push () to throw an exception if StackTop == nullptr.

Changed the code to this but realised midway that this would reverse the order of the Stack. Then thought, I could exploit my [] overload to push Other in reverse order so I can get it to be what is expected but that's just too much burden for a copy ctor (the O(n**2), I guess, for just making a copy of the stack!)
I think I'll have to add another characteristic to ObjectNode so that each node can hold the previous stack node address too so that I can reverse iterate to get copy to work in O(n) time. Will that be good enough for a hobby stack project or is it just overkill?

Code:

template <typename T> Stack <T>::Stack (const Stack& Other)
    : ActiveNodes (0) ,
      StackTop (nullptr)
{
    ObjectNode* OtherCurrentNode = Other.StackTop;

    for (size_t i = 0; i < Other.ActiveNodes; i++)
    {
        this->Push (OtherCurrentNode->Data);
        OtherCurrentNode = OtherCurrentNode->Next;
    }
}

Thanks

Originally Posted by Zeus_

How is the [] overloaded in the vector class in the STL?

That is, by definition, dependent on the implementation

But in practice, it probably essentially looks like this:

Code:

return data[index];

Originally Posted by Zeus_

Is it similar to my implementation? (In it's implementation, it probably too is using linked lists right?)

std::vector models a dynamic array; it is therefore very different from a linked list. std::vector's operator[] has random access, just like an array. A linked list trying to implement operator[] to allow indexed access to its elements can never have random access because traversing to the middle of a linked list must surely take linear time, hence a stack implemented with a linked list that offers operator[] suffers from the same problem.

Originally Posted by Zeus_

Changed the code to this but realised midway that this would reverse the order of the Stack. Then thought, I could exploit my [] overload to push Other in reverse order so I can get it to be what is expected but that's just too much burden for a copy ctor (the O(n**2), I guess, for just making a copy of the stack!)

Yes, and that goes back to why operator[] is a bad idea: you're tempted by this operator[] overload even though you know it's inefficient.

Originally Posted by Zeus_

I think I'll have to add another characteristic to ObjectNode so that each node can hold the previous stack node address too so that I can reverse iterate to get copy to work in O(n) time. Will that be good enough for a hobby stack project or is it just overkill?

Basically, you want to implement your stack with a doubly linked list just so that copying can be efficient. That's overkill. You just need to keep track of the previous node when creating the copy of the linked list such that you can set the next pointer of the previous node to point to the current node.

Thanks for all the help!