Data Structures: Stack

What is a Stack?

A stack is an ordered collection of items where the addition of new items and the removal of existing items always takes place at the same end. This end is commonly referred to as the “top,” where the end opposite the top is known as the “base.” This ordering principle is sometimes called LIFO, or “last in first out”. Newer items are near the top, while older items are near the base. Consider a PEZ dispenser: its candy is inserted in the top, and the last candy to be placed in is the first candy to be dispensed.

In the image below, the term "push" refers to an item being placed onto the Stack because a Stack is LIFO, the item most recently pushed onto the Stack will be on top. Similarly, the term "pop" refers to an item being taken off of the Stack. Only the item at the top of the Stack can be popped.

The class text provides code implementation of the Stack ADT here: