Stacks and Queues

Stacks and queues are two of the most useful abstract data types (ADTs). An ADT is defined by the operations you can perform on it and the rules governing them, not by how it is stored in memory. Both a stack and a queue are ordered collections, but they differ in which element you are allowed to remove next. That single rule leads to very different behavior and very different applications.

Stacks: last in, first out

A stack follows the LIFO rule: last in, first out. The last item you add is the first one you take out, exactly like a stack of plates where you only add to and remove from the top. A stack supports a small set of operations:

• push(item) — add an item to the top of the stack.
• pop() — remove and return the item on top.
• peek() (sometimes called top) — look at the top item withou