Stack Processing Review

It's probably a good idea to spend a few moments thinking about stacks, first the more theoretical abstract data type and second the more practical version we really want to work with.

Stacks

Suppose we want to evaluate 


(1 + 5) - (2 + 3)
Saying how to do this out loud (and being very wordy about it!), we'd probably say something like:
  1. ``Add 1 to 5 and stash the result someplace''
  2. ``Add 2 to 3 and stash the result someplace''
  3. ``Take the last two results and subtract them''
One of the basic rules of programming is to avoid special cases - the way we just described evaluating that expression uses a different description of how to add 1 to 5, and 2 to 3 than how to subtract the last two results. So here's another description of how to do it, which is wordier but doesn't end up with so many special cases.
  1. ``Write a 1 on a piece of paper and put it on the table''
  2. ``Write a 5 on a piece of paper and put it on top of the last piece of paper''
  3. ``Add the contents of the top two pieces of paper together, throw them away, write the result of the addition on a piece of paper, and put it where the old pile of papers was.''
  4. ``Write a 2 on a piece of paper and put it on top of the last piece of paper''
  5. ``Write a 3 on a piece of paper and put it on top of the last piece of paper''
  6. ``Add the contents of the top two pieces of paper together, throw them away, write the result of the addition on a piece of paper, and put it where the old pile of papers was.''
  7. ``Subtract the top piece of paper from the second piece from the top, throw the pieces of paper away, write the result on yet another piece, and put the new piece on the table.''

    8. This is an example of using a stack. A stack is a natural data structure to use in applications where you need to retrieve data from the structure in the reverse of the order in which it is inserted (like we just did). The classic example is in expression evaluation like we did above (in fact there have been many, many pocket calculators on the market that use stack-based operations. HP is best known, but far from alone). The stack has two fundamental operations: push and pop. push puts data on the stack, and pop gets it back off.

    We also normally define the stack operations as including arithmetic: add() adds the top two elements of the stack together, while subtract() subtracts the top element from the second-from-the top. Our arithmetic evaluation now looks like this: 

    
push(1)
push(5)
push(pop() + pop())
push(2)
push(3)
push(pop() + pop())
push(-pop() + pop()

    There is an alternative notation for arithmetic, developed by Lukasiewicz. In his notation, instead of putting the operation between the operands like we're used to, we put it after the operands, like this. 

    
1 5 + 2 3 + -

    The 1 5 + means what we're used to seeing as 1 + 5. The 2 3 + means 2 + 3.

    The advantage of this notation is that it isn't necessary to have any sort of defined order of evaluation, nor to use parentheses.

    Practical Stacks

    The "theoretical" stack has two operations (in addition to initialization and tests for empty): push and pop. In practice, we also need to be able to examine and modify the contents of the stack. This means we'll need an additional operation.

    The top operation lets us look at the top element of the stack. This operation actually turns up occasionally in "theoretical" descriptions of stacks. We actually want more than this: we will want to be able to examine an element at a distance of n from the top of the stack. As you can guess, we'll use indexed addressing for this.