Many years ago, the Swiss computer scientist Niklaus Wirth wrote a book titled Algorithms + Data Structures = Programs. Wirth wrote that a program is formed from a set of algorithms that are based on particular representations and structures of data. Wirth’s formula for writing a computer program is to start with the proper representation and structure of the data, which when followed by a set of algorithms that act to manipulate and transform the data, lead to a successful computer program. A computer program will not be successful if the data structures underlying it are faulty or insufficient.
Choosing the proper data structure for a problem is often the key to finding a good solution to a problem. More importantly, choosing the wrong data structure can make some problems almost impossible to solve. For example, if the goal of a program is to be able to search a data set quickly, storing the data as objects in memory is probably the wrong choice. Learning the proper use of data structures will keep choices like this from being made.
An example of a data structure that lends itself to efficient solutions is the stack. A stack is a list that only allows access to the top element of the list. You can add new piece of data to the stack (called a push operation), and you can remove the top element from the stack (called a pop operation). The only other major operation allowed is a peek, or view, operation to examine the top element of the stack.
What are stacks used for? In computer science, stacks are used to implement function calling in programming languages, and in computer architecture hardware stacks are used to allocate and access memory. There are many more uses for stacks in computer science, but let’s focus on the use of stacks for more day-to-day tasks.
One good use of a stack is to convert a number from decimal to binary. The algorithm is quite simple: take the number you are converting modulus 2, and push that result on the stack; divide the number by 2, and go back to the previous step while the number is greater than 0. To get the converted number, pop off all the elements of the stack until the stack is empty.
Here’s another stack example: parentheses balancing. Scan an expression and push each left parenthesis and its position onto a stack. When your scanner gets to a right (closing) parenthesis, pop the stack. An unbalanced expression will have a parenthesis left on the stack after the full expression is scanned.
Effective Binary Search Trees
Another data structure that lends itself to very efficient algorithms is the binary search tree. A tree is a data structure where each data element is stored in a node, with the first node being the root node, and nodes below it are child nodes. In a binary tree, each parent node can have exactly two child nodes, one to the left of the parent and one to the right of the parent. In a binary search tree, there is a further rule that child nodes must be ordered with smaller values stored in the left child node and greater values stored in the right child node.
When a binary search tree is fully formed, you can find the minimum value of any data set by following the left child nodes to the bottom of the binary search tree, and the maximum value is found by following the right child nodes to the bottom of the binary search tree. This leads to a huge performance gain over searching through an unsorted data set.
Add to Your Toolbox