Part II of our look at data takes us into more sophisticated structures that are fundamental to computing  - stacks, queues, deques and trees. If you don't know about these four then you are going to find programming tough and you will have to reinvent the wheel to solve otherwise simple problems.

What Programmers Know

Contents

1. The Computer - What's The Big Idea?*
2. The Memory Principle - Computer Memory and Pigeonholes*
3. Principles of Execution - The CPU
4. Assemblers and assembly language*
5. The Essence Of Programming
6. Variables - Scope, Lifetime And More*
7. Binary Arithmetic
8. Hexadecimal*
9. Binary - Negative Numbers*
10. Floating Point Numbers*
11. Inside the Computer - Addressing
12. The Mod Function
13. Recursion
14. The Lost Art Of The Storage Mapping Function *
15. Hashing - The Greatest Idea In Programming
16. Advanced Hashing
17. XOR - The Magic Swap*
18. Programmer's Introduction to XML
19. From Data To Objects*
20. What Exactly Is A First Class Function - And Why You Should Care*
21. Stacks And Trees*
22. The LIFO Stack - A Gentle Guide*
23. Data Structures - Trees
24. Inside Random Numbers
25. The Monte Carlo Method
26. Cache Memory And The Caching Principle
27. Data Compression The Dictionary Way
28. Dates Are Difficult*
29. Sequential Storage*
30. Magic of Merging*
31. Power of Operators
32. The Heart Of A Compiler*
33. The Fundamentals of Pointers
34. Functional And Dysfunctional Programming*

* Recently revised

This is a beginners informal introduction to some of the common data structures. Think of it as the least you should know about data structures with a few comments about object oriented programming along the way - but the main focus is on data.

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! (With apologies to functional, logic and other types of programmer who might be reading this.)

To paraphrase a well known quote:

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

Ok I'm partly joking as there are other approaches to programming but none so all pervasive and accepted.

If you want to know more about the connection between objects and data structures then see Data Structures Part I - From Data To Objects.

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.

The stack

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 - see later) 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:

var Stack[];
var Pointer=0;

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. This sort of error is often used to break into a computer system. If you can cause a "stack overflow" then the stack pointer might end up pointing out side of the allocated area or memory and might point at some other program's data. A stack overflow can be used to inject rogue code into a program and so take over the machine. 

If you would like to know more about stacks then see:  The LIFO Stack - A Gentle Guide

<ASIN:0201000237>

<ASIN:0534491820>

<ASIN:1584502509>

<ASIN:0521670152>