Data, the boring part of computing!

Of course I for one don’t believe this common view of this major component of every application and computer system. Many view data as something that programs simply shovel from one place to another, occasionally changing it on the way.

Even though this view admits that programs are about manipulating data, and hence important, I don’t think that this goes far enough. The traditional view is that a program is an equal mix of commands, the verbs, and data, the nouns. An alternative and more modern view is of data and commands mixing together in a smooth blend that produces a “mechanism”, a “model” if you like, of something that does a job. Yes, you’ve guessed it, I’m taking about object-oriented programming but my excuse is that there really is no other sort!

To paraphrase a well known quote:

any sufficiently sophisticated form of programming is going to be indistinguishable from object-oriented programming…

The stack

What does all this mean? When you first start to program you learn about variables, then arrays, and then if you are lucky you learn about structures or records. After this what you learn is very variable – pun intended…

The art of programming beyond this simple beginning depends on inventing, or should I say reinventing, sophisticated data structures. The problem is where to begin and the general consensus is that the stack is where it’s at.

A stack is exactly what it sounds like. Make a stack of cards, say, on a table and you have everything you need to know about a stack. What are the basic stack operations – you can put a new card on the top of the stack and you can take a card off the top of the stack. As long are you aren’t cheating and dealing from the bottom (that would make it a data structure called a deque) putting something on the top and taking something off the top are the only two stack operations allowed.

Usually these two operations are called “push” and “pull” or “push” and “pop” but what you call them doesn’t really matter as long as you understand what is going on.

Pushing C onto a stack stores it where the TOS pointer indicates

Popping the stack retrieves the top data item and moves the TOS down one

If we have a stack and we do Push A, Push B and Push C what do you think you get if we next do a Pop? If your answer is C you understand how a stack works. Stacks are interesting because they can be used to alter the order of things. You stack A, B and C and you get back C, B and then A. It reverses the order without you having to do anything and this is very useful.

This accounts for the other name for a stack – a Last In First Out stack or LIFO stack. In fact this order changing ability is such a powerful property that you can build computers that have no other memory than a stack and no other storage operations than push and pop. You can even create programming languages that have nothing but a stack as their single data structure and all of their commands refer to the stack.

Even though you can have stack-oriented languages there are few popular or common languages that have stacks as standard – you have to create your own using whatever they provide. If you know how fine, if not then you have to use something less appropriate. So, how is it done? All you need is an array and a variable to act as a pointer to the top of stack or TOS as it is usually known. The array simply has to be big enough to hold the maximum number of items. The pointer is simply set initially to the start of the array. You might set up the stack as:

Dim Stack(10)
Pointer=1

To push something on to the stack the operation is:

Stack(Pointer)=something
Pointer=Pointer+1

To pop something off the stack the operation is:

Pointer=Pointer-1
Something=Stack(Pointer)

If you want to get picky about stacks you can argue the point of whether the pointer should point to the item on the top of the stack or to the next free space on the stack. Experts prefer to have the pointer to the item on the top of stack rather than the next free space. About the only thing that can go wrong with a stack is that it runs out of space i.e. the stack pointer goes beyond the end of the array or that it under runs, i.e. the user of the stack attempts to pop something off the stack when there isn’t anything to pop.

<ASIN:0201000237>

<ASIN:0534491820>

<ASIN:1584502509>

<ASIN:0521670152>