implementing stack

[Ben]

Hi all,

I implemented a stack in C++ in 2 different ways and I'd like to know
which approach is better than the other.. and if there is any
difference between the two? I'd also like to know if the destructor
i'm using is correct.. I got segmentation fault in my second approach
while I quit the program. I appreciate any help....

My first appoach goes like this:

/* List struct */
typedef struct list {
int data;
list *next;
list *prev;
} list;

/* Stack class */
class dynamic_stack {
list *head;
list *tail;
list *cur;
int NumNodes;

public:
dynamic_stack() {
head = tail = cur = NULL;
NumNodes = 0;
}
~dynamic_stack() {
delete head; delete tail; delete cur;
NumNodes = 0;
}
void push(int);
void pop();
void print();
};

My second approach is without the struct:

/* Stack class */
class dynamic_stack {
dynamic_stack *head;
dynamic_stack *tail;
dynamic_stack *cur;
int NumNodes;
int data;
dynamic_stack *next;
dynamic_stack *prev;

public:
dynamic_stack();
~dynamic_stack() {
delete head; delete tail; delete cur;
NumNodes=data=0;
delete next; delete prev;
}
void push(int);
void pop();
void print();
};

Thanks a lot!
Ben

 

[Rolf Magnus]

Hi all,

I implemented a stack in C++ in 2 different ways and I'd like to know
which approach is better than the other.. and if there is any
difference between the two? I'd also like to know if the destructor
i'm using is correct.. I got segmentation fault in my second approach
while I quit the program. I appreciate any help....

My first appoach goes like this:

/* List struct */
typedef struct list {
int data;
list *next;
list *prev;
} list;

Leave out the typedef. It's not needed. I'd also rather name it "node"
or something instead of list, because it isn't a list, but rather only
one node of it.

struct node {
int data;
node* next;
node* prev;
};

/* Stack class */
class dynamic_stack {
list *head;
list *tail;
list *cur;
int NumNodes;

public:
dynamic_stack() {
head = tail = cur = NULL;
NumNodes = 0;
}

It's good habit to prefer initialization over assignment. So this should
look like:

dynamic_stack()
: head(0),
tail(0),
cur(0),
NumNodes(0)
{}

~dynamic_stack() {
delete head; delete tail; delete cur;
NumNodes = 0;

Setting NumNodes to 0 is not really needed here, because the object
won't exist anymore after the destructor finished.

}
void push(int);
void pop();
void print();
};

My second approach is without the struct:

/* Stack class */
class dynamic_stack {
dynamic_stack *head;
dynamic_stack *tail;
dynamic_stack *cur;
int NumNodes;
int data;
dynamic_stack *next;
dynamic_stack *prev;

public:
dynamic_stack();
~dynamic_stack() {
delete head; delete tail; delete cur;
NumNodes=data=0;
delete next; delete prev;
}
void push(int);
void pop();
void print();
};

Thanks a lot!

I'd prefer the one with the struct. You could put that struct into the
private section of class dynamic_stack.

 

[Siemel Naran]

My first appoach goes like this:

/* List struct */
typedef struct list {
int data;
list *next;
list *prev;
} list;

