A Playdate With Some Python Stacks

What up, you data dork!

Today I’m talking about the good ole data structure everyone loves – stacks.

I mean, who doesn’t love them, right?

Okay, okay, there’s a reason for talking about this madness right now.

I’m reading The Self-Taught Computer Scientist right now, and there are five important ideas regarding stacks.

1. Creating a stack using an array
2. Creating a stack using a linked list
3. Reversing a string with a stack
4. Creating a MinStack to track the min element
5. Using a stack to find balance in a string (read for more on this)

Let’s get into the juicy stuff now…

1. Creating a stack using an array

I wouldn’t call myself a Python Pro yet, but I’ve been using the language enough to become a list ninja. They don’t scare me one bit…

So recreating this first stack class felt like writing down my name…

2. Creating a stack using a linked list

Remember how I said I’m a list ninja? Well, err, that’s not true if it’s a linked list.

Yeah, I understand how they work and can (kinda) make one myself, I’m far from a Linked List Pro.

But that doesn’t mean I’d skip recreating this class…

I may have referenced the book a few times for this, but doing so made me build a better understanding of linked lists and stacks.

So screw it!

I didn’t cheat. I learned.

3. Reversing a string with a stack

Okay, this one’s giving me a bit of PTSD from my sophomore year Intro to Comp Sci class.

I remember having an extra credit problem once where the professor ruthlessly challenged me to reverse a string in three different ways. And frankly, I couldn’t even do it in one way.

But that’s a story for another time…

I couldn’t help but chuckle when I saw that old challenge show up in this book.

And guess what…

I still can’t reverse a string in three different ways. But I can do it in two different ways! So, it’s not a total loss…

Anyway, here are three ways to reverse a string (with the last method incorporating a stack).

4. Creating a MinStack to track the min element

This is one cool cat… I mean, cool class.

It allows you to track the minimum value in your stack at any point.

After reading this chapter, I was kind of able to recreate this from memory but needed to reference the book for the push function…

5. Using a stack to find balance in a string

Last but not least, we’ve got this doozy of a problem.

This, too, gives me some gnarly PTSD.

I discovered LeetCode a few weeks ago, and the crazy data dork in me decided to try a problem that checks if the parentheses, square brackets, and curly brackets are balanced in a string.

Let’s just say…

I never solved the problem. It was too much for a Python Noobie like me.

But now that I know stacks, I’m prepared.

After giving it a second shot, I *almost* solved the problem on my own. I ended up needing a little boost at the end, but I came up with this method here…

(notice the sexy use of a hash map too)