Stack Data Structure?

BlitzMax Forums/BlitzMax Programming/Stack Data Structure?

zoqfotpik(Posted 2014) [#1]
While investigating and evaluating different data structures for a larger project I've been working on, I keep coming back to the idea of a somewhat expanded stack.

Arrays have problems: they aren't dynamic unless wrapped up in a system that's basically like a stack anyway. They are slow for insertions (but I don't foresee doing insertions anyway.)

Lists have problems: they are not addressable by index, they have memory overhead and they cause GC issues that I don't want to deal with.

The expanded stack I'm talking about maintains a map so that it can be shuffled around internally but still be addressable by index. It is comparatively quick to expand with the size doubling algorithm-- start it at a number slightly above what you think you will need, then if more are needed, double the size. Most likely you will only have to do that once or twice at the most and that would cause a total of two fairly negligible hitches.

It's easy to push and pop on/off the end. Because of the map you can do very quick insertions-- move item N to the end of the list and insert the item you want to insert where N used to be.

Stacks are also good for things that naturally fluctuate from zero up to some arbitrary number and then back down to zero again, like a particle system or a renderables list where every tick in the update loop you check to see if a given object is onscreen and then add it to renderables. When it comes time for the render loop, you can either just pop every item until the list is at zero, or you can run through and render everything and then manually set the top of the stack to zero which might be somewhat problematic in a memory management sense but if the stack contains only index ints it isn't too bad to just leave them out there, they will mostly get overwritten next tick anyway.

Non-ordered array walks, eg. Foreach, can happen without having to go through the extra abstraction of the index map.

Thoughts? Are there limitations of this approach that I'm not noticing? Someone, maybe Brucey, had mentioned using a TList full of arrays, which seems to me to be unnecessarily unwieldy, but are there advantages there?


zoqfotpik(Posted 2014) [#2]
In case anyone reads this and wonders how to make a self-doubling stack, here it is. If you use this for any user-defined type make sure you initialize the empty locations on the array (using an init loop, eg "data[i]=new <whatever type>") or you may get an exception error or other bizarre behavior when you attempt to use it. See this if you feel the need to be even more confused.

Again, the reason for size doubling is so that if you exceed the stack size, you can resize it in an optimal number of doubling operations.

Type intstack
Field data:Int[1]
Field top:Int = 0
Field length = 1
Method push(num:Int)
	top= top+ 1
	' Check to see if we're exceeding the current size of the array
	If top > length
		' if so, double the array size.  The idea here is no matter how large the number of items we have to
		' deal with is going to be, we can resize the stack to deal with that number and do so in a small
		' number of doubling operations.  Of course it's probably a good idea to set the initial array size
		' to a reasonably large number, and the length field to that number.
		'Print "stack exceeded
		length = length*2
		data = data[..length] ' The .. is an array slice, up to the new doubled length, so the array size
							'   gets doubled.
		'Print "expanded to "+length
	EndIf
	data[top]=num
End Method 
Method pop:Int()  ' Remove the top item from the stack
	If top = 0 Return Null
	a = data[top]
	top= top- 1
	Return a
End Method 
Method dump()
	Print "---------------"
	Print "Data Space:"+data.length
	Print "Items on Stack:"+top
	If top > 0
		For i = 1 To top
		Print i+":"+data[i]
		Next
	EndIf
	Print "---------------"
End Method
Method peek(num:Int)  ' returns the int at a specific array index
	Return data[num]
End Method
Method poke(addr:Int, num:Int)  ' overrwrite the data at a specific array index with <num>
	If instack(addr)
		data[addr]=num
	EndIf
End Method
Method swap(addr1:Int, addr2:Int) ' Swap the values at two array indexes
	If instack(addr1) And instack(addr2)
		Local temp:Int = data[addr1]
		data[addr1]=data[addr2]
		data[addr2]=temp
		Return 1
	Else
		Return 0
	EndIf
End Method
Method instack(num:Int) ' Error checking function to make sure an index is in bounds
	If num > 0 And num < top+1 Return 1
	Return 0
End Method
Method 
End Type



Yahfree(Posted 2014) [#3]
The stack ADT (Abstract Data Type) in computer science generally supports three operations:

O(1) (constant time) push
O(1) (constant time) pop
O(1) (constant time) peek

Stacks are usually implemented as either a adjustable array (as you have done) or using a linked list (adding / removing to the head of the list).

Your push / pop are O(1) as you have implemented them. If you want to access specific elements, you'll probably want the array approach you specified.

I don't know what your specific needs are, so I can't tell you what data structure would help best. But it sounds like you might already know?


TomToad(Posted 2014) [#4]
You can write methods that will allow your type to be called with EachIn. Information is in the Help section of the IDE under Collections. Here is a stack type that works with Object. Should be easily modified to work with primitive types.



TomToad(Posted 2014) [#5]
If you use this for any user-defined type make sure you initialize the empty locations on the array (using an init loop, eg "data[i]=new <whatever type>") or you may get an exception error or other bizarre behavior when you attempt to use it.
Initializing the elements of the array is not necessary as you will only be passing already initialized objects to the stack methods.
Local Array:TMyType[10]
Array[0].MyInt = 0 <-Will not work, Array[0] not initialized

Local Array:TMyType[10]
Array[0] = New TMyType
Array[0].MyInt = 0 <- Will work, Array[0] has been initialized

Local Array:TMyType[10]
Local MyType:TMyType = New TMyType
Array[0] = MyType
Array[0].MyInt = 0 <-will also work as an initialized object has been stored in Array[0]



zoqfotpik(Posted 2014) [#6]
I may be able to get useful behavior out of a stack of index ints and a tlist, with the list.toarray() method. With 1000 on the list, I can do a listfromarray() something like 50,000 times per second. With 400 on the list, and that may be a more reasonable number, it's basically trivial.

So maybe the right thing to do is to let the list exist as a list for part of the loop, then translate it to an array and do needed array operations there.

Listtoarray is about 6 times faster than listfromarray so maybe I can get by without turning it back into a list.

A lot of this can be amortized away and elided with trickery in various ways because I'm not going to do full updates on things that aren't on the screen.

Tomtoad thanks for that object stack.