Using Stacks and Queues

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, but I'll cover them in other articles.

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 .Count.
• 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 organization.

To do this, you need to use the System.Collections.Generic package instead of System.Collections. For example, in our case, we could use Stack<int>:

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 Pop() function:

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 Contains() method:

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 till 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 and 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 Dequeue() function:

Also, we can once again just look at the elements without modifying the collection using the Peek() method, and we have the Clear() and 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.

Conclusion

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.