Pick the right data structure to get the most out of your algorithms!
This article is also available on Medium.
When you work with a lot of data, oftentimes, choosing the right data representation can be crucial in reducing the processing time. Depending on your algorithm and the various steps in your logic, you may need to write data, or read it, or modify it, or count the number of items in a collection…
To this end, most programming languages offer a wide variety of data structures to handle those different cases: hash tables and dictionaries are great for accessing data because they are well-indexed and items are quick to get; arrays and lists are great to count elements because everything is contiguous so you easily get the total length; tuples are interesting to pass small amount of data quickly and easily, and so on.
There are several ways of categorising data structures in C#: you can differentiate between generic and non-generic collections, or between mutables and immutables, etc.
Today, let’s see the difference between LIFO and FIFO structures with their two most famous implementations: the stack and the queue!
Stacks: “last in, first out”
The LIFO acronym stands for: “last in, first out”. A LIFO structure is a data structure where the data that is most accessible is “on top of the pile”, meaning that you first read the last items you inserted in your collection.
When we add an item, we say that we “push” it; when we take it back, we say we “pop” it.
It’s just like a stack of plates: as you put more plates on the pile, the first ones are less and less accessible, and you’re forced to remove all the new ones to get them back!
How to use stacks in C#?
In C#, to use stacks, you just need the
System.Collections package, and you’ll then have the
Stack class available:
As you can see:
- we can easily get the current number of elements in the stack with
- we can add new elements using
.Push(): this puts a new item at the top of the pile
- when we read back our values with the iterator, we get them in “reverse” order: we have LIFO structure, so we first get the last element we inserted, then the last-but-one, then the first one (in our case: 3, 2, 1)
Usually, it’s better to avoid using the non-generic
Stack class and instead rely on the generic version,
Stack<T>. This allows you to pass in the type of elements that you’ll store in your collection which is better for type checks, safety and overall code organisation 🙂
To do this, you need to use the
System.Collections.Generic package instead of
System.Collections. For example, in our case, we could use
Using generic collections is nice because, this way, your program knows the type of items in the collection at compile time, and it gives a hint to your IDE for autocompletion/variable typing.
Here is the same for-loop using the
var keyword for auto-typing with a non-generic and a generic stack:
In the first case (non-generic), the IDE can’t tell you exactly which object type you have here, whereas in the second case (generic), it knows ahead of time that those items are integers!
You can easily extract the first element and remove it from the stack using the
You see that after a
Pop(), your collection has one less item, so the new “top of the pile” is now the last-but-one inserted item.
This gives us a basic routine for emptying a stack and doing something on each item:
Here, we simply go through the pile and extract elements one by one, starting with the most recent because it’s a LIFO structure, and run some logic on each item as we remove them from the collection. When we don’t have items anymore (we’ve reached the bottom of the pile and extracted the least-recently inserted item), we exit the while-loop and stop.
If you don’t want to remove the element and instead just need to look at the most recent item, you can use another method:
Peek(). This allows you to get “a quick look” at the structure and its top element but not modify it in any way (see how the total number of elements stays the same after the “peeking”):
Finally, you can empty a stack completely using the
Clear() function or check for a specific item with the
Why are stacks interesting?
The big advantage of stacks is that, by definition, getting back the latest element is really easy. We say that “reading the top value” is a “constant-time operation” (and we write it as O(1) in complexity theory).
Similarly, adding a new item is usually pretty simple: you just push one plate on the pile. So it’s also an O(1) operation most of the time. Note however that, in C#, the size of the stacks is automatically adapted to fit the total number of elements; so if you exceed the size allocated up til now, adding a new item requires the program to “shift” all current elements and is therefore way more costly!
We can also get the total number of elements quickly by keeping track of this counter when we add or remove elements.
And getting a specific element is harder than with index collections (like arrays or dictionaries): the only solution is to iterate through every element of the collection and check if it’s the one you want which, in the worst case scenario, means you’ll go through all the items in your stack (which we write O(n)).
When are stacks useful?
A common beginner’s study case for stacks is checking for balanced parentheses in an arithmetic expression. Say you want to know if a given expression has as many opening brackets as it has closing ones: then you can simply push an item on your stack when you encounter an opening parenthesis and pop it when you encounter a closing parenthesis. If, at the end, you have an empty stack, it means that the brackets were properly balanced 🙂
Note: stacks are more powerful than a simple counter – we could adapt this snippet of code to check for different types of braces/brackets at the same time which would be trickier with only counters 😉
More generally speaking, stacks are an essential component inside of computers, both in software and hardware. For example, they’re a critical part of programs execution. Whenever you have direct values in your program that are stored in variables, these variables are “on the stack” and pushed or popped as the program executes. This is particularly useful to get variable scopes inside of functions (for local variables and parameters).
Stacks are also used to evaluate arithmetic expressions and compute everything along the execution process because they allow the computer to “remember” the pending operations and then combine them into a final result.
Yet another use case for stacks is tree traversal: when you want to do depth-first search, stacks are a great way of storing your data since they let you push you info as you go down and then pop it back to the last “intersection”!
Queues: “first in, first out”
Queues are often studied alongside stacks because they are kind of the “other side of the coin”. Contrary to stacks, queues are FIFO structures: “first in, first out”. This means that the first items you stored in your collection will be the most accessible ones.
When we add an item, we say that we “enqueue” it; when we take it back, we say we “dequeue” it.
This is a bit like a line at a take-away: the customer that arrived first will be the first to get to the counter and order.
Or if you want to stick with plates: if you’re washing your plates and they are on a conveyer belt, then the first one to come back to you will be the least recent one…
How to use queues in C#?
Just like with stacks, C# has both non-generic and generic queues that are available respectively in the
System.Collections.Generic packages. Creating, populating and reading from a queue is very similar to using a stack:
But, of course, you see in the output that this time we get back our elements in the same order as when we pushed them in the queue! 😉
To extract the first element and remove it from the collection, we use the
Also, we can once again just look at the elements without modifying the collection using the
Peek() method, and we have the
Contains() methods, too.
Why are queues interesting?
The complexity of operations for queues is the same as for stacks. The only difference is that we call “the first element” is the “head” of the container instead of the “tail” 😉
When are queues useful?
Whenever you want to retrieve your data in the same order as you wrote them originally, you should use a queue. Messaging systems like RabbitMQ rely a lot on queue structures because they nicely implement this logic of “enqueuing” messages and “dequeuing” them later on one by one, in their order of arrival.
In software and game development, queues are a nice way of creating a basic history system: you can store your actions and then re-read in the chronological order.
Note: for an undo/redo system, though, stacks are better because you most probably want a reverse chronological order 🙂
Queues can also be used for “customer selection policies“: if you have a website with a limited threshold of concurrent connections and there’s a sudden rush that exceeds this capacity, then your server will need to decide who to accept and who to reject. A “fair policy” could be to give access to the customers that arrived first and only then respond to the other ones, on a “first-come first-serve” basis. In that case, a queue can help you “remember” the order of arrival.
That’s also something that computers can use internally to schedule the processes to run and decide which program should get the upper hand and run its logic.
Queues can also be used for tree traversal when you want to do breadth-first search.
Stacks and queues are fundamental notions in computer science that can be applied to an endless number of use cases in very various domains. Although they may seem basic and almost too simple at first glance, they can often be adapted or combined with other structures to create really complex systems, like messaging or software scheduling.
What about you: do you use those data structures in your projects? Have you had the chance to get a performance boost thanks to these specific data representations? Don’t hesitate to share in the comments! 😉