Stack
Data Structure · Starter
Step through it: Monotonic Stack pattern
Step 1 of 7
Goal: for each number, find the next bigger number to its right. Comparing every number with everything after it is slow. Instead keep a stack of numbers that are still waiting for a bigger one.
Step 2 of 7
Take 2. Nothing to compare yet, so it waits on the stack.
Step 3 of 7
Take 1. It is smaller than the waiting 2, so it cannot be anyone's answer. It waits too, on top.
Step 4 of 7
Take 5. It is bigger than 1, so 5 is the answer for 1. Pop 1. It is bigger than 2 as well, so pop 2 too. Then 5 waits.
Step 5 of 7
Take 3. Smaller than 5, so it waits on top.
Step 6 of 7
Take 6. It beats 3 and 5, so both get answer 6. Whatever is left never found a bigger number. Each number is pushed once and popped once, so it is one pass. The stack stays in decreasing order, which is why this is called a monotonic stack.
Step 7 of 7
Your turn.
In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations:
- push, which adds an element to the collection, and
- pop, which removes the most recently added element that was not yet removed.
The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out). Additionally, a peek operation may give access to the top without modifying the stack. The name "stack" for this type of structure comes from the analogy to a set of physical items stacked on top of each other, which makes it easy to take an item off the top of the stack, while getting to an item deeper in the stack may require taking off multiple other items first.
Simple representation of a stack runtime with push and pop operations.
Made with okso.app
Code
import LinkedList from '../linked-list/LinkedList';
export default class Stack {
constructor() {
// We're going to implement Stack based on LinkedList since these
// structures are quite similar. Compare push/pop operations of the Stack
// with prepend/deleteHead operations of LinkedList.
this.linkedList = new LinkedList();
}
/**
* @return {boolean}
*/
isEmpty() {
// The stack is empty if its linked list doesn't have a head.
return !this.linkedList.head;
}
/**
* @return {*}
*/
peek() {
if (this.isEmpty()) {
// If the linked list is empty then there is nothing to peek from.
return null;
}
// Just read the value from the start of linked list without deleting it.
return this.linkedList.head.value;
}
/**
* @param {*} value
*/
push(value) {
// Pushing means to lay the value on top of the stack. Therefore let's just add
// the new value at the start of the linked list.
this.linkedList.prepend(value);
}
/**
* @return {*}
*/
pop() {
// Let's try to delete the first node (the head) from the linked list.
// If there is no head (the linked list is empty) just return null.
const removedHead = this.linkedList.deleteHead();
return removedHead ? removedHead.value : null;
}
/**
* @return {*[]}
*/
toArray() {
return this.linkedList
.toArray()
.map((linkedListNode) => linkedListNode.value);
}
/**
* @param {function} [callback]
* @return {string}
*/
toString(callback) {
return this.linkedList.toString(callback);
}
}References
Practice
Monotonic Stack
- Valid ParenthesesEasy
- Next Greater Element IEasy
- Min StackEasy
- Baseball GameEasy
- Remove All Adjacent Duplicates In StringEasy
- Daily TemperaturesMedium
- Next Greater Element IIMedium
- Evaluate Reverse Polish NotationMedium
- Decode StringMedium
- Remove K DigitsMedium
- Online Stock SpanMedium
- Car FleetMedium
- Asteroid CollisionMedium
- Simplify PathMedium
- 132 PatternMedium
- Sum of Subarray MinimumsMedium
- Largest Rectangle in HistogramHard
- Maximal RectangleHard
- Trapping Rain WaterHard
- Basic CalculatorHard
Spotted a mistake or something unclear? Report it on GitHub.