Picture any structure you can think of: A maisonette, a bungalow, a cottage, a cowshed, a skyscraper, a dormitory, a cathedral, a mosque, an apartment, a barn, a silo, a warehouse, a mall, even a small camping tent. They are all just arrangements of spaces meant to organize people/things in a manner befitting of their purpose for being there. Some are bigger, more permanent and complex. Some are smaller, simpler, and easier to build. It all depends on the problem you're trying to solve.

Data Structures are kind of the same. You can think of them as arrangements of space to organize data in a manner befitting of its purpose for being there. Data is stored on your computer so that you can retrieve it whenever needed and manipulate it for the specific tasks at hand. These 2 things: the nature of the data and the nature of the task you hope to accomplish with the data largely determine the type of data structure you use to store your data.

There are many types of data structures, some more complex than others just like man-made structures. If you've read some of my previous articles you have already come across a data structure called arrays (a collection of similar items stored in one contiguous block of memory). Other fascinating data structures they teach during week 5's lecture are linked lists, binary search trees, hash tables, associative arrays(dictionaries), queues and stacks. Some of these structures are quite tricky to implement. If you mess up the pointers on linked lists for example you might end up with a meme:

Let's talk about the last 2 (queues and stacks) which are fun and easy to understand:

Queues and Stacks

Juja folks are already in panic mode thinking about the SuperMetro queues 😅

Queues work with a FIFO policy; First In First Out. If you came in first, you ought to get served first, and that's why we secretly (some not so secretly) curse those people who try to skip queues. Stacks on the other hand work with a LIFO policy; Last In First Out. Think of a stack of biscuits in a box; the biscuit that was put in the box last will be the first to come out. Another example of a stack is browser history. When you click on the back icon, you go to the page that was added to the history list last.

An interesting analogy was used here which I think some guys will relate to...

Muthomi always has the same black t shirt on. Some people call him 'black t-shirt guy' behind his back. Kamau, worried that his friend Muthomi might forever be the black t-shirt guy decides to intervene. He goes to Muthomi's home and asks to see his wardrobe. He finds that all his clothes are arranged in one big stack.

"Why do you always wear the same t-shirt Muthomi?"

"Um, I don't know, it just happens. Every evening, I wash it and when it dries I fold it and place it on top of the stack of clean clothes. Later, when it's time to dress up I just grab whatever is at the top of the pile and head out."

"Aah! I see where the problem is. Let me show you a better way. Get enough hangers for each of your clothes and hang them up on the rack. From tomorrow, pick the clothes on the left end of the rack as your outfit for the day. In the evening, when they are cleaned and dried, hang them up on the right side of the rack. Your wardrobe is now in a queue structure!"

"Oh wow! I had never though of that. You have changed my life forever!"

(Kamau holds his cowboy hat in a subtle nod, mounts his horse and slowly rides off into the sunset. His job here is done.)

Speller Problem Set

In this problem set, you're meant to implement a program that checks the spelling of words in a text file in the fastest time possible. A lot of the distribution code has already been done for you but the main part of the assignment is to implement a hash table data structure to quickly cross-check all the words in a text file against the words in a dictionary.

Admittedly it sounds quite easy but this was the toughest problem set yet! I think they make it very complex and tedious as a crescendo to the 5 difficult weeks of C programming. It is the cherry on the cake before switching to python in week 6.

Stay tuned as we finally get back to Python on Episode 7!