Introduction to Stacks
Stacks, queues, deques, and lists are data collections with items ordered according to how they are added or removed. Once an item is added, it stays in the same position relative to its neighbours. Because of this characteristic, we call these collections linear data structures.
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”, and the opposite end is known as the “base”.
Items that are closer to the base have been in the stack the longest. The most recently added item is always on the top of the stack and thus will be removed first.
There are many examples of stacks in everyday situations. Consider a stack of plates on a table, where it’s only possible to add or remove plates to or from the top.
Or
Imagine a stack of books on a desk. The only book whose cover is visible is the one on top. To access the others, we must first remove the ones sitting on top of them.
Here’s another stack containing a number of primitive data objects:
Features of Stacks
One of the most useful features of stacks comes from the observation that the insertion order is the reverse of the removal order.
To make things simpler stack follows LIFO which means item that was Last In would be the item that would be First Out.
Starting with a clean desk, place books on top of each other one at a time and consider what happens when you begin removing books: the order that they’re removed is exactly the reverse of the order that they were placed. This ability to reverse the order of items is what makes stacks so important.
Below we show the object stack during insertion and removal. Note the objects’ order.
Considering this reversal property, perhaps you can think of stack examples that occur while using your computer. For example, every web browser has a “Back” button. As you navigate from page to page, the URLs of those pages are placed on a stack. The page you’re currently viewing is on the top, and the first page you looked at is at the base. Clicking on the Back button moves you in reverse order through the stack of pages.
