Imagine a narrow elevator wide enough for only one person but deep enough to line-up ten. As you add people you can only see the most recently added person. Everyone else is hidden behind the first person. To empty the elevator you must remove the people from most recent to last. This is an example of a last-in-first-out structure or LIFO. Stacks are exactly that, a structure where you want to preserve the order of each addition and removal of data wherein the last data added is the next one to be removed. Stacks have two operations. Pop removes an item and push adds one. The most common use of stacks is in call stacks. When a function is called the current programs scope, called a frame, are saved onto the stack so that when the function terminates the programs can know where in the program to return to. Each function call adds another frame to the stack and each return brings the programs back to the locations of the call to continue executing.


Now imagine a line-up of people wanting to buy widgets in a store. People can only be added to the end of the line and removed from the front of the line. The first person in the line is the first person out, first-in-first-out or FIFO. Similar to the stack except the place where items are removed is opposite. Queues have two primary operations: enqueue and dequeue. Enqueue adds an item to the queue and dequeue removes one. A queue could be used as a data server resource allocator which serves data to the client who has been waiting the longest.