🔒 Locked

dynamic stack class

Started by vaneger Aug 11, 2002 at 2:34 PM 14 replies 550+ views

Original Post

Aug 11, 2002 at 2:34 PM

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

niyaw

Aug 11, 2002 at 2:43 PM

is there a reason to not use std::stack?

bslayerw

Aug 11, 2002 at 2:51 PM

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.

vaneger

Author

vaneger

Aug 11, 2002 at 4:59 PM

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]

TangentZ

Aug 11, 2002 at 5:26 PM

Hmm... std::stack is as standard as it''s gonna get...

Kami no Itte ga ore ni zettai naru!

vaneger

Author

vaneger

Aug 11, 2002 at 7:29 PM

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.

Deyja

125

Deyja

Aug 11, 2002 at 7:45 PM

Write it in assembly.

DanG

Aug 11, 2002 at 9:51 PM

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.

DerekSaw

Aug 11, 2002 at 9:59 PM

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!

c_wraith

Aug 12, 2002 at 2:52 AM

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.

Origin

Aug 12, 2002 at 2:18 PM

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.

daerid

Aug 12, 2002 at 3:53 PM

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?

Origin

Aug 12, 2002 at 4:25 PM

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

vaneger

Author

vaneger

Aug 12, 2002 at 5:55 PM

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.

Shannon Barber

Mod

368

Shannon Barber

Aug 12, 2002 at 6:05 PM

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]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.