1.
Say we create a stack by pushing numbers 1 to 4 from lowest to highest. What would the stack look like afterwards?
Section 3.3 What is a Stack?
A stack (sometimes called a “push-down 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.” The end opposite the top is known as the “base.”
The base of the stack is significant since items stored in the stack that are closer to the base represent those that have been in the stack the longest. The most recently added item is the one that is in position to be removed first. This ordering principle is sometimes called LIFO, last-in first-out. It provides an ordering based on length of time in the collection. Newer items are near the top, while older items are near the base.
Many examples of stacks occur in everyday situations. Almost any cafeteria has a stack of trays or plates where you take the one at the top, uncovering a new tray or plate for the next customer in line. Imagine a stack of books on a desk (Figure 3.3.1). The only book whose cover is visible is the one on top. To access others in the stack, we need to remove the ones that are sitting on top of them. Figure 3.3.2 shows another stack.
This image illustrates a stack of books. The books, from the bottom to the top, are: History, Music, Physics, Calculus and Python.
This image depicts a stack data structure with labeled "Top" and "Base" sections. The stack contains four elements, each represented as a block with a string value. From bottom (Base) to top, the elements are: "4", "dog", "True", and "8.4". The "Base" of the stack is the bottom-most element ("4"), while the "Top" of the stack is the upper-most element ("8.4"). This structure visually represents how stacks operate in a Last-In-First-Out (LIFO) manner, where the last element added ("8.4") is the first one to be accessed or removed.
One of the most useful ideas related to stacks comes from the simple observation of items as they are added and then removed. Assume you start out with a clean desktop. Now place books one at a time on top of each other. You are constructing a stack. Consider what happens when you begin removing books. The order that they are removed is exactly the reverse of the order that they were placed. Stacks are fundamentally important, as they can be used to reverse the order of items. The order of insertion is the reverse of the order of removal. Figure 3.3.3 shows the stack object as it was created and then again as items are removed. Note the order of the objects.
This image illustrates the process of reversing the order of elements in a stack. The stack contains four elements: "8.4", "True", "dog", and "4". The "Original Order" is represented at the bottom of the image, starting with "8.4" (4th element) at the top of the stack and ending with "4" (1st element) at the bottom. The "Reversed Order" is shown on the right side, where the elements have been rearranged such that "4" becomes the first element, "dog" the second, "True" the third, and "8.4" the fourth. The arrows illustrate the flow of elements from their positions in the stack to their corresponding reversed positions, emphasizing how a stack’s Last-In-First-Out (LIFO) nature can be used to reverse a sequence of elements.
Considering this reversal property, you can perhaps think of examples of stacks that occur as you use your computer. For example, every web browser has a Back button. As you navigate from web page to web page, those pages are placed on a stack (actually it is the URLs that are going on the stack). The current page that you are viewing is on the top and the first page you looked at is at the base. If you click on the Back button, you begin to move in reverse order through the pages.
Reading Questions Reading Question
You have attempted of activities on this page.
