Queue and Stack
There are multiple implementations of Queue in Java, such as LinkedList, ArrayDeque, etc. offer
, poll
, peek
methods are used to manipulate data in the queue. Circular array is another choice to implement an queue.
Leetcode 158. Read N Characters Given Read4 II - Call multiple times
For stack, we use Stack class and push
, pop
, peek
methods.
Leetcode 225. Implement Stack using Queues
Leetcode 232. Implement Queue using Stacks
Monotonic stack
Monotonic stack is used to find the next lager element in an array. Vice verser.
Stack<Integer> stack = new Stack<>();
Map<Integer, Integer> nextGreaterMap = new HashMap();
for(int i = 0; i < nums2.length; i++){
while(!stack.isEmpty() && stack.peek() < nums2[i]){
nextGreaterMap.put(stack.pop(), nums2[i]); //pop all element smaller than the current one.
}
stack.push(nums2[i]);
}
Leetcode 42. Trapping Rain Water
Leetcode 84. Largest Rectangle in Histogram
Leetcode 316. Remove Duplicate Letters
Leetcode 496. Next Greater Element I
Leetcode 739. Daily Temperatures