NewsForumsCodeLogsGallerySpecsSearch

stack implementation in BlitzMax?

BlitzMax Forums/BlitzMax Beginners Area/stack implementation in BlitzMax?

Bukky(Posted 2006) [#1]
Does BlitzMax come with a default Stack type? If so, what is the syntax for declaring, pushing, and popping a stack?


Defoc8(Posted 2006) [#2]
I dont think there is a stack class/type..

You should easily be able to simulate stack behaviour by
extending TList - perhaps not optimal..but maybe the
simplest solution..


H&K(Posted 2006) [#3]
Would you extent Tlist. Or do it with an "expanding" contracting Array? I suppose it depends on if expanding the array means making a whole new array, and coping the old one.
But if you wanted to "Cap" the stack, an array would work.

OR, and I think this is the way to do it, would be to alloc some memory, and have a pointer to the "End of the stack", that you move up and down in your stack.
If you did it with ?debug compiler directives, you could bounds check in debug and not in release


Dreamora(Posted 2006) [#4]
My datastructure modules include beside a feature rich LinkedList class a Queue and Stack class. ( http://www.dreamora.net )


Defoc8(Posted 2006) [#5]
anyway whatever you do - it wont be tricky if you stick to
storing one specific object type on your stack..
If you want to mix n match - letting primitives like float
and int be stored alongside object pointers..things get a
little tricky - partially becuase return type is explicit, you might
need multiple return methods, one for each basic type..
and additionial information stored with every object pushed on to the stack - basically wrapper which can
contain each type of object, and information about what
type is actually being stored..a mask might be enough..

I dont know enough about what is, and what isnt possible
with bmax objects.. I cant actually see how a clean system
would be developed that can store all possible types under one simpler interface..a single stack that can mix n
match... lol, i guess i didnt think this through when i made
my initial post... ;)

id grab dreamora's work..save yourself a headache


Bukky(Posted 2006) [#6]
Thanks guys :)


dmaz(Posted 2006) [#7]
?? just use TList

Local stack:TList = New TList

' push
stack.AddFirst(blah:yourtype)
' pop
blah:yourtype = stack.RemoveFirst()


but if you need just a stack of ints like I did a little while back.... I put this together
'Since we can't do a list of Ints without a type
Type IntStack
	Field a:Int[]
	
	Method NotEmpty:Int()
		If Len(a) > 0 Return True Else Return False
	End Method

	Method Size:Int()
		Return Len(a)
	End Method
	
	Method Push(i:Int)
		a = a[..Len(a)+1]
		a[Len(a)-1] = i
	End Method
	
	Method Pop:Int()
		Assert Len(a)>0," Tried to Pop and empty IntStack"
	
		Local i:Int = a[Len(a)-1]
		a = a[..Len(a)-1]
		Return i
	End Method
	
	Method Clear()
		a = a[..0]
	End Method
	
	Method Dump:String()
		Local s:String
		For Local i:Int = EachIn a
			s = s + i + ", "
		Next
		Return s
	End Method
End Type



Defoc8(Posted 2006) [#8]
dmaz, looks like your resizing the array by one element?
- this isnt usually a good idea, try increasing the stacksize
as needed & using array index values to mark the current pos -
If the stack is full, resize it..double it...dont grab/release
mem like this.. :p - you should be
looking to minimise stalls caused by allocating and freeing
memory...if your careful about your initial stack size, it
probably wont even have to resize itself..

anyhoO..thats jst my opinion..


Dreamora(Posted 2006) [#9]
Jupp, double and half the size of arrays when you need to resize it. Thats common programming practices as it results in a "averange cost" in O(1) if you do it that way ie on the long run it won't make a difference.

Slicing one by one costs an awfull lot of time.


dmaz(Posted 2006) [#10]
yeah, should be doing that for sure.