Stacks and Stack Pointers
(Last Mod: 27 November 2010 21:38:40 )
A "stack" is a specific kind of data storage and retrieval scheme that lends itself to many, many applications in engineering - and only a fraction of them are in the field of software engineering.
A stack has specific properties that govern its behavior and if those properties match the behavior needed, then using a stack can make your system development considerably easier. But the reverse is true - not all problems lend themselves to the behaviors inherent with a stack and using a stack in those situations can be extremely frustrating and counterproductive. A stack is simply one tool among many that you have and, as with all things, the more tools you have and know how to use, the simpler your job will be.
To get a useful mental picture of a simple stack, consider a plate dispenser found at cafeterias. This is a spring loaded platform that trays are loaded onto and the user always takes the tray on top. Likewise, when trays are placed onto the stack they are placed on top of the trays already there (at least we'll assume this is the case). The key thing to note is that this is a LIFO system which means Last-In First-Out - the last item placed into the storage device is the first item that will be pulled out of the device. Hopefully you can see that the use of the word "stack" to describe this method of data storage is quite appropriate and descriptive.
To get a mental picture of a physical stack that is more closely analogous to most software and hardware stacks, consider a stack of N mailboxes that are numbered 0 through N-1. Obviously, you can put N pieces of information into this set of boxes (assuming that each box is limited to holding one piece of information which is the case if those "boxes" are actually locations in memory). Sounds like an plain old array, doesn't it? Well, it is. What will make it a "stack" is how we use it - we agree up front that we will restrict ourselves to specific, well-defined operations that will make it behave like we expect a stack to.
So what are these behaviors? The most basic two behaviors are simply:
To see how this is implemented, imagine that our stack of mailboxes is in a room and there is a clerk at the door. Users come up to the door and either give the clerk something to place in storage or they ask the clerk to give them something that is already in storage, subject to the two behaviors above. The key thing to note is that the User never interacts directly with the mailboxes - this is the job of the clerk. As the long as the clerk knows how to do their job, we don't have to worry about the User coming in and messing up the data.
So what, exactly, is the clerk's job? Simple, they manage the stack. They enforce the Rules of the Stack. Nothing more and nothing less. How they do this is up to them - the user does not need to know these details. Similarly, the clerk doesn't need to know what the data is or what it is used for or why the User is bring things by to drop off or coming to pick things up - that is the User's area of expertise and it is the User's responsibility to do it correctly.
It turns out that there are a couple of questions that arise so frequently that, if the clerk can answer them for the User, it helps the User do their job a lot more efficiently. The first is whether there is presently anything at all in storage (is the stack empty?) and the second is whether there is enough room to store any more items (is the stack full?). So we will add these to the behavior of our generic stack. There is one other behavior that is frequently overlooked and that is the need to have some means of emptying the stack. At the very least, we need to do this when we first start up our program to initialize the stack. It's also possible that, for reason's known only to the User (the clerk doesn't care, they just comply) the User might periodically tell the clerk to clear out the room and start over. So this leaves us with the following list of behaviors:
Stack behavior:
So what if you are the clerk? Clearly the clerk has to have some means of dealing with the details of managing the stack. How do they do this? The most obvious way is for the clerk to place the first item given to them in Box 0. If they are given another item, they place it in Box 1. The next item goes in Box 2. If someone then comes to get an item, the clerk gives them whatever is in Box 2. You can imagine the clerk looking at all of the boxes and determining which box is presently "on top" and then placing a new item in the next box up or, if handing out an item, simply taking whatever is in the "on top" box. This method, where the clerk has to examine all of the boxes (or at least many of them) each time a transaction occurs is workable for a small number of boxes but quickly becomes unmanageable as the number of boxes increase.
Imagine being the clerk in a room the size of a football field having several hundred thousand boxes. You need something more elegant and efficient in this case in order to do your job. What if you simply had a whiteboard near the door and the only thing written on that board was the number of boxes that presently have something stored in them. If you had 100 boxes (numbered 0 through 99) and the number on the board was 15, then that one number gives you a lot of information. Specifically it tells you that:
Now let's shift our attention to a software stack manager (the generic name for the collection of functions that carry out the list of tasks described earlier). Our data storage system consists of:
Once we have been introduced to the concept of "structures" in C the tasks of grouping the container and the stack pointer together and passing them around as a single entity will become very straightforward. Object Oriented Programming, in C++, takes this a step further and groups not only the data but also the functions that act on that data together as an "object". But for now, we will just accept that the User will have to pass the any needed data - namely a pointer to the container and a pointer to the stack pointer - to the stack management functions.
Even so, in keeping with the separation of responsibilities, the User agrees not to use or change any of that data directly - it's treated as though it were in a sealed envelope or written in some strange language. If the User wants to know if the stack is empty, they give the manager the container and the stack pointer and ask the manager to examine them and answer the question. This is important, because if the User takes a short cut and "peeks" at the stack pointer and answers their own question they might answer it wrong. Sure, a stack pointer that is equal to zero might mean that the stack is empty - that would certainly be true using the description we developed above. But what if the manager decides to change how they keep track of things? What if they decide that the stack pointer will point to the top item on the stack (instead of the first empty location on the stack)? Now if the stack is empty the pointer will be equal to -1. This aspect is one of the driving forces behind object oriented programming where the idea is not just to package the functions together with the data but to make it impossible (or at least extremely difficult) to interact with the data directly and thereby force the User to interact only through the functions intended to do so. That way if we change the internal workings of the data and the functions we don't have to worry about our impact on Users that chose to cheat (even though it's their own fault if things go bad) because cheating wasn't an option for them to begin with.