Stacks

A stack is an abstract data type that follows the "Last In, First Out" (LIFO) principle. Using LIFO means that the last item added to the stack is the first item to be removed.

Imagine a stack of plates. When you place a new plate on top of this stack, it covers all the other plates that were there before. If you need to remove a plate, you'll take off the one you placed last first because it's on top. You won't reach down to grab one from the bottom until all those placed above it have been removed. This "top-down" approach is the essence of LIFO.

Key Operations

There are three primary operations you can perform on a stack data structure:

Push

• In stack terminology, pushing is the act of adding an element to the top of the stack. Just as you would place a clean plate on top of the others, pushing in a data context adds a data element (like a number, character, or object) to the stack.
• This operation is accomplished in constant time, O(1), because it doesn't require shifting or moving other elements around; you simply place the new item on top.

Pop

• Similar to removing the top plate from a stack when you need to use it, popping in a stack data structure involves removing the top element.
• This is also a constant time operation, O(1), as it directly accesses the top element without needing to rearrange or look through the rest of the stack.

Peek

• In a plate stack, you might glance at the top plate to see if it's clean or the one you want. In a stack data structure, "peeking" lets you see the value of the top element without removing it from the stack. This can be useful for checking the value before deciding to remove it or perform other operations.

---

Practical Applications of Stacks

Function Call Management

In programming, whenever a function (a block of code designed to perform a specific task) is called, information about where the function was called from and its internal variables are stored in a stack. Each subsequent function call adds another layer to this stack. When a function completes its task, its information is removed from the stack, and the program returns to the point where this function was called. This system helps manage where the program should continue running after a function has been executed.

Undo Mechanisms in Applications

Think about using a word processor or a graphics design program. Each action you take (like typing a letter or drawing a shape) can potentially be reversed by using the "undo" feature. Stacks make this possible by keeping a record of each action in the reverse order in which they were performed. When you hit "undo," the most recent action is "popped" off the stack and reversed.

Web Browser Navigation

The back button in a web browser allows you to revisit the previous web page. This is implemented using a stack. Each time you visit a new page, the URL (web address) is pushed onto a stack. When you press the back button, the most recent URL is popped off, taking you back to the last page you visited.

Depth-First Search (DFS) in Graphs

We will cover Graphs in a later lesson. Without going into what graphs are right now, just know that they are a data structure and we can traverse this data structure using something called depth-first search algorithm. This algorithm uses a stack to perform the traversal.

In the next assignment, we'll see how we can implement a stack using a linked list.