Stack Data Structure

[volk]

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;
}

 

[John H.]

I hope someone can resolve this.

Have you considered std::stack for your needs?
http://www.sgi.com/tech/stl/stack.html

 

[LR]

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.

#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-
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);

I suggest that you use this function or one like it,

void dump(IntNode *p) {
std::cout << "start" << std::endl;
while(p) {
std::cout
<< p << ", "
<< p->getData() << ", "
<< p->getLink() << std::endl;
p = p->getLink();
}
std::cout << "end" << std::endl;
}

and create a member of your Stack class similar to this,
void Stack::dump() const {
::dump(head);
}

and call this member after you construct the stack and after each call
to Stack:ush.

LR

 

[Eric Pruneau]

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) );
}

addNode will work only if you add at the end of the list (which mean that
_link == NULL).
if _link != NULL when calling addNode, you have a memory leak.

void insert(IntNode* link, int & data) { link-
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;

You should call the variable _link "next". I assume you want it to be the
pointer to the next element of your list.

};

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

When this constructor is called, it push the value 0 in your stack. Head
should be NULL for an empty stack.

void push(const int & X)
{
head->addNode(X);
}

Here is your biggest problem. Every time you try to add an element to your
stack, you add an element directly after the head. So there is no way your
list can actually contain more than 2 elements. Push should insert a new
element before the head and the new element will be the new head.

void push(const int & X)
{
if(head == NULL)
{
... // special case when the list is empty. I let you figure this
one out!
return;
}
IntNode* t = head;
head = new IntNode(X,t); // your new head now points to your old head
}

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

This doesn't return the top, it returns the element after the head. It
should returns the head

void pop()
{
if( head->getLink() != NULL)
{
IntNode* t = head->getLink();
head->setLink(t->getLink());

delete t;
}

}

This doesn't delete the top element, it deletes the element after the head.
It should deletes the head

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

int main()
{
Stack* st = new Stack;

With your current code, this actually create a stack with the element 0 in
it

st->push(5); 5 is pushed after 0
st->push(6);

6 is also pushed after 0 and memory for 5 is lost forever... your list has 2
elements

st->push(7);

7 is stillpushed after 0 and memory for 6 is lost forever... your list still
has 2 elements

st->push(8);

Guess what? 8 is pushed after 0 and I guess you won't be surprised if I tell
you that your list is still 2 element long...

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

this pop will delete 8, now your stack size is 1

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

your top function try to return the second element, which has just been
deleted... KABOOM!!! Here is your seg fault

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

delete st;

return 0;
}

If I had to use a stack, I would use std::stack. But if you really want to
implement a linked list based stack, I suggest something like that:

Note that you should do some error checking
class stack
{
public:
stack() : head(NULL){}
~stack() { // delete all the elements here ... }
void push(int X) { // allocate a Node which will be your new head and
don't forget to set the next pointer to the old head }
void pop() { Node* t = head->next; delete head; head = t; } // add error
check here... what if the stack is empty
int top() { return head->value; } // what if the stack is empty.....

private:
struct Node {
int value;
Node* next;
};

Node* head;
};

Much more simple like that!!!

Well, the best thing here is to do a template. That way the node value could
be anything you want.


Eric Pruneau

 

[Jorgen Grahn]

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

Some things which annoy me in old C++ code, and which I never want to
see again:

class Stack
{ ....
bool isEmpty(){ if(head->getLink() == NULL) return

Const missing!

int main()
{
Stack* st = new Stack;

Why a new here? Why not just put it on the stack?

/Jorgen

 

[red floyd]

Some things which annoy me in old C++ code, and which I never want to
see again:




Const missing!


Why a new here?  Why not just put it on the stack?

Too much Java in his past?

 

[cout_iWin]

I was thinking that a stack isn't very different from a vector. it will also allow random access inside the array, while still allowing to to add/remove from the end. I am new to c++ but fundamentally it seems that a vector IS a stack.