Data Structures & Algorithms: A Beginner’s Guide to Stacks

Photo by Ajda ATZ on Unsplash

To kick off my learning about stacks, I decided to hit the stacks and take a book off of my stack for reference. (We’re leaning into this stack thing, I’m not sorry). I found Cory Althoff’s The Self-Taught Computer Scientist to be extremely effective and beginner-friendly for learning about this concept. Most of the examples provided in this article have been translated from the original Python in Chapter 11: Stacks.

The following is a summary of what I’ve learned and what I’ve found most helpful as a beginner. I hope you’ll find it helpful, too!

📊 Data Structures: The Basics

Before we get into stacks, let’s talk about data structures in a more general sense. Data structures & algorithms (colloquially known as DS&Algos or DSA) tend to loom over the heads of new developers as scary and unknown territory. They can have the effect of encapsulating within four words all of the many things we know that we do not know. But this is really what makes up programming on a fundamental level, and defining the concept makes it a little less intimidating:

The algorithm tells your computer what to do, and your data structure tells your computer how to store the data from your algorithm.

– The Self-Taught Computer Scientist, Chapter 8

That’s it. At the most fundamental level, data structures are for visualizing (and then implementing) the storage of data. Algorithms access and manipulate those data.

Some helpful vocabulary from Chapter 8:

• Data structure: A way of organizing data in a computer so programmers can effectively use it in their programs.
• Linear data structure: A data structure that arranges data elements in a sequence.
• Nonlinear data structure: A data structure that links data nonsequentially.
• Static data structure: A data structure with a fixed size.
• Dynamic data structure: A data structure that can grow or shrink in size.

In a dynamic data structure, the computer allocates additional memory as additional elements are added to the structure, and when you remove an element the computer frees that memory to make space for other data. Stacks can be considered dynamic data structures in certain contexts, but it depends on the specific implementation. Memory allocation and optimization are a little outside of the scope of what we’re talking about here, so don’t worry too much about that for now:

Unless you are writing low-level code for an operating system or some other project where you have to squeeze out every possible performance optimization, you most likely will not spend a lot of time thinking about choosing a static or dynamic data structure. Instead, you will probably spend more time deciding whether you should use a linear or nonlinear data structure and, once you’ve made that decision, which linear or nonlinear data structure to use.

– The Self-Taught Computer Scientist, Chapter 8

🔍 Choosing the Right Data Structure

According to Althoff, “The best data structure to use in a program depends on what type of problem you are trying to solve and what you are trying to optimize for.” (Chapter 8)

It follows, then, that to determine which data structure to use for a given problem, we must understand the potential advantages and disadvantages of each one. Seeing data structures in different contexts & applications through practice helps us to increase confidence and an understanding of their pros & cons.

These pros and cons are mostly related to their efficiency in inserting, deleting, searching, and sorting data and how efficiently they use memory space.

– The Self-Taught Computer Scientist, Chapter 8

🥞 Stacks: The Basics

A stack is an abstract data type and a linear data structure from which we remove only the most recent element added.

Across the literature, the most common real-world examples for conceptualizing this data structure are a stack of books, a stack of dishes, or a stack of pancakes. If you had a stack of books and wanted to take a book from the middle of the stack, you would first have to remove all the books stacked on top of it. Ditto eating pancakes.

So… This is about the point where my chaotic evil twin says, “But you could technically remove a book from the middle of the stack, or stab a few pancakes at the top of the stack with a fork and remove the middle one with your free hand. And what about Jenga? Hmm?” 😈

Chaotic evil twin says: “Yeah, see! You could do this!”

Okay, chaotic evil twin, you are very creative. However, those processes would be represented by a different data structure entirely. And structure is the point. Data structures are useful because we can rely on them to behave in very specific and logical (you might say structured) ways.

📚 Stacks: Key Principles

The main principles you need to understand when it comes to stacks:

1. Last-in, first-out (LIFO). The last element you put into the structure will always be the first item to come out. No exceptions.
2. Because you need to follow the LIFO principle, a stack is therefore a good example of a limited-access data structure. Limited-access data structures require you to access their elements in a particular order.

Source

🛠️ Stacks: Expected Behaviours

