Stacks

From C64-Wiki
Jump to navigationJump to search

It is vital to understand how to create and use stacks if you wish to perform some of the more advanced programming techniques in C64 BASIC.

A stack is basically an array which provides access only to the last value placed in the stack. In order to setup a stack you need to DIMension an array and set aside a variable whose sole use is as a "stack pointer" (an index into the array). There are two routines involved with stacks: a PUSH routine which add an element to the stack and a PULL routine which removes an element from the stack.

Stacks can be made from arrays of strings, real numbers or integers. An integer stack is often useful when storing indexes into other arrays since it can conserve space. Stacks can either grow downwards (the stack pointer points at the end of the array and is decremented each time an element is added) or upwards (the stack pointer points to the beginning of the array and is incremented each time an element is added). The stack pointer may be set to point to the next free array index or to the element last added.

None of these things matter as long as the PUSH and PULL routines use the stack pointer consistently. However, if the stack grows upwards and the stack pointer points to the last element added then the stack pointer variable automatically gives the number of elements already on the stack.

The following example sets up a stack of real numbers and includes an (optional) check for full/empty status.

10 MX=20:DIM ST(MX):SP=0
196 REM
197 REM PUSH - ADD NUMBER IN VARIABLE N
198 REM TO THE TOP OF THE STACK
199 REM 
200 IF SP<MX THEN 220
210 PRINT"? STACK OVERFLOW ERROR":STOP
220 SP = SP+1:ST(SP)=N
230 RETURN
296 REM
297 REM PULL - REMOVE NUMBER AT TOP OF
298 REM THE STACK AND STORE IT IN N
299 REM
300 IF SP THEN 320 
310 PRINT"? STACK UNDERFLOW ERROR":STOP
320 N=ST(SP):SP=SP-1
330 RETURN