Stacks

STACKS

• Random access memory requires knowing the address of every byte/word you want to access
• Stacks offer a way of organising and accessing memory without random (indexed) access:
• There are hardware stacks and software stacks.
• Hardware stacks created out of dedicated shift registers
• Software stacks typically defined in RAM using conventions (we’ll come back to this):

IN SIMPLE TERMS...

• A stack allows us to mothball/backup/hibernate a process/ task at will on the receipt of an interrupt or code invocation.
• To do this, we
• push instructions/data that we will need later onto the stack;
• do the task;
• and then pop the stored data back off the stack and
• continue as before.

Stacks (6 deep)

5 7 5 x x x x x

Push on a 0. 5 x x x x x x x Pop off the 0 x

Pop off the 7 x x x x x x x x Push a 2 x

Pop off the 2 x x x x x x x x x If you remove another item you get the 5 and the stack is now empty. x x x x x x x x x If you try to remove another you either get a underflow error or rubbish.

SOFTWARE STACKS

• We can also use ordinary RAM to implement a stack.
• Stack space only limited by the amount of addressable RAM.
• The "top" of the stack moves "up" and "down" as things are pushed or popped, and the location of the "top" is stored in a register (Stack pointer).
• We will come back to this later in semester

SUMMARY

• Stacks are a fundamental data:
• Simple and efficient storage/recalling of data
• Reduces need for storing memory addresses
• Can only access data at the top of the stack
• We store data by “pushing” data onto the stack
• We recall data by “popping” data off of the stack
• Hardware stacks utilise dedicated shift registers:
• soon we are going to build one ourselves!
• Software stacks use RAM (we’ll come back to this later!)