Stacks typically define a certain set of expected behaviours:

1. Pushing and popping are the two primary operations. You’ve likely come across these terms in working with arrays, but to recap: to push is to add an element and to pop is to remove an element.
2. Peeking is another common operation defined within a stack. Peeking, in this context, means looking at the topmost element in a stack (without removing it).
3. A stack can be bounded or unbounded. This means, respectively, that we can limit the number of elements that can be added… or not.

If a stack is unbounded and the computer’s memory capacity is exceeded, we have stack overflow. (Yes, this is where the website gets its name).

Some fun Stack Overflow history here 😜

🤔 Stacks == Arrays?

When I first learned about stacks, it seemed to me that we were really just talking about arrays. Arrays have push and pop methods, it’s relatively easy to “peek” at the last item in an array… So why do we need stacks? Are we just extending an existing structure?

There are some key differences between arrays and stacks:

1. Stacks are a limited-access data structure. We could technically iterate through an array from index 0 to index -1, but we could also go from -1 to 0, meaning that arrays do not follow the LIFO principle. Stacks limit these behaviours because that is what makes them useful: we know that we can only read or remove the last item on the stack. Even if internally stacks are represented by an array (they can also be represented by a linked list), they represent a class distinct from arrays with unique behaviours in and of themselves.
2. Stacks give us an opportunity to extend or limit the behaviours typically associated with arrays through the methods we define.
3. Creating a stack allows for abstraction and encapsulation of behaviours, both of which are core principles of Object-Oriented Programming.

⏱️ A Note on Time Complexity and Efficiency

Each operation on a stack is O(1). They are quite efficient in adding and removing data; however, if a problem requires us to access data throughout the entire stack, they would not be the best choice of data structure.

If you were to print each element within a stack, this would be O(n) (where n represents the total number of elements in the stack). In this situation, time complexity grows linearly based on the number of elements in the structure.

If we are popping elements off of a stack, we might recreate that same stack in reverse order. One option for working with stacks is to append popped elements to a temporary/holding stack. Then, you can print each element as you pop it off of the temporary stack and append it back to the original. Storing data in a temporary stack requires more resources; we can represent this operation’s time complexity with O(2*n), meaning it takes twice as long as it would to simply print the elements in reverse order.

Stacks come with a cost: memory. For every item we place on the stack, we allocate a stack frame to it. Think of an array index. Each index is allocated space to hold something. If we keep adding and adding to a stack, we hold the possibility of running out of space, like a parking lot that is full. When that happens, we have an overflow, hence, the term “stack overflow”. This can lead to crashes and stuck processes.

– freeCodeCamp

💻 Usage

However simple they may be, stacks are one of the most frequently used data structures in computing. A few examples:

• Run-time systems for programming languages (Python, Java, JavaScript…)
• Backtracking algorithms in machine learning and AI
• Compilers use stacks to parse expressions, as with standard arithmetic— particularly expressions involving nested pairs of parentheses. Keep this in mind, as it’s a user-friendly example I’ll cover later on.
• Programs that have “undo” and “redo” functions (web browsers and their ability to move backward and forward through a user’s browsing history, word processors, code editors, etc)

If you’re interested in how Ctrl + Z is implemented, Stack Exchange (🤓) has a really interesting overview explaining why it is often limited.

👩🏼‍💻 Let’s Write Some Code!

The best way to understand stacks is to see them at work. I decided to translate the examples from The Self-Taught Computer Scientist from the original Python to Ruby both for practice and because Ruby is an object-oriented language that I have more experience with. The code translations can be found in my GitHub repo for this article and I’ve included snippets below so that you can run the code in IRB. Let’s do this!

Basic Stack Structure

In this example, we can see all of the expected components of a stack: we have our push, pop, and peek methods, with additional methods to check the size of the stack (size) and to check if the stack is empty (is_empty). The stack, as defined in this class, keeps track of its elements with an array (items). We can clearly see how this class simplifies and abstracts functionality to align with what is typically expected of a stack:

class Stack
  def initialize
    @items = [] # @items is a private instance variable, which is what we
                # want: stacks should not be directly accessible outside 
                # of the class.
  end

  def push(data)
    @items << data
  end

  def pop
    @items.pop
  end

  def size
    @items.length
  end

  def is_empty
    @items.length == 0
  end

  def peek
    @items[-1]
  end
