Just another Duke WordPress Sites site

Category: Data Structures

Data Structures in Real Life: Stacks

Stacks

Have you ever used a text editing document (e.g. Microsoft Word, Google Docs) to write an essay? In this situation, it is useful to be able to keep track of the last several commands you performed. That way you can simply back out of a mistake (or mistakes) and “undo” them when applicable. 

How do we keep track of the last several commands performed though? 

We can use a stack! 

Introduction (Beginner):

A stack is a data structure used to store a bunch of data, and then access the data in the opposite order that the data was stored. This process is commonly described as “last in, first out”, or LIFO. 

You can think of a stack as a pile of books placed in vertical order. When we’re piling the books up, we first place (push) book 1, then book 2 on top of book 1, and finally book 3 on top of book 2. Now in order to retrieve book 1, we need to first remove (pop) book 3, then remove book 2. This book analogy illustrates the “last in, first out” nature of the stack data structure – the last book that is placed (pushed) on the pile is the first book to be removed (popped).

Examples (Intermediate):

Now let’s see how a stack can help us undo mistakes in a document-editing scenario. 

Imagine you are an elementary English teacher planning a vocabulary lesson for your first grade students. You start off by writing “cars”, “dogs”, “cats”, then “ICT” on a word document. You suddenly realize that “ICT”, short for Information and Communication Technology, probably shouldn’t be on the vocabulary list for a first-grader. Luckily, you hit the undo button on Google Docs, and “ICT” disappears. This process can be modeled by a stack. As you record the terms, “cars”, “dogs”, “cats”, and “ICT” are pushed onto the stack one by one. When you hit the undo button, you are essentially popping off the most recent word you added to the document (“ICT”) from the stack. 

There are so many more real-life examples of stacks, such as car decks, cafeteria trays, and breakfast pancakes.

The “back button” on a web browser is also an excellent example of stack implementation. When a user visits a new web page, the current page is pushed onto the stack. When the user clicks the “back button”, the last page pushed onto the stack is popped off and loaded into the browser window. When all the pages are popped off of the stack, the back button will gray out, signaling that the stack is empty. The “forward button” works in a similar but slightly different way. While clicking the “back button” pushes the current page onto the stack, clicking the “forward button” pops the top page off the stack. When you visit a new page without clicking either button, the forward button stack is automatically emptied. In class, I usually run through a web demonstration of clicking a series of back buttons and forward buttons to better illustrate how stacks work. 

Memory (Advanced):

If you have some experience in programming, you’ve probably used “Stack Overflow”, a Q&A website for software development. But what exactly does the term “stack overflow” mean in Computer Science? The “stack” here refers to the memory stack, which stores data in a computer’s memory. In computer programs, the memory stack stores local variables contained by a function. Since it is fixed in size, the memory stack is designed to be temporary – when computational tasks are complete, the memory of the variables are automatically erased. 

A stack overflow is a run-time software bug when a program attempts to use more space than is available on the memory stack, which results in a program crash. The most typical case of a stack overflow error happens when your code executes an infinite or very deep recursion (a function invoking itself). Whenever a function is invoked, some part of the stack memory is consumed. Since the memory stack is fixed in size, once all the memory is exhausted with consecutive recursive function calls, a stack overflow error will be thrown. Note that a stack overflow error should be differentiated from a run-time error, which is typically caused by an infinite loop. 

Conclusion: 

From organizing books and undoing document changes to navigating with web browsers and utilizing computer memory, stacks are more relevant to our daily lives than you think! 

Data Structures in Real Life: Arrays

For those who don’t have a Computer Science background, computer programs might seem like far-fetched wizardry. When I took my first Duke CS course, Data Structures & Algorithms, I also had a difficult time wrapping my head around the numerous ideas introduced throughout the course. At the time, data structures (e.g. linked lists, binary trees, stacks, queues) seemed abstract and confusing to me. Looking back, data structures (and CS in general) are so much more relatable to our daily lives than I used to think! As a programming instructor this summer, I want to make sure that my students can realize this sooner. Given this goal, I began to think: How should I teach data structures? 

“How do we access an element in a sorted array?” 

A few hands go up hesitantly…

“How do we look up a page in a book?” 

Most students are willing to share!

