Stacks

Whereas Queue<T> operates a FIFO order, Stack<T> operates a last in, first out (LIFO) order. Looking at this from a queuing perspective, it seems like the height of unfairness—latecomers get priority over those who arrived early. However, there are some situations in which this topsy-turvy ordering can make sense.

A performance characteristic of most computers is that they tend to be able to work faster with data they’ve processed recently than with data they’ve not touched lately. CPUs have caches that provide faster access to data than a computer’s main memory can support, and these caches typically operate a policy where recently used data is more likely to stay in the cache than data that has not been touched recently.

If you’re writing a server-side application, you may consider throughput to be more important than fairness—the total rate at which you process work may matter more than how long any individual work item takes to complete. In this case, a LIFO order may make the most sense—work items that were only just put into a queue are much more likely to still live in the CPU’s cache than those that were queued up ages ago, and so you’ll get better throughput during high loads if you process newly arrived items first. Items that have sat in the queue for longer will just have to wait for a lull.

Like Queue<T>, Stack<T> offers a method to add an item, and one to remove it. It calls these Push and Pop, respectively. They are very similar to the queue’s Enqueue and Dequeue, except they both work off the same end of the list. (You could get the same effect using a LinkedList, and always calling AddFirst and RemoveFirst.)

A stack could also be useful for managing navigation history. The Back button in a browser works in LIFO order—the first page it shows you is the last one you visited. (And if you want a Forward button, you could define a second stack—each time the user goes Back, Push the current page onto the Forward stack. Then if the user clicks Forward, Pop a page from the Forward stack, and Push the current page onto the Back stack.)