end

stack = Stack.new

puts stack.is_empty # => true

stack.push(1)
stack.push(2)
stack.push(3)

puts stack.size # => 3
puts stack.peek # => 3

# Here we see that stack.pop has taken the topmost element from the array:
popped_item = stack.pop
puts popped_item # => 3

# The stack has now decreased in size and the topmost element is 2:
puts stack.size # => 2
puts stack.is_empty # => false
puts stack.peek # => 2

Stack for String Reversal

In technical interviews, it is not uncommon to be asked to reverse a string using multiple different approaches. One approach might be to use the methods already built into a given programming language. Stacks are another great option for this problem because, as we’ve learned, characters are popped off the stack in reverse order:

def reverse_string(string)
  stack = []
  reversed_string = ""

  string.each_char { |c| stack.push(c) }
  string.each_char { reversed_string += stack.pop }

  reversed_string # The reversed string is returned here
end

puts reverse_string("stressed") # => desserts
puts reverse_string("🌮 tacocat 😸") # => 😸 tacocat 🌮

Min Stack

The purpose of a min stack is to keep track of the smallest element of the stack at all times. This is helpful both for technical interviews and various situations in day-to-day programming. We can accomplish this with two stacks: a main stack and min stack. The main stack’s role is to keep track of all the push and pop operations, while the min stack’s role is to hold the smallest element at all times. I’ll go through this one step-by-step following the complete example:

class MinStack
  def initialize
    @main = []
    @min = []
  end

  def push(n)
    if @main.length == 0
      @min << n
    elsif n <= @min[-1]
      @min << n
    else
      @min << @min[-1]
    end

    @main << n
  end

  def pop
    @min.pop
    @main.pop # returns this value
  end

  def get_min
    @min[-1]
  end
end

minstack = MinStack.new

minstack.push(3)
minstack.push(4)
minstack.push(5)
minstack.push(2)
minstack.push(1)

puts minstack.get_min # => 1

minstack.pop
puts minstack.get_min # => 2

minstack.pop
puts minstack.get_min # => 3

Let’s break this down a little bit. First, the push method:

  def push(n)
    # ----- Step 1: -----
    if @main.length == 0
      @min << n
    # ----- Step 2: -----
    elsif n <= @min[-1]
      @min << n
    # ----- Step 3: -----
    else
      @min << @min[-1]
    end
    
    # ----- Step 4: -----
    @main << n
  end

Step 1: If main is empty, we automatically push the provided value (n) to min because no matter what the value is, it is–as the initial value–the smallest number in the stack.

Step 2: If main is not empty, we check the provided value (n) against the topmost value of min (min[-1]). If n is less than or equal to the topmost value, we push it to min.

Step 3: In the case that n is greater than the topmost value of min, we duplicate the current minimum value at the top of the stack. This ensures that the number of values in min is reflective of the number of items in main.

Step 4: We will always add the pushed value (n) to the main stack.

The pop method pops the last value from both main and min, because if a value is no longer in the main stack then it does not need to be tracked by the min stack.

Finally, get_min is essentially our peek method for the min stack.

Stacked Parentheses

I love this example. I think this is where the concept (and its usefulness) started to really click for me. The purpose of this function is to check for balanced parentheses, meaning that for every opening parenthesis, there should be a closing parenthesis.