When the vocabulary is technical, students are less likely to trust that they know the answer, even when they actually do. Putting technical ideas into familiar, real-life settings effectively reduces the fear associated with classroom discussion. Thus, when I’m introducing new data structures, I make sure to draw on plenty of analogies to simplify abstract concepts and encourage further discussion. Since students are more likely to personally connect with these everyday examples, I find that they have a much easier time comprehending and implementing data structures in code later on.

In the following weeks, I will be introducing several important data structures with the examples I frequently use in class. Let’s start with arrays!  

Arrays

Introduction (Beginner):

Arrays are the simplest and most widely used data structure. Other data structures, such as stacks and queues (which I’ll explain later) are derived from arrays. Because arrays are so prevalently used in programming, they often are amongst the first data structures students learn in an introductory CS course. 

Below is a simple array of size 4, containing elements 1, 2, 3, and 4.

You can think of an array as a row of boxes with each box capable of storing a single element. The type of element that is stored in each box within the array needs to be the same. In other words, if the one box stores a number (i.e. int, double), the other boxes cannot store words (i.e. Strings) because all the boxes within the array need to be consistent in type.  

Each element is assigned a positive numerical value called an index, which corresponds to the position of that particular element in the array. Note that array indices typically start at a value of 0 (starting from 0 instead of 1 is a recurring theme in CS). 

There are two major types of arrays: 

  • One Dimensional Arrays (as illustrated previously)
  • Multi-Dimensional Arrays (arrays within arrays, or nested arrays) 

You can picture a two-dimensional array as a table made of rows and columns, such as a spreadsheet. Since two-dimensional arrays can be a little confusing for beginners, I like using an empty egg carton to demonstrate how a two-dimensional array is traversed. 

 

In a two-dimensional array, each row represents a distinct array of elements. As pictured above, the carton (array) holds two rows of eggs (elements), so it contains two distinct arrays, specifically {0, 1, 2, 3, 4, 5} and {6, 7, 8, 9, 10, 11}. In class, I have students place pieces of candies into different spaces of an egg carton to simulate a piece of array-accessing code step by step. And yes, they get to eat the candies afterwards!

 

Memory (Intermediate):

To understand how arrays work on a low level in memory, you can think of an array as a group of apartments (elements) side by side in an apartment complex (the array). Each apartment has an associated address number (memory address) at its front door. For instance, if the first apartment has an address number of 1000, then the second apartment will have an address number of 1001, and so on. Following this logic, we know that the fifth apartment will have an address number of 1004 and the tenth apartment will have an address number of 1009. A similar phenomenon happens in arrays. Since the elements of an array are stored in contiguous memory locations, if the memory address of the first element of an integer array is 1024, then the memory address of the fifth element will be 1024 + 4*4 ( the size of an integer element is 4 bytes) = 1040. This means that as long as we keep track of the memory location of the first element of the array, we can find any element in the array with a quick calculation (see below).     

Dynamic Array (Advanced):

Unlike static arrays (what we’ve covered so far), which are initialized with a fixed memory allocation (e.g. 10 integer elements; int[10]), dynamic arrays automatically grow when the programmer tries to make an insertion and there is no more space left for a new element. 

How does this iterative resizing process work? Whenever there is no more space to add a new element, a new array is allocated and each element from the original array is copied to the new array. To avoid incurring the cost of resizing many times, dynamic arrays resize by a large amount, such as doubling in size (as illustrated above), and use that space for future expansion. The old array, which is now useless since everything is copied to the new array already, is deleted (memory is freed). As you can see this is a relatively costly process, but resizing doesn’t happen every time you append an element to the original array. Resizing only occurs when the original array is full of elements and thus out of memory.  For those who understand Big-O Time Complexity, appending in dynamic arrays is O(n) instead of O(1) (appending in static arrays) because of its additional infrequent resizing process.

Interestingly, the resizing process in dynamic arrays can be compared to the process in which hermit crabs find new shells. As a hermit crab grows bigger, its shell becomes an ever-tighter fit so eventually the crabs need to move into a bigger one. As more elements are appended to a dynamic array, the array’s pre-allocated memory gets increasingly filled until the last space eventually gets filled, prompting it to resize. This fun analogy helps students better understand the logic behind resizing. 

Most modern programming languages have built-in dynamic arrays (e.g. ArrayLists in Java and lists in Python). However, to illustrate how a dynamic array is specifically implemented, here’s code for a dynamic array I wrote from scratch using Python:

Conclusion:

Whether you’re a beginner, intermediate, or advanced programmer, I hope you gained new perspectives on arrays after reading this post. Stay tuned for next week’s post on stacks!