Data Structures Part II - Stacks And Trees

Page 1 of 3Part 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.

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 stackA 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.
Source