People often make the mistake of using a counter to check if there are equal numbers of opening and closing parentheses. Where this approach becomes problematic is when we have a string like “ ) ( ) ( ”. While equal in numbers, the parentheses are not properly closed. Let’s walk through the solution with a stack.

def check_parentheses(string)
  stack = []

  # ----- Step 1: -----
  string.each_char do |c|
    # ----- Step 2: -----
    if c == "("
      stack.push(c)
    # ----- Step 3: -----
    elsif c == ")"
      return false if stack.length == 0
      stack.pop
    end
  end
    
    # ----- Step 4: -----
    stack.length == 0
end

puts check_parentheses("(This should return true (all brackets close))") # => true
puts check_parentheses("(This should return false") # => false
puts check_parentheses(")( )(") # => false

Step 1: We iterate through each character of a given string.

Step 2: Each time we encounter an opening bracket, we push it to the stack.

Step 3: If we encounter a closing bracket, we check to see if there is an opening bracket on the stack. If there is not, we return false as we know that we do not have balanced parentheses. If there is, we pop the opening bracket from the stack and continue checking characters.

Step 4: If, by the end of our checks, the stack is empty, our statement will resolve to true (balanced parentheses). If it is not empty, that means it contains an opening bracket that has not been closed, and our statement therefore resolves to false (unbalanced parentheses).

📞 The Call Stack

How are stacks related to call stacks? Let’s see what MDN has to say:

A call stack is a mechanism for an interpreter (like the JavaScript interpreter in a web browser) to keep track of its place in a script that calls multiple functions — what function is currently being run and what functions are called from within that function, etc.

• When a script calls a function, the interpreter adds it to the call stack and then starts carrying out the function.

• Any functions that are called by that function are added to the call stack further up, and run where their calls are reached.

• When the current function is finished, the interpreter takes it off the stack and resumes execution where it left off in the last code listing.

I find this easier to conceptualize if I’m thinking about order of operations in math (as well as the stacked parentheses problem). If we think of an opening parenthesis as a function call and we know that a function can encapsulate other functions, we need to execute those other functions before we can return the value of the outermost function in its entirety. Each opening parenthesis requires that we locate its closing parenthesis and resolve what is contained between them (even if that means nesting further and further down). Here’s a simple example:

def add_three(n)
  n + 3
end

def multiply_two(n)
  n * 2
end

def subtract_one(n)
  n - 1
end


add_three(
  multiply_two(
    subtract_one(10)
  )
) # => 21

Beginning with the innermost call, we get 9:

    subtract_one(10) # => 9

Then, moving outward to the next set of parentheses (carrying the resulting 9 from the innermost function call), we get 18:

  multiply_two( # 9 * 2 => 18
    subtract_one(10)
  )

Finally, we move to the outermost set of parentheses, adding 3 to our 18 to get a final return value of 21:

add_three( # 18 + 3 => 21
  multiply_two(
    subtract_one(10)
  )
)

Let’s visualize this as a call stack with the Last In, First Out rule:

Remember how I was talking about Ctrl + Z? I used it a lot while creating this image 😅

The MDN documentation for call stacks has another great example of how a function is executed via call stack.

🔁 The Event Loop

If you’re working with browsers, you’re working with JavaScript’s event loop. The JavaScript event loop is a topic worth exploring all on its own, but it’s important to give a brief overview here and to connect this concept (stacks) to the event loop as it is an integral part of its functionality. The JS event loop makes use of a stack for keeping track of function calls with just a few layers of added complexity:

Source: Rahul Sagore (CodePen)

(This is an extremely high-level explanation of the event loop as I’ve chosen to focus on stacks more generally).

In addition to the stack, your browser’s JavaScript engine (V8 in the case of Google Chrome) makes use of a callback queue for asynchronous function calls. The short and sweet explanation for the callback queue is that this is where V8 places all of the script’s asynchronous calls, meant to be non-blocking. This ensures that these calls do not force other functions to wait around while they retrieve data from another server, for example. Rather than hanging out at the top of the stack and blocking all the other functions below, asynchronous calls are sent to the callback queue.

🎬 Conclusion

While I felt overwhelmed in approaching this topic initially, I have consistently found that the best thing for building confidence (as much as we are sometimes loathe to hear it) is practice. If you’re studying a new data structure, this is what I’d recommend:

1. Find a reputable and accessible source of information
2. Limit your read of the theory to a general introduction
3. Study examples (in code) and practice writing your own

It’s okay to feel overwhelmed at the start, and it’s okay to talk about feeling overwhelmed. The key is to break things down step by step and practice. You will eventually find yourself more at ease with the concepts if you keep going. Happy coding! 😊

Main Sources & Further Reading

The Self-Taught Computer Scientist: The Beginner's Guide to Data Structures & Algorithms

A Gentle Introduction to Data Structures: How Stacks Work

Data Structures 101: Stacks

How to Use the Stack Data Structure to Solve Coding Challenges