/* Stack class */
class dynamic_stack {
list *head;
list *tail;
list *cur;
int NumNodes;

public:
dynamic_stack() {
head = tail = cur = NULL;
NumNodes = 0;
}
~dynamic_stack() {
delete head; delete tail; delete cur;
NumNodes = 0;
}

Why are there 3 nodes (head, tail, cur)? In the destructor, you delete only
3 nodes, so is there a memory leak? Plus, what happens for a stack of 1
element; do you delete the same node twice?

My second approach is without the struct:

/* Stack class */
class dynamic_stack {
dynamic_stack *head;
dynamic_stack *tail;
dynamic_stack *cur;
int NumNodes;
int data;
dynamic_stack *next;
dynamic_stack *prev;

public:
dynamic_stack();
~dynamic_stack() {
delete head; delete tail; delete cur;
NumNodes=data=0;
delete next; delete prev;
}
void push(int);
void pop();
void print();
};

The reason for the crash is probably because the destructor deletes the same
node twice. But again you seem to have a memory leak as you delete at most
5 nodes.

The first way seems better to me as you can implement a generic double
linked list, and then adapt this to the interface of a stack. So it's two
for the price of one .


Note in the standard you can use

std::stack<int> stack1;
std::stack<int, std::deque<int> > stack2;
stack1 = stack2; // OK, same type
std::stack<int, std::list<int> > stack3;

 

[Dave Townsend]

Ben, the destructors in both don't seem to be right, I would expect
to see a loop to visit all the list-nodes and delete each of them.
I'm also a bit suspicious of what happens when you have 1 or 2
items in the list, it looks to me that head and tail might be deleted
twice, what about cur too?

You have a pop() operation, but there's no way to get the value of
the top of the stack, such as int top().

 

[Ben]

I'd prefer the one with the struct. You could put that struct into the
private section of class dynamic_stack.

why is the first approach (with struct) better than the second one?
are there any performance issues or other overhead involved in the
second approach?


Thanx
Ben

 

[Ben]

Why are there 3 nodes (head, tail, cur)? In the destructor, you delete only
3 nodes, so is there a memory leak? Plus, what happens for a stack of 1
element; do you delete the same node twice?

head, tail and cur are used in pop() and print() functions... perhaps
they are redundant- i haven't carefully looked at them.. i'm just
trying to do it my own way to make it work... my code works fine.. all
i'm concerned about now is the destructor. I'm not quite sure if I
have to delete *next and *prev pointers as well... I'm worried if I've
designed it the right way... Dave suggested that i have to use a loop
to delete each node..

 

[Siemel Naran]

head, tail and cur are used in pop() and print() functions... perhaps
they are redundant- i haven't carefully looked at them.. i'm just
trying to do it my own way to make it work... my code works fine.. all
i'm concerned about now is the destructor. I'm not quite sure if I
have to delete *next and *prev pointers as well... I'm worried if I've
designed it the right way... Dave suggested that i have to use a loop
to delete each node..

Seems you need only one node (for the top). You could also have 2 nodes
(for the top and bottom). Anyway, if the top node is NULL then it means you
have no elements. If you have one element the top node points to a node,
but this node's next pointer is NULL.

As for print, etc, you can create a local variable node * cur = member_top.

And yes, Dave's suggestion is correct.

 

[Dave Townsend]

AHHHGG!
Ben, This is horrible! I think you've not factored the functionality
properly
between the Stack and the "storage" or list class:-

A stack can be implemented by using a list or an array, the essence of the
stack is you only care about the head or the "top", so there's a lot of
unnecessary
cruft in your list struct ( or more accurately a "node" class) dealing with
tails & curs.

Secondly, I'd want the list to be a bit smarter than the class you've
provided, I'd want to
do useful, powerful things like insert a node, get a node remove a node,
tell me if the list is empty.

Thirdly, a stack is a more "specialized" data structure than the list in
that operations are
solely performed at the head, it would seem that I could easily adapt a list
to perform operations
at the head of the list and I'd get my stack class. Typically, this
specialization is performed by "wrapping" a list class member inside the
stack class and implementing the stack operations by "forwarding" to
particular member list operations:

class Stack
{
public:
// constructor/destructor stuff not show.
public:
// error checking for empty stack omitted for illustration
void push( int e){ _list.insert_at_head(e); } // forwarding operation.
int pop( ) { return _list.remove_at_head( );}
int top( ) { return _list.element_at_head();
bool isempty(){ return _list.isempty();}
private:
list _list;
};

So, the Stack is a simple shell or wrapper over the list class which has all
the brains.
In this model, the destruction of the Stack is trivial, the _list member is
automatically
destroyed, the list class should provide the destruction behavior to loop
over the remaining
nodes left in the list and destroy them.

hope that helps!
dave

 

[Prateek R Karandikar]

An approach better than both these is to use the std::stack class template.

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
To iterate is human, to recurse divine.
-L. Peter Deutsch
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!