Stack: first in last out?

Monkey Forums/Monkey Programming/Stack: first in last out?

AdamRedwoods

(Posted 2013) [#1]

Does the current stack module do a first-in last-out? Surprised I don't see it.
Could use a "PopLast:T()" for queues, but i suppose you'd need another variable to track location of both ends, to avoid costly list iterations. Or pre-define a FILO over FIFO.
Should I just use a list?

Gerry Quinn

(Posted 2013) [#2]

First-in last-out is the standard for stacks. There is a ring buffer class for first-in first-out.

I don't think Monkey has a deque class as yet, but maybe one could make one from an adapted ring buffer.

AdamRedwoods

(Posted 2013) [#3]

sorry! I meant FIFO!
you're right, FILO is standard. i'll look a the ring buffer and see what it has.

dmaz	(Posted 2013) [#4]

Class ugFIFO<T>
	Field queue:T[]
	Field in:Int
	Field out:Int

	Method New()
		queue = New T[3+1]
	End

	Method New( size:Int )
		queue = New T[size+1]
	End
	
	Method Init()
		in = 0
		out = 0
	End
	
	Method Size:Int()
		Return queue.Length-1
	End
	
	Method Put( value:T )
		If in = (out-1 + queue.Length) Mod queue.Length
			' is full
			queue = queue.Resize(queue.Length*2)
		Endif
		
		queue[in] = value
		in = (in+1) Mod queue.Length
	End
	
	Method IsEmpty:Bool()
		If in = out
			' is empty
			Return True
		Endif
		Return False
	End

	Method Get:T()
		If IsEmpty()
			Error "Attempted Get() on empty fifo"
		Else
			Local value:T = queue[out]
			out = (out+1) Mod queue.Length
			Return value
		Endif
	End

	Method ObjectEnumerator:Enumerator<T>()
		Return New Enumerator<T>( Self )
	End


End

Class Enumerator<T>

	Method New( q:ugFIFO<T> )
		Self.q=q
	End

	Method HasNext:Bool()
		Return Not q.IsEmpty()
	End

	Method NextObject:T()
		Return q.Get()
	End

Private

	Field q:ugFIFO<T>
	Field index

End


#rem
Function Main()
	Local q:ugFIFO<String> = New ugFIFO<String>'(3)
	
	For Local i:Int = 0 To 10
		q.Put i+"-> "+(i+100)
	Next

'	For Local i := Eachin q
'		Print i
'	Next

Print ""


	Print q.Get()

'	q.Init

'	Print q.Get()
'	Print ""
'
'	For Local i:Int = 3 To 4
'		 q.Put i+1000
'	Next
Print ""
	For Local i := Eachin q
		Print i
	Next
	
'	For Local i:Int = 0 To 10
'		If Not q.IsEmpty() Then Print q.Get().value
'	Next
	
'	For Local i:Int = 0 To 4
'		q.Put i+100
'	Next
'
'	For Local i:Int = 0 To 4
'		Print q.Get()
'	Next

End
#end