A stack is an abstract data structure which is used to store a collection of elements with the ability to add or remove elements at only one endpoint (often called the top). Due to this property of a stack which restricts addition or removal of elements only from one end, a stack is also known as a Last In First Out (LIFO) data structure. It means that the last element which is added to the stack will be the first one to come out of the stack during removals.
Visualizing a Stack Data Structure
A stack can be visualized as a vertical space into which objects can be added or removed from the top. The recently added element will be at the top of stack. The image below depicts how a stack looks if it were to exist in real world (Image Source).
Elements 42, 23, 2, 9 are added to the stack in order. The spring makes sure that the element which is added last will be at the top of stack thereby making the top element easily accessible. Any element added to the stack will move the existing top element down and the newly added element will be at the top.
While removing elements, the topmost element is removed and after removal, the next top element will move to the top. So the first element to be removed will be the most recently added element which is 9. Followed by 2, 23 and 43.
Basic Operations Supported by a Stack
Below are all the operations supported by a stack abstract data structure:
| Operation | Description |
|---|---|
| push | Adds an element to the top of the stack |
| pop | Removes an element from the top of the stack |
| top | Examines the element at the top of the stack |
| is_empty | Determines whether the stack is empty |
| size | Determines the number of elements in the stack |
Let us now go through each operation in detail.
Push an element to the Stack
This operation allows us to push an element into open end of stack. The animation below pushing of 4 elements A, B, C, D into a stack in that order.
Note that we show the stack data structure as a vertical space with storage slots from top to bottom. But in theory a stack can be visualized in any orientation as long as insertion and removal of elements happen only from one end.
Pop an element from the Stack
This operation allows us to remove element present at the top of stack. The animation below depicts popping out all the elements present in a stack one by one.
Access the element present at the top of Stack
This operation allows us to access the “top” element of the stack. It can be used in cases where we just need temporary access to the top element in the stack and removal/popping of the top element is not necessary.
Check if the Stack is Empty
This operation is useful for finding out if a stack is empty. This is helpful especially to prevent popping an element from an empty stack. Or to prevent accessing the top most element in an empty stack etc.
When to use a Stack data structure?
Stack is a natural choice for handling undo and redo operations on a document:
- Let’s say we we have typed the word “a w e s o m e” character by character in a text editor.
- What should happen when we do undo or ctrl+z the first time?
- The last character which is typed should be deleted i.e, ‘e’. So the remaining text is “a w e s o m”.
- The next time we perform the undo operation, the last typed character among the remaining characters should be removed. The text then becomes “a w e s o”.
- This is similar to what a stack does i.e., while removing/reversing an operation, it removes/undoes the last operation (the last character typed in this case).
- Similarly if we store all the undo operations performed in another stack, it can be used as a reference while redoing any undo operation.
Stack is also used for managing execution of nested function calls:
- For example if function A calls function B which in turn calls function C, at the time function A calls B, function A is added to the stack. Similarly function B is added to the stack when function C is called.
- Now when function C finishes it’s work, the top most / latest function in the stack - function B regains control.
- After function B finishes, the next top most function - function A regains control.
- This mechanism is performed by the operation system using a stack.
- Programs based on recursion have nested function calls similar to scenario above. These programs can be converted to iterative logic using stack data structure.
In any scenario where the last/latest element added to a collection has to be retrieved first (Last in First out - LIFO), stack is a natural choice. Eg: Backtracking.