Stack Data Structure [Learn C or C++]

Prev: Call For Manuscripts: International Journal of Signal Processing (IJSP)
Next: Test your C Skills

From: Pavel R. on 5 Mar 2010 10:55

I hope someone can resolve this. I've spent all morning trying to work
the problem out by I keep getting a seg. fault. I believe it has to do
in the pop function when I later try to pop them out.

If I only called top without ever calling pop, I will get the data
without any problems. If I call pop and then call top, then I get a
seg. fault.

Thanks

http://codepad.org/950oTNEQ

OR

#include <iostream>

class IntNode
{
public:
IntNode() {}
IntNode(int data, IntNode* link) : _data(data), _link(link) {}
IntNode* getLink() const { return _link; }
int getData () const { return _data; }
void setData(int & data) { _data = data; }
void setLink(IntNode * link) { _link = link; }
void addNode(int data)
{
setLink(new IntNode(data, NULL) );
}
void insert(IntNode* link, int & data) { link->setLink( new
IntNode(data, link->getLink()) ); }
IntNode* search(IntNode* head, int target)
{

IntNode* temp = head;

if(temp == NULL)
return NULL;
else
{
while(temp->getData() != target && temp->getLink() != NULL)
temp = temp->getLink();

if(temp->getData() == target)
return temp;
else
return NULL;
}
}

private:
int _data;
IntNode* _link;
};

class Stack
{
public:
Stack(){ head = new IntNode(0,NULL);}

void push(const int & X)
{
head->addNode(X);
}
int top ()
{
IntNode* t = head->getLink();
return t->getData();
}
void pop()
{
if( head->getLink() != NULL)
{
IntNode* t = head->getLink();
head->setLink(t->getLink());

delete t;
}

}
bool isEmpty(){ if(head->getLink() == NULL) return true; return
false; }
private:
IntNode* head;
};
int main()
{
Stack* st = new Stack;

st->push(5);
st->push(6);
st->push(7);
st->push(8);
for(int i = 0; i <= 3; i++)
{
std::cout << st->top() << " ";
// st->pop();
}
st->pop();
std::cout << st->top();
/* for(int i = 0; i <= 5; i++)
{
std::cout << st->top() << " ";
st->pop();
}*/

delete st;

return 0;
}

From: John H. on 5 Mar 2010 12:55

On Mar 5, 9:55 am, "Pavel R." <razor...(a)gmail.com> wrote:
> I hope someone can resolve this. I've spent all morning trying to work
> the problem out by I keep getting a seg. fault. I believe it has to do
> in the pop function when I later try to pop them out.
>
> If I only called top without ever calling pop, I will get the data
> without any problems. If I call pop and then call top, then I get a
> seg. fault.
>
> Thanks
>
> http://codepad.org/950oTNEQ
>
> OR
>
> #include <iostream>
>
> class IntNode
> {
> public:
> IntNode() {}
> IntNode(int data, IntNode* link) : _data(data), _link(link) {}
> IntNode* getLink() const { return _link; }
> int getData () const { return _data; }
> void setData(int & data) { _data = data; }
> void setLink(IntNode * link) { _link = link; }
> void addNode(int data)
> {
> setLink(new IntNode(data, NULL) );
> }
> void insert(IntNode* link, int & data) { link->setLink( new
> IntNode(data, link->getLink()) ); }
> IntNode* search(IntNode* head, int target)
> {
>
> IntNode* temp = head;
>
> if(temp == NULL)
> return NULL;
> else
> {
> while(temp->getData() != target && temp->getLink() != NULL)
> temp = temp->getLink();
>
> if(temp->getData() == target)
> return temp;
> else
> return NULL;
> }
> }
>
> private:
> int _data;
> IntNode* _link;
>
> };
>
> class Stack
> {
> public:
> Stack(){ head = new IntNode(0,NULL);}
>
> void push(const int & X)
> {
> head->addNode(X);
> }
> int top ()
> {
> IntNode* t = head->getLink();
> return t->getData();
> }
> void pop()
> {
> if( head->getLink() != NULL)
> {
> IntNode* t = head->getLink();
> head->setLink(t->getLink());
>
> delete t;
> }
>
> }
> bool isEmpty(){ if(head->getLink() == NULL) return true; return
> false; }
> private:
> IntNode* head;};
>
> int main()
> {
> Stack* st = new Stack;
>
> st->push(5);
> st->push(6);
> st->push(7);
> st->push(8);
> for(int i = 0; i <= 3; i++)
> {
> std::cout << st->top() << " ";
> // st->pop();
> }
> st->pop();
> std::cout << st->top();
> /* for(int i = 0; i <= 5; i++)
> {
> std::cout << st->top() << " ";
> st->pop();
> }*/
>
> delete st;
>
> return 0;
>
> }
>
>

