Stacks

Stacks, also known as Last-In-First-Out (LIFO) queues, are an important data structure for the implementation of functions and procedures. Data elements are removed from a stack in the reverse order from which they were inserted on the stack. Stacks are useful for a variety of reversal and backtracking operations.

A stack has two operations:

1. push(x) inserts element x on the stack.
2. pop(x) removes the last element inserted from the top of the stack and returns it in x.

Stacks can be implemented in a variety of ways such as arrays, linked lists, or trees. In SAL, we implement a stack using an array of elements and a variable called the stack pointer which contains the address of the array element on the top of the stack.

A stack of integer elements may be declared in SAL as:

        .data
stack:  .word   0:stacksize   # the stack array
sp:     .word   stack  # the stack pointer

Alternatively, the stack pointer may be initialized using the la instruction:

        .data
stack:  .word   0:stacksize
sp:     .word
        .text
        la      sp, stack

In both of these declarations, the stack pointer is initially set to the first element of the stack array, which is empty. By convention, the stack pointer contains the address of the empty array element just above the top of the stack.

To push an integer element, X, onto the stack requires a move operation followed by an update to the stack pointer:

        move    M[sp], X
        add     sp, sp, 4

To pop the top element of the stack, the stack pointer is first decremented and then the element is moved to X:

        add     sp, sp, -4
        move    X, M[sp]

Care must be taken not to push elements onto a full stack or attempt to pop elements from an empty stack. Such operations will result in memory accesses which are outside the memory array allocated to the stack.

A stack is a useful structure when performing binary to decimal ASCII conversion, as in the put I instruction, where I is an integer. The conversion algorithm for positive integers is:

        repeat
            digit := number mod 10 ;
            number := number div 10 ;
            push(digit) ;
        until (number = 0) ;
        repeat
            pop(digit) ;
            writeln(digit) ;
        until (stackempty()) ;

A SAL implementation of this algorithm is shown below:

#       
#       Print a positive binary integer as ASCII decimal characters
#
        .data
stack:  .word   0:10    # the stack array
sp:     .word   stack   # the stack pointer
bottom: .word   stack
bias:   .word   48      # ASCII '0'
number: .word   # the number to be converted to ASCII
digit:  .word   # a decimal digit during the conversion

        .text
__start:
        get     number  # read a number as an integer
loop:   rem     digit, number, 10
        add     digit, digit, bias    # convert digit to ASCII
        move    m[sp], digit   # push(digit)
        add     sp, sp, 4
        div     number, number, 10
        bgtz    number, loop
print:  add     sp, sp, -4     # pop(digit)
        put     m[sp]
        bgt     sp, bottom, print
        done