Stack vs. Queue

I was asked the other day about First In, First Out (FIFO) and First In, Last Out (FILO) data structures.

Sticking to basic data structure examples a Stack and a Queue represent these type of operations.

Queue

Think of a queue as standing in line at the movie theater or anywhere else you would stand in line.  You stand in line until called up (ususally when a ticket window is available to help you, or in computer terms when a queue item is ready to be processed).  The first person in line will be the first person helped and the last person in line will be the last person helped.  So First In, First Out; FIFO.  Conversely, Last In will be Last Out.

Stack

In a "traditional" implementation of a stack things will be First In, Last Out; FILO.  Think of a stack as a stack of papers.  As you stack the paper the first paper in the stack will be at the bottom.  So as you work through the stack of papers, the last item will be first one off the stack.  So First In, Last Out.  Conversely, Last In, First Out.

Of note, putting an item on a stack is called a "push" and removing an item from the stack is called a "pop".

Usage in Applications

A queue is probably used more often than a stack based on my professional experience.  Generally, items on a queue follow an order such that you want to process the first item in before the previous item due to business rules.  For example, imagine if I had a queue for order creation and changes.  An order must exist to be changed so logically I need to process the creation of the order first.  Using a queue, the creation action will always occur before the changes.  Then when a change occured, I could apply the changes to the order.  Then a subsequent change would be inacted upon the order based on the previous change, etc.

A stack is well suited for cases where the newest information is what you'll access first. So a cache or something like that.  I might have a stack to store objects and the last used object will be the last (first out) item of the cache.