Stack - Data Structures

[kevin]

PlayBASIC Code: [Select]

; *=-------------------------------------------------------------------------=*
;
;   This example shows how you can roll some functions to treat arrays like
; stacks.  In this example were using a 1D integer array  for a data stack.
;
;  What is a stack ?
;  =================
;
;  Conceptually, a stack is simple: a data storage method that allows adding and
;  removing elements in a particular order. Every time an element is added,
;  it goes on the top of the stack, the only element that can be removed is
;  the element that was at the top of the stack.
;
;   Consequently, a stack is said to have "first in last out" behavior
;  (or "last in, first out"). The first item added to a stack will be the last
;  item removed from a stack.
;
; *=-------------------------------------------------------------------------=*


 Dim MyStack(0)

 Print "Pushed Data to stack"
 For lp=0 to 10
; grab a random value to store on our MTSTack() array
  ThisValue=rnd(1000)  
; display the value so we can see it
     print ThisValue
; push it to the stack
     PushToStack(myStack(),ThisValue)
 next



setcursor 0,200
print "STACK CONTENTS:"
print ShowStack(MyStack())




; Display the values off the stack
setcursor 0,300
Print "Popped values"

  For lp=1 to StackSize(MyStack())
  Print PopFromStack(MyStack())  
  next

Sync
waitkey



; =-----------------------------------------------------------------=*
;            Get the Size of this array stack
; =-----------------------------------------------------------------=*


FUnction StackSize(Array())
  Size=GetArrayElements(Array(),1)
EndFunction Size


;  Note, This example is generic (works on any 1D integer array) you
;        could easily optimize this to remove the constant resizing 
;        by storing the current stack index/pointer in element zero
;        of the array.  Which is not used.. Same applies for the 
;        cell copy, as you could simply store new cells at the end. 
;
;         But that's an exercise for the user :) 


; =-----------------------------------------------------------------=*
;            Push a Integer value onto our Stack array
; =-----------------------------------------------------------------=*


Function PushToStack(Array(),ThisValue) 
; Get the current size of this array
  Size=GetArrayElements(Array(),1)

; redim it (resize) so it's one element bigger
  redim Array(size+1)  

; copy all existing cells (elements) down one stop to
; make room for inserting the new element at top
  CopyArrayCells   array(),size,-1,array(),size+1,-1,size 

; insert the new Top element at array position #1
  array(1)=ThisValue
EndFunction


; =-----------------------------------------------------------------=*
;             Pop the top value off our Stack array
; =-----------------------------------------------------------------=*


Function PopFromStack(Array())
; Get the Arry of the stack array
  Size=GetArrayElements(Array(),1)
; check if there's at least 1 item in the stack
  if size>0
 ; grab the TOP item at array index #1
     ThisValue=Array(1)
 ; copy all the following cells Up.  So now element
 ; 2 is in element 1's position and so on
     CopyArrayCells  array(),1,1,array(),0,1,size
       ; reduce the arrays size by 1 element 
     redim Array(size-1)  
  endif
EndFunction ThisValue



; =-----------------------------------------------------------------=*
;        Build a string of the stack contents for displaying
; =-----------------------------------------------------------------=*

Function ShowStack(Array())
  Size=GetArrayElements(Array(),1)
  if size>0
     for lp=1 to size
    s$=s$+str$(Array(lp))
    if lp<>size then s$=s$+","
     next
  endif
EndFunction s$

Return To PlayBasic Tutorial Index