Archived

This topic is now archived and is closed to further replies.

vaneger

dynamic stack class

Recommended Posts

hows this stack as a linked list class look?
  
#ifndef DYSTACK_H_
#define DYSTACK_H_
template <class type>
class dyStack
{
	public: 
		dyStack();
		bool push(const type& x);
		bool pop(type& x);
		bool get_top(type& x)const;
		inline bool is_empty()const
		{
			return m_top == NULL;
		}
		inline bool is_full()const
		{
			node *x = new node;
			return (node == NULL);
		}

		bool m_return;
	private:
		struct node
		{
			type item;
			node *next;
		};
		node *m_top;
};
#include"dyStack.cpp"
#endif

#include<stdlib.h>

template <class type>
dyStack<type>::dyStack()
{
	m_top = NULL;
	m_return = false;
}

template <class type>
bool dyStack<type>::push(const type& x)
{
	node *m_old;
	bool success;
	m_old = m_top;
	m_top = new type;
	if(m_top ==NULL)
	{
		m_top = m_old;
		success = false;
	}
	else
	{
		m_top->next = m_old;
		m_top->item = x;
		success = true;
	}
	return success;
}

template <class type>
bool dyStack<type>::pop(type& x)
{
	node m_old;
	bool success = false;
	if(m_top != NULL)
	{
		x = m_top->item;
		m_old = m_top;
		m_top = m_old->next;
	}
	return success;
}
template <class type>
bool dyStack<type>::get_top(type& x)const
{
	bool success = false;
	if(m_top!=null)
	{
		x = m_top->item;
		success = true;
	}
	return get_top;
}
  

Share this post


Link to post
Share on other sites
My thoughts exactly. Use the std::stack. It has been tested, debugged and optimized. It seems you already understand the concept of a stack which is the one of the only reasons someone would want to implement their own stack.

Share this post


Link to post
Share on other sites
i use my own classes and containers all the time so i dont have to deal with using something else if i am forced to use a differnt compiler or an unfamilar machine, i cna just upload my classes from disk and run with it.plus its easier to modify my code then it is to modify a .pch file from the std.

[edited by - vaneger on August 11, 2002 6:06:13 PM]

Share this post


Link to post
Share on other sites
It can be worth while to write your own contenners on occasion if you want something specific and/or know a way that is better than the std implementation for this. If you need the stack to have an Add_10_to_All() function, you''ll have to write your own. It may well be the same case for vaneger here.

Share this post


Link to post
Share on other sites
quote:
Original post by vaneger
ok perhaps this is a better question : how can i make my dyStack class as efficent as teh std::stack without copiying the source and renaming it or something.

Study how STL does things. Understand the concept of iterators. Profiling other version of std::stack with yours. See what''s the different between STLPort, Dinkumware, RogueWave or etc in term of actually implementation.... AND ... extensive DEBUG!

Share this post


Link to post
Share on other sites
Depending on your desired performance characteristics, an array-based implementation can be much more efficient than a linked-list based implementation.

Array: Assuming you use a double-on-copy approach to resizing the array, significantly faster overall. However, the few times it needs to resize the array it''ll be very slow for one access.

Linked List: Much more uniform access times. However, the overhead on memory allocation/freeing is relatively high, leading to slower speeds overall.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I would use std::stack.

But if you''re stuck on using your own stuff, this looks a bit buggy. You''re leaking memory. The whole linked list is never deleted!

Also, i''m pretty sure new throws a bad_alloc exception when it fails, not return 0 like malloc.

Share this post


Link to post
Share on other sites
Don''t try to beat std::stack or other STL containers in performance. Only create custom container classes if the standard classes don''t fit your needs.

The STL is well designed and highly efficient, the only drawback is its - to my mind - ugly C style. But that way you can easily tell STL code from your own code... assuming that you use a different coding style, of course.

Share this post


Link to post
Share on other sites
quote:
Original post by Origin
The STL is well designed and highly efficient, the only drawback is its - to my mind - ugly C style.


Holy shit. Where can I get my hands on the shit you''re smoking? Or are you just talking about naming conventions?

Share this post


Link to post
Share on other sites
quote:
Original post by daerid
Holy shit. Where can I get my hands on the shit you''re smoking? Or are you just talking about naming conventions?

Of course I''m just talking about naming conventions. I guess I should have said that clearer but that''s what I meant with "style".

Share this post


Link to post
Share on other sites
ok so i need a destructor:/ hows this look

  
~dyStack()
{
node *m_old = new node;
m_old = m_top;
while(m_top != null)
{
delete m_top;
m_top = m_old->next;
}
}

im 99% sure this is wrong, havent coded a destructor for a linked list.

Share this post


Link to post
Share on other sites
The performance test performed by the Boost Graph Library guys resulted in nearly uniform results on vector being the fastest for _all cases except one_ when using MSVC. When performing random deletes the list won by a _small_ margin.
In gcc this was not the case. The list & vector performed better or worse as expected.
The discrepency seems to lie in the lack-luster optimization that gcc performs, and the hideously slow (de)allocation time of MSVC's C run-time.

quote:

Also, i'm pretty sure new throws a bad_alloc exception when it fails, not return 0 like malloc.


It's suppose to, but older C++ compilers don't do this (e.g. Borland Turbo C++ 3.0), nor does MSVC 4/5/6/7 to preserve compatiblity with older code. MSVC7 (an maybe 6) does call the new handler, so you can implement standard behavior if you want to.


  
node* temp, p = m_top;
while(p)
{
temp = p;
p = p->next;
delete temp;
}


[edited by - Magmai Kai Holmlor on August 12, 2002 7:07:21 PM]

Share this post


Link to post
Share on other sites