Stack |
The easiest kind of list to implement is the stack, it is defined as a list in which all the deletions and insertions take place at one end, called the top of the stack.
E.g. Stack of plates on a counter, new plates are added at the top, and plates are also taken from the top
When we add an item to the stack, we say that we push in on to the stack. When we remove an item from the stack we pop it from the stack. For this purpose, the stack is also known as the push-down list.
As an important application of stacks, is what happens within a computer system when subprograms are called. The system (or the program) must remember the place where it was called from, so that it can return there after the subprogram has completed. It must also remember all variables, CPU registers, and the like, so that the information will not be lost while the subprogram is working. We can think of all this information as one large record, a temporary storage area for each subprogram.
Suppose now that we have three subprograms called A, B, and C. If A is operating (1) the data from A is on the stack, if A then invokes B (2), the data relating to B is pushed on the stack, if B then invokes C (3), the data from C is pushed on the stack. When C completes the data relating to C is popped from the stack and processing returns to B.
Stacks operate under a LIFO property. last in first out, stacks are also referred to as LIFO lists because of this property.
To ensure that addition/deletion occurs properly a stack pointer is used
Another possible application of stacks is recording containers in a container ship. Containers are loaded onto a ship one on top of the other and stacks in front of other stacks. In general terms the containers need to be unloaded in the reverse order they are loaded. So using a stack data structure would enable you to manage the containers.
Consider one stack of containers (for the example we'll limit them to 4 high).
Adding a container to the stack (PUSH)
After 3 containers added (PUSHed)
Deleting entry from a Stack using POP
Application areas |
Similarily in a coolstore, pallets are loaded on top of each other. Obviously you need to be careful that the pallet on the bottom isn't stuck there.
[Rev 05/03/99] 28/5/97 © 1997-99 V/2-Com (Verhaart), P O Box 8415, Havelock North, New Zealand.