The Secret to Mastering Queue, Stack and Dictionary in C#!

One of the things that makes me sad when I'm reviewing code is seeing people overuse list. It's a great type, but a lot of times it's not the best choice for your use case. My name is Michael Jolley and I'm the bold bearded builder. And today we're gonna demystify three classic data structures in C. We'll talk about how they think, where they shine in real world code, and maybe some modern C tips so that your future self doesn't file a bug report against you.

Now the first one I wanna talk about is a queue. And the way queue works is it's a first in first out. That means like your grocery store line, you pull up with your buggy or cart or whatever you call that a bin maybe. Anyway, you pull up with your groceries. If you're the first one in line, you're the first one that checks out and gets delete.

If you pull up and you're the second one in line, someone else is going first and then you. First in, first out. You know how queues work and appropriately named queue is the type. Now we've got the subscriber class. I just created that as something we can play with, but we can say var waitlist equals new queue, and it's a queue of type subscriber.

And we can say waitlist dot enqueue because that's how we add things to our queue. We enqueue it appropriate names, right? New subscriber, we'll say first name equals Ada because that sounds appropriate. And I'm gonna copy and paste that a couple of times. We'll say grays and maybe Linus, even though I'm using windows.

And let's see, now we've got a list with three and if we wanted to get those out, we would, if we enqueued, we dequeue. You've got how this works. And the nice thing is we can go a while and say waitlist dot count is greater than zero. And this works great because dequeue actually doesn't just give you back the first out. It actually removes it from the list.

So as you're pulling it, it's cleaning it up. So the count of that waitlist is getting shorter so that you can do a while like this. So we can say var next up equals waitlist dot deque, not default of empty dequeue, and then we'll say console. Writeline, and we'll just do something like now serving, we'll say nextup. Firstname, and yeah, do all that.

Now, if we run this, we can go see .net run. We should get now serving Ada, Grays and Linus. Works just like we'd expect that wait list gets queued up with things and then they get de queued with things. But maybe sometimes we don't wanna necessarily pull the thing out of the list. We don't wanna get ADA.

We just kinda wanna know who's next. For that we can use Peek. Check this out. We can just close that terminal down. Now that we've got things in the list, we'll just do a real quick console.

Writeline and we'll say, just log out waitlist. Peak. First name. Actually peak is a method. I gotta make it a method first name.

There we go. And then now if we run it, let's clear this and dot net run. We should get it to write Ada and then it goes through that list that while to do that's now serving works like we'd expect and it's fantastic. But there's a big gotcha with peak and with dequeue. If you call those methods when the queue is empty, it's gonna throw an exception.

Actually, it's an invalid operation exception. But luckily if you're using dot net six and beyond, you get new methods like try and queue and try peak. And if you're not using those, well, our thoughts and prayers are with you. Hope you can get that upgraded at some point. Well, let's try those out.

The nice thing about try DQ and try peak is they return a Boolean. So we can say if a waitlist dot try DQ out VAR served, then we can say console. Writeline. Let's just do that served. Let's just write their name, first name.

There we go. Net try to queue is gonna run it and happen just fine. And then we can actually do an if here, like if there wasn't something we could say, console, console dot right line, no one left, right? Now we probably have this in some kind of loop, but you get the idea here that if lets us know if there is one and inside it, we can actually do something with it because it will dequeue it. And we run that it'll it'll run it'll just do do ADA because we don't have it in a list.

Right? But we'll still get ADA's name written there as we hope we would. So when in the real world would you wanna use a cue? When you need predictable order and fairness. You could always use the non generic cue but that's gonna trade type safety for flexibility.

And honestly, in most modern code, you're always gonna wanna use the queue of type T. One bonus tip. Well, if you have multi threaded producers and consumers look at the concurrent queue type in the system collections concurrent namespace. That's a mouthful. It has lock safe in queues and tri deque for all your concurrent work.

Next up are stacks and they work on a last in first out basis. That's kind of like an undo button or your browser's back button. The last one in is always the first one out. Does that make sense? I hope it does because I can't explain it any better.

But let's simulate that with maybe navigation history in a browser. So if we said var history equals new stack of string, let's say, And then we said history. How do we get it in? Is it in queue? No, it is push.

So we'll go push a new string and maybe it's like slash home. And then maybe we navigated to push, let's say productsproducts because we gotta be official with this. And then maybe there was history. Push the shopping cart, right? Now, if we want to get one of those out, remember it's last in first out.

So the last in was cart. We would do history. Pop, right? And we can actually say var last in equals history dot pop. And when we do that, we can say console dot writeline.

Let's just do last in dot Oh, it's just a string. So we just do that. Open up the console.net run, and we should see it just write out that slash cart because it was the last in first out. Now, if you're immediately thinking, well, wait, if pop is like DQ and push is like NQ, Is there some kind of peak for a stack? Well, friend, you're on the right track and it's called, you'll never guess, peak.

So we can bring up that same thing and say history. Peak. And then look at that try peak. It's kind of a spoiler there in my IntelliSense, isn't it? Because now when I run this, you're gonna see it's gonna still have that slash cart because that is the last, it's just not gonna take it out.

But as you saw, just like a Q, we do have a Tri Peak and a Tri Pop so that you can do that with safety because yes, calling pop and calling peak on a stack with nothing in it is gonna get you the same invalid operation exception. So where does stack shine? We've already talked about them being good with undo and redo buffers, but they're also great at depth first searches like graphs and trees. They're really solid as well with expression evaluation and parsing. Heck, if you've ever seen a stack trace, I'm sure you haven't because you don't write bugs.

But if you had, you've seen a stack. But let's look at an even cooler example. If we check out this method up here, it's actually checking to make sure that parentheses are balanced within the string. Now you could see that as part of a code parser or something like that, but it's pretty sick, right?

And lastly, we've got hash tables, but be prepared. I'm about to give you the old bait and switch because C actually has two flavors of hash based collections.

One is an older and there's another that's the new hotness. Hash tables is non generic and it lives in system collections. It's the old broken down version. You're not likely to see it in newer code. It's gonna be in legacy code, but let's take a look at how it works.

Let's start up a new one with VAR table. We'll say equals new system collections. Hash table. And then we'll say table dot add. And let's see for the key, we'll say one.

And for the value, I'm gonna say 42 and then say table dot add and we'll say two. And for that one, I'm gonna say, you know, 100, but it's a string, right? Now, this is great for fast lookups, but you can see already where this is gonna cause a problem as I'm pulling things out because we're boxing those values in an object. Hash table just uses object as the value. So you've gotta be very careful about what you're doing on that end.

But remember that old bait and switch I told you about? Yeah, here it is. Hash table like I mentioned is probably used more in legacy code or the future code you're writing. You're gonna wanna prefer the dictionary. Dictionary of T key, T value.

Let's try that one out now. We're gonna get rid of this code. We'll just say new table equals new, dictionary of type string and end. And in this case, we are strongly typing that value so that we don't get issues trying to unbox that value from a hash table. And we can just say table dot add and we'll say in this case, one and one maybe, and table dot add two and two, but this could be anything, whatever the types are you've specified as that key and value.

But if you're gonna get away from using like basic types as your key, make sure you've implemented a really good get hash code and equals override so that it's consistently able to look those up a lot faster. But one thing that's really nice about this is there's type safety. We don't have to worry about unboxing and casting errors and all that sort of thing. And if we wanna make sure that IDs are okay, we can use the try get value. So we can say if table dot try get value, we'll say we'll say two because we want it to exist there.

We'll say out who knows user whatever we wanted to call that. Then we'll do that. I feel like I typed that wrong. Oh yeah, missing a parentheses. There we go.

Now you're not so happy with me. You're not so happy. I need that out int user. There we go. And now I can console dot writeline, something like user found it, found it, learn how to speak.

It came in type much less speak. So if I run that .net, dot net run, we'll get that, you know, it with the two and the Lambda layer. So that's really not nicer than the hash table because you get strong typing and you get that try get value that allows you to check for keys if you're not sure they exist. But if you are using a hash table, there are a few things you're gonna be aware of. Number one contains key.

It checks for a key. Contains value can be surprisingly expensive because it's actually going through and reviewing all the values, which we remember are boxed. And then as I mentioned, custom key types should have a really good get hash code and equals implemented. But like I said, in most modern code, you're gonna wanna use the dictionary or a hash set, or maybe even a concurrent dictionary, depending on your use case.

Before I wrap up, there's a few other things you really ought to know. For instance, stack and queue, they are great for expanding as you need. But if you can specify an initial size, you'll see enhanced performance because it will reduce allocations. Also avoid contains value on large data sets. It's a linear search and can really slow down your performance.

And then lastly, for keys, as I mentioned, prefer immutable types. Strings are great, but if you must use something else, like I've mentioned multiple times and because it's important, implement a solid get hash code and equals. So yeah, if your code needs order and fairness, reach for a queue. And if you need to time travel, look for a stack.

And then if you need instant lookups, hash it with a dictionary. Until next time.