A stack is a data structure used to store the contents of registers for later use. A series of contiguous memory locations are set aside to hold the data. A pointer is used to record where the top of the stack is. When an item is added to the stack, we store it in the memory word pointed to by the stack pointer. We then increment the pointer to point to the next word.
When we remove an item from the stack, we first decrement the stack pointer and then access the memory word which it points to. The stack is therefore a 'last in, first out' (LIFO) structure.
There are four possible stack structures, which are made of combinations of two variants.
The first of these variants determines which direction the stack grows in. We can create stacks that grow upwards in memory as extra items are pushed on, and contract downwards as items are pulled off (ascending stack), or the opposite, where the stack grows downwards in memory as items are added, and contracts back up again as they are pulled off (descending stack).
When a stack is implemented, you must decide exactly what the stack pointer should point to. It could point to the top entry on the stack, i.e., the one most recently pushed on the stack ('full'), or alernatively, it may point to the next available space in the stack's memory area, i.e., the address a which a new item would be stored if it were pushed onto the stack ('empty').
Hence the four stack structures are:
(1) Full, ascending stack
(2) Full, descending stack
(3) Empty, ascending stack
(4) Empty, descending stack
Examples
The LDM and STM instructions provide the facilities to implement stacks in machine code. The elements pushed to, and pulled from, the stack are the register contents specified in the instruction's register list.
The stack pointer is implemented using the instruction's base register. This always points to the address in memory where the instruction will store or load data. R13 is used most often for this purpose although any register could be used.
Implementing stacks
[sh-index] Back to list of manuals
|
| |