It looks like you are trying to use the head as a way to keep track of
what node is on the top of the stack. Your push operation adds a node
to the top of the stack. It seems like you would have to update head
in someway to reflect that there is now a different node at the top of
the stack.

From: Paul Bibbings on 5 Mar 2010 16:46

"Pavel R." <razoredx(a)gmail.com> writes:

> I hope someone can resolve this. I've spent all morning trying to work
> the problem out by I keep getting a seg. fault. I believe it has to do
> in the pop function when I later try to pop them out.
>
> If I only called top without ever calling pop, I will get the data
> without any problems. If I call pop and then call top, then I get a
> seg. fault.

I haven't fully analysed your code, but it is easy to see where the
problem lies. You are using a linked list as your underlying stack
structure, but you are not maintaining your links! You should be able
to follow what is actually happening in your debugger.

Having built your code with gcc-4.4.3, stepping through it using gdb I
see the following:

21:20:50 Paul Bibbings(a)JIJOU
/cygdrive/d/CPPProjects/CLCPP $gdb stack_data_structure
(gdb) break stack_data_structure.cpp:74
Breakpoint 1 at 0x4010d5: file stack_data_structure.cpp, line 74.
(gdb) run
Starting program: /cygdrive/d/CPPProjects/CLCPP/stack_data_structure
[New Thread 17316.0x442c]
[New Thread 17316.0x45e8]

Breakpoint 1, main () at stack_data_structure.cpp:74
74 st->push(5);
(gdb) next
75 st->push(6);
(gdb) print *st->head->_link
$1 = {_data = 5, _link = 0x0} // #1
(gdb) next
76 st->push(7);
(gdb) print *st->head->_link
$2 = {_data = 6, _link = 0x0} // #2
(gdb) next ^^^
77 st->push(8);
(gdb) print *st->head->_link
$3 = {_data = 7, _link = 0x0} // #3
(gdb) next ^^^
78 for(int i = 0; i <= 3; i++)
(gdb) print *st->head->_link
$4 = {_data = 8, _link = 0x0} // #4
(gdb) ^^^

At line #1, in the debugger output above, we see the result of:

74 st->push(5)

We would expect the _link corresponding to the node to be NULL (0x0),
since this is the first element on the stack. However, at #2, after

75 st->push(6)

we find that the link for the second element added is *still* NULL
(0x0). The same pattern continues at #3 and #4. You are not linking
each node against the previous node, which is how a linked list works.
As you have it here, for each node added, all previously nodes are
simply lost and, aside from anything else, leaking memory.

> class IntNode
> {
> public:
> // ...
> void setLink(IntNode * link) { _link = link; }
> void addNode(int data)
> {
> setLink(new IntNode(data, NULL) );
> }
> };
>
> class Stack
> {
> public:
> // ...
> void push(const int & X)
> {
> head->addNode(X);
> }
> };

You can see the problem in your code here. Stack::push adds a new node
passing the data, calling IntNode::addNode(int). Inside
IntNode::addNode, however, you are consistently setting the _link for
the new IntNode to NULL. This is to miss the very purpose of a linked
list, which uses a node's _link member, upon being newly added to the
list, to maintain a pointer to the previously added node. In your code
you don't set this anywhere, and so you perpetually have a list of only
one referencable item and a lot of leaked memory.

It is no surprise, then, that after popping you end up with the head
referencing a NULL pointer, and then your next attempt - whatever it is
- to use this pointer in the belief that it actually points to
something, *this* leads to the segfault.

In short, you will need to ocus on a strategy for maintaining the list
correctly.

Hope this helps.

Regards

Paul Bibbings

From: Paul Bibbings on 5 Mar 2010 18:56

"Pavel R." <razoredx(a)gmail.com> writes:

> I hope someone can resolve this. I've spent all morning trying to work
> the problem out by I keep getting a seg. fault. I believe it has to do
> in the pop function when I later try to pop them out.
>
> If I only called top without ever calling pop, I will get the data
> without any problems. If I call pop and then call top, then I get a
> seg. fault.
>

After my previous post I did have another look at your code, to see what
little could be changed to get it working. Below is a rough-and-ready
repair, without any consideration as to whether or not the overall
design/strategy is a good one or otherwise. You'll see that the changes
are actually few, but I thought it might help you to get a clearer
picture of what was failuring in the code as you posted it. Comments
afterwards.

>
> #include <iostream>
>
> class IntNode
> {
> public:
> IntNode() {}
> IntNode(int data, IntNode* link) : _data(data), _link(link) {}
> IntNode* getLink() const { return _link; }
> int getData () const { return _data; }
> void setData(int & data) { _data = data; }

void addLink(IntNode * link) { //
link->_link = _link; // Added
setLink(link); //
} //

> void setLink(IntNode * link) { _link = link; }
> void addNode(int data)
> {
> addLink(new IntNode(data, NULL) ); // Changed setLink -> addLink
> }
> void insert(IntNode* link, int & data) {
> link->setLink( new IntNode(data, link->getLink()) );
> }
> IntNode* search(IntNode* head, int target)
> {
> IntNode* temp = head;
>
> if(temp == NULL)
> return NULL;
> else
> {
> while(temp->getData() != target && temp->getLink() != NULL)
> temp = temp->getLink();
>
> if(temp->getData() == target)
> return temp;
> else
> return NULL;
> }
> }
>
> private:
> int _data;
> IntNode* _link;
> };
>
> class Stack
> {
> public:
> Stack(){ head = new IntNode(0,NULL);}
>
> void push(const int & X)
> {
> head->addNode(X);
> }
> int top ()
> {
> IntNode* t = head->getLink();
> return t->getData();
> }
> void pop()
> {
> if( head->getLink() != NULL)
> {
> IntNode* t = head->getLink();
> head->setLink(t->getLink());
>
> delete t;
> }
>
> }
> bool isEmpty(){
> if(head->getLink() == NULL) return true;
> return false;
> }
> private:
> IntNode* head;
> };
>
> int main()
> {
> Stack* st = new Stack;
>
> st->push(5);
> st->push(6);
> st->push(7);
> st->push(8);
> for(int i = 0; i <= 3; i++)
> {
> std::cout << st->top() << " ";
> st->pop();
> }
> st->pop(); // safe, but doesn't do anything
> // std::cout << st->top(); // dangerous: no top!
> /* for(int i = 0; i <= 5; i++)
> {
> std::cout << st->top() << " ";
> st->pop();
> }*/
>
> delete st;
>
> return 0;
> }

You'll see that I've added an extra method to your IntNode class -
IntNode::addLink. Ordinarily I might have wanted to merely modify your
existing IntNode::setLink method, but the problem with this is that,
while the call from your original IntNode::addNode requires this extra
functionality, the method is also used within your implementation of
Stack::pop which, as it stands, requires setLink to be implemented just
as you have it - in this instance no new node is being added. With more
consideration it might be possible to factor out the need for this extra
method with suitable modifications elsewhere but, as I've said, this is
just a quick repair.

Having added this new method I've merely needed to change the call in
IntNode::addNode from setLink to addLink and everything seems to work
for the code as you exercise it in main. (What I haven't checked for is
whether it breaks other code that you haven't used in your example, such
as IntNode::insert, which will probably need some consideration of its
own.)

Finally, I've commented out one line in main since, under any
circumstances, you are here trying to dereference the top element when
there are no longer any elements left to access, all of them having been
popped.

22:36:11 Paul Bibbings(a)JIJOU
/cygdrive/d/CPPProjects/CLCPP $g++ -o stack_data_structure stack_data_structure.cpp

22:37:33 Paul Bibbings(a)JIJOU
/cygdrive/d/CPPProjects/CLCPP $./stack_data_structure
8 7 6 5

Regards

Paul Bibbings

From: Helge Kruse on 6 Mar 2010 04:08

Am 06.03.2010 00:56, schrieb Paul Bibbings:
> You'll see that I've added an extra method to your IntNode class -
> IntNode::addLink. Ordinarily I might have wanted to merely modify your
> existing IntNode::setLink method, but the problem with this is that,
> while the call from your original IntNode::addNode requires this extra
> functionality, the method is also used within your implementation of
> Stack::pop which, as it stands, requires setLink to be implemented just
> as you have it - in this instance no new node is being added. With more
> consideration it might be possible to factor out the need for this extra
> method with suitable modifications elsewhere but, as I've said, this is
> just a quick repair.

You dont need to change setLink. The addNode method can be modified to
achieve the stack functionality:

void addNode(int data)
{
// setLink(new IntNode(data, NULL) );
setLink(new IntNode(data, _link) );
}

The member _link is NULL when the stack is empty as defined in Stack
constructor.

The main function now works with the pop operations:

for(int i = 0; i <= 3; i++)
{
std::cout << st->top() << " ";
st->pop();
}

Even the pop method is save for calling with empty stack:

st->pop();

But you get an exception when you try to get the TOS of an empty stack:

std::cout << st->top();

You will have to define the behavior of the stack class for this
situation. Probably the exception is by design, but you can also throw a
special exception like this:

int top ()
{
if (head->getLink() == NULL)
{
throw StackUnderflowException;
}
IntNode* t = head->getLink();
return t->getData();
}

Regards,
Helge

| Next | Last
Pages: 1 2
Prev: Call For Manuscripts: International Journal of Signal Processing (IJSP)
Next: Test your C Skills