What is a Stack?
Explore the fundamentals of stack data structures, their Last In First Out ordering, and key operations such as push and pop. Understand how stacks are used in programming tasks like undo functionality, recursion backtracking, and algorithm implementations to solve complex problems effectively.
We'll cover the following...
Introduction
Everyone is familiar with the famous undo option, which exists in almost all popular applications. But have you ever wondered how that works? Well, store the previous states of your work (which are limited to a specific number) in the memory in such an order that the last one appears first. You can’t efficiently do this with simple arrays for reasons explored in the coming chapters. This is where the “stack” data structure comes in handy.
Stacks follow the Last in First Out (LIFO) ordering. This means that the last element added is the element on the top, and the first element added is at the bottom.
A real-life example of stack could be a stack of books. To get the book that’s somewhere in the middle, you will remove all the books placed at the top of it. Also, the last book you added to the stack of books is at the top!
What are stacks used for?
Despite the simple implementation, stacks can be used to solve very complex problems.
There are many famous algorithms such as depth first search and the expression evaluation algorithm, which harness the functionality of stacks. Stacks are used:
-
To backtrack to the previous task/state. For example, it backtracks in recursive code.
-
To store a partially completed task; for example, you are exploring two different paths on a graph from a point while figuring out the smallest path to the target.
How does a stack work?
Stacks can be implemented in many ways, but a typical stack must offer the following functionalities:
| Function | What does it do? |
|---|---|
push(value) |
Inserts an element at the top |
pop() |
Removes an element from the top and returns it |
isEmpty() |
Returns a boolean 1 if the stack is empty |
getTop() |
Returns the element added most recently |
The following animation is a high-level demonstration of the push(value) and the pop() functions.