Search Blogs

Showing results for "NextGreaterElement"

Found 3 results

LeetCode 496: Next Greater Element I — Java Solution With All Approaches Explained

IntroductionLeetCode 496 Next Greater Element I is your gateway into one of the most important and frequently tested patterns in coding interviews — the Monotonic Stack. Once you understand this problem deeply, problems like Next Greater Element II, Daily Temperatures, and Largest Rectangle in Histogram all start to make sense.Here is the Link of Question -: LeetCode 496This article covers plain English explanation, real life analogy, brute force and optimal approaches in Java, detailed dry runs, complexity analysis, common mistakes, and FAQs.What Is the Problem Really Asking?You have two arrays. nums2 is the main array. nums1 is a smaller subset of nums2. For every element in nums1, find its position in nums2 and look to the right — what is the first element that is strictly greater? If none exists, return -1.Example:nums1 = [4,1,2], nums2 = [1,3,4,2]For 4 in nums2: elements to its right are [2], none greater → -1For 1 in nums2: elements to its right are [3,4,2], first greater is 3For 2 in nums2: no elements to its right → -1Output: [-1, 3, -1]Real Life Analogy — The Taller Person in a QueueImagine you are standing in a queue and you want to know — who is the first person taller than you standing somewhere behind you in the line?You look to your right one by one until you find someone taller. That person is your "next greater element." If everyone behind you is shorter, your answer is -1.Now imagine doing this for every person in the queue efficiently — instead of each person looking one by one, you use a smart system that processes everyone in a single pass. That smart system is the Monotonic Stack.Approach 1: Brute Force (Beginner Friendly)The IdeaFor each element in nums1, find its position in nums2, then scan everything to its right to find the first greater element.javapublic int[] nextGreaterElement(int[] nums1, int[] nums2) { int[] ans = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { int found = -1; boolean seen = false; for (int j = 0; j < nums2.length; j++) { if (seen && nums2[j] > nums1[i]) { found = nums2[j]; break; } if (nums2[j] == nums1[i]) { seen = true; } } ans[i] = found; } return ans;}Simple to understand but inefficient. For each element in nums1 you scan the entire nums2.Time Complexity: O(m × n) — where m = nums1.length, n = nums2.length Space Complexity: O(1) — ignoring output arrayThis works for the given constraints (n ≤ 1000) but will not scale for larger inputs. The follow-up specifically asks for better.Approach 2: Monotonic Stack + HashMap (Optimal Solution) ✅The IdeaThis is your solution and the best one. The key insight is — instead of answering queries for nums1 elements one by one, precompute the next greater element for every element in nums2 and store results in a HashMap. Then answering nums1 queries becomes just a HashMap lookup.To precompute efficiently, we use a Monotonic Stack — a stack that always stays in decreasing order from bottom to top.Why traverse from right to left? Because we are looking for the next greater element to the right. Starting from the right end, by the time we process any element, we have already seen everything to its right.Algorithm:Traverse nums2 from right to leftMaintain a stack of "candidate" next greater elementsFor current element, pop all stack elements that are smaller or equal — they can never be the next greater for anything to the leftIf stack is empty → next greater is -1, else → top of stack is the answerPush current element onto stackStore result in HashMapLook up each nums1 element in the HashMapjavapublic int[] nextGreaterElement(int[] nums1, int[] nums2) { Stack<Integer> st = new Stack<>(); HashMap<Integer, Integer> mp = new HashMap<>(); // Precompute next greater for every element in nums2 for (int i = nums2.length - 1; i >= 0; i--) { // Pop elements smaller than current — they are useless while (!st.empty() && nums2[i] >= st.peek()) { st.pop(); } // Top of stack is the next greater, or -1 if empty mp.put(nums2[i], st.empty() ? -1 : st.peek()); // Push current element as a candidate for elements to its left st.push(nums2[i]); } // Answer queries for nums1 int[] ans = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { ans[i] = mp.get(nums1[i]); } return ans;}Why Is the Stack Monotonic?After popping smaller elements, the stack always maintains a decreasing order from bottom to top. This means the top of the stack at any point is always the smallest element seen so far to the right — making it the best candidate for "next greater."This is called a Monotonic Decreasing Stack and it is the heart of this entire pattern.Detailed Dry Run — nums2 = [1,3,4,2]We traverse from right to left:i = 3, nums2[3] = 2Stack is emptyNo elements to popStack empty → mp.put(2, -1)Push 2 → stack: [2]i = 2, nums2[2] = 4Stack top is 2, and 4 >= 2 → pop 2 → stack: []Stack empty → mp.put(4, -1)Push 4 → stack: [4]i = 1, nums2[1] = 3Stack top is 4, and 3 < 4 → stop poppingStack not empty → mp.put(3, 4)Push 3 → stack: [4, 3]i = 0, nums2[0] = 1Stack top is 3, and 1 < 3 → stop poppingStack not empty → mp.put(1, 3)Push 1 → stack: [4, 3, 1]HashMap after processing nums2:1 → 3, 2 → -1, 3 → 4, 4 → -1Now answer nums1 = [4, 1, 2]:nums1[0] = 4 → mp.get(4) = -1nums1[1] = 1 → mp.get(1) = 3nums1[2] = 2 → mp.get(2) = -1✅ Output: [-1, 3, -1]Time Complexity: O(n + m) — n for processing nums2, m for answering nums1 queries Space Complexity: O(n) — HashMap and Stack both store at most n elementsWhy Pop Elements Smaller Than Current?This is the most important thing to understand in this problem. When we are at element x and we see a stack element y where y < x, we pop y. Why?Because x is to the right of everything we will process next (we go right to left), and x is already greater than y. So for any element to the left of x, if they are greater than y, they are definitely also greater than y — meaning y would never be the "next greater" for anything. It becomes useless and gets discarded.This is why the stack stays decreasing — every element we keep is a legitimate candidate for being someone's next greater element.How This Differs From Previous Stack ProblemsYou have been solving stack problems with strings — backspace, stars, adjacent duplicates. This problem introduces the stack for arrays and searching, which is a step up in complexity.The pattern shift is: instead of using the stack to build or reduce a string, we use it to maintain a window of candidates while scanning. This monotonic stack idea is what powers many hard problems like Largest Rectangle in Histogram, Trapping Rain Water, and Daily Temperatures.Common Mistakes to AvoidUsing >= instead of > in the pop condition We pop when nums2[i] >= st.peek(). If you use only >, equal elements stay on the stack and give wrong answers since we need strictly greater.Traversing left to right instead of right to left Going left to right makes it hard to know what is to the right of the current element. Always go right to left for "next greater to the right" problems.Forgetting HashMap lookup handles the nums1 query efficiently Some people recompute inside the nums1 loop. Always precompute in a HashMap — that is the whole point of the optimization.FAQs — People Also AskQ1. What is a Monotonic Stack and why is it used in LeetCode 496? A Monotonic Stack is a stack that maintains its elements in either increasing or decreasing order. In LeetCode 496, a Monotonic Decreasing Stack is used to efficiently find the next greater element for every number in nums2 in a single pass, reducing time complexity from O(n²) to O(n).Q2. What is the time complexity of LeetCode 496 optimal solution? The optimal solution runs in O(n + m) time where n is the length of nums2 and m is the length of nums1. Processing nums2 takes O(n) and answering all nums1 queries via HashMap takes O(m).Q3. Why do we traverse nums2 from right to left? Because we are looking for the next greater element to the right. Starting from the right end means by the time we process any element, we have already seen all elements to its right and stored them in the stack as candidates.Q4. Is LeetCode 496 asked in coding interviews? Yes, it is commonly used as an introduction to the Monotonic Stack pattern at companies like Amazon, Google, and Microsoft. It often appears as a warmup before harder follow-ups like Next Greater Element II (circular array) or Daily Temperatures.Q5. What is the difference between LeetCode 496 and LeetCode 739 Daily Temperatures? Both use the same Monotonic Stack pattern. In 496 you return the actual next greater value. In 739 you return the number of days (index difference) until a warmer temperature. The core stack logic is identical.Similar LeetCode Problems to Practice Next739. Daily Temperatures — Medium — days until warmer temperature, same pattern503. Next Greater Element II — Medium — circular array version901. Online Stock Span — Medium — monotonic stack with span counting84. Largest Rectangle in Histogram — Hard — classic monotonic stack42. Trapping Rain Water — Hard — monotonic stack or two pointerConclusionLeetCode 496 Next Greater Element I is the perfect entry point into the Monotonic Stack pattern. The brute force is easy to understand, but the real learning happens when you see why the stack stays decreasing and how that single insight collapses an O(n²) problem into O(n).Once you truly understand why we pop smaller elements and how the HashMap bridges the gap between precomputation and query answering, the entire family of Next Greater Element problems becomes approachable — including the harder circular and histogram variants.

ArrayStackMonotonic StackHashMapEasyLeetCode

Stack Problems Explained: NGR, NGL, NSR, NSL — The Four-Problem Family You Must Master

IntroductionAmong all the problems built around the Stack data structure, four stand out as a family — they appear repeatedly in coding interviews, competitive programming, and real-world software systems. These four are the Next Greater to the Right (NGR), Next Greater to the Left (NGL), Next Smaller to the Right (NSR), and Next Smaller to the Left (NSL).What makes them special is not just their individual solutions — it is the fact that all four are solved by a single elegant technique called the Monotonic Stack. Learn the pattern once, and you have all four in your toolkit permanently.This guide breaks down each problem with a full solution, step-by-step dry run, edge cases, and the exact reasoning behind every decision in the code. Whether you are preparing for a technical interview or simply want to deeply understand this pattern — you are in the right place.The Story That Makes This ClickBefore any code, let us understand this family of problems with one real-world story.Imagine you are standing in a queue at a cricket stadium. Everyone in the queue has a different height. You are standing somewhere in the middle. You look to your right and ask — who is the first person taller than me? That is your Next Greater Element to the Right (NGR).Now you look to your left — who is the first person taller than me on this side? That is your Next Greater to the Left (NGL).Now instead of taller, you ask shorter — who is the first shorter person to my right? That is Next Smaller to the Right (NSR).And shorter to your left? That is Next Smaller to the Left (NSL).Same queue. Same people. Four different questions. Four different answers. This is exactly what these four problems are about — and they all share the same solution pattern.What Is a Monotonic Stack?A monotonic stack is just a regular stack with one rule — elements inside it are always maintained in a specific order, either always increasing or always decreasing from bottom to top.You never enforce this rule explicitly. It happens naturally as you pop elements that violate the order before pushing a new one. This popping step is the key insight — the moment you pop an element, you have found its answer for the current element being processed.This one pattern solves all four problems. Only two small details change between them — the direction of traversal and the comparison condition inside the while loop.The Four Problems — Quick ReferenceProblemDirectionWhat You WantProblem LinksNGRTraverse Right to LeftFirst greater on right"Next Greater Element GFG"NGLTraverse Left to RightFirst greater on left"Previous Greater Element GFG"NSRTraverse Right to LeftFirst smaller on right"Next Smaller Element GFG"NSLTraverse Left to RightFirst smaller on left"Previous Smaller Element GFG"Problem 1 — Next Greater Element to Right (NGR)GFG Problem: Search "Next Greater Element" on GeeksForGeeks Difficulty: Medium | Accuracy: 32.95% | Submissions: 515K+The QuestionFor each element in the array, find the first element to its right that is strictly greater than it. If none exists, return -1.Input: [1, 3, 2, 4] Output: [3, 4, 4, -1]Input: [6, 8, 0, 1, 3] Output: [8, -1, 1, 3, -1]Real World ExampleThink of the stock market. You have daily closing prices: [1, 3, 2, 4]. For each day, you want to know — on which future day will the price first exceed today's price? Day 1 has price 1, first exceeded on Day 2 with price 3. Day 2 has price 3, first exceeded on Day 4 with price 4. Day 3 has price 2, also first exceeded on Day 4 with price 4. Day 4 has no future day, so -1. This is exactly NGR — and it is literally used in financial software to detect price breakout points.The IntuitionThe brute force is obvious — for every element, scan everything to its right and find the first greater one. That works but it is O(n²). For an array of 10⁶ elements that becomes 10¹² operations. It will time out on any large input.The stack insight is this — traverse right to left. As you move left, the stack always holds elements you have already seen on the right side. These are the candidates for being the next greater element. Before pushing the current element, pop all stack elements that are smaller than or equal to it. Why? Because the current element is blocking them — for any future element to the left, the current element will always be encountered first, so those smaller popped elements can never be an answer for anything. Whatever remains on top of the stack after popping is the answer for the current element.Step-by-Step Dry RunArray: [1, 3, 2, 4], traversing right to left.i=3, element is 4. Stack is empty. Answer for index 3 is -1. Push 4. Stack: [4]i=2, element is 2. Top of stack is 4, which is greater than 2. Answer for index 2 is 4. Push 2. Stack: [4, 2]i=1, element is 3. Top of stack is 2, which is not greater than 3. Pop 2. Top is now 4, which is greater than 3. Answer for index 1 is 4. Push 3. Stack: [4, 3]i=0, element is 1. Top of stack is 3, which is greater than 1. Answer for index 0 is 3. Push 1. Stack: [4, 3, 1]Answers collected right to left: [-1, 4, 4, 3] After Collections.reverse(): [3, 4, 4, -1] ✓The Code// NGR — Next Greater Element to Rightclass Solution {public ArrayList<Integer> nextLargerElement(int[] arr) {ArrayList<Integer> result = new ArrayList<>();Stack<Integer> st = new Stack<>();// Traverse from RIGHT to LEFTfor (int i = arr.length - 1; i >= 0; i--) {// Pop all elements smaller than or equal to current// They can never be the answer for any element to the leftwhile (!st.empty() && arr[i] >= st.peek()) {st.pop();}// Whatever is on top now is the next greater elementif (st.empty()) {result.add(-1);} else {result.add(st.peek());}// Push current — it is a candidate for elements to the leftst.push(arr[i]);}// Collected answers right to left, so reverse before returningCollections.reverse(result);return result;}}Edge CasesAll elements decreasing — Input: [5, 4, 3, 2, 1] Output: [-1, -1, -1, -1, -1] Every element has no greater element to its right. Traversing right to left, each new element is larger than everything already in the stack, so the stack gets cleared and the answer is always -1.All elements increasing — Input: [1, 2, 3, 4, 5] Output: [2, 3, 4, 5, -1] Each element's next greater is simply the next element in the array. The last element always gets -1 since nothing exists to its right.All elements equal — Input: [3, 3, 3, 3] Output: [-1, -1, -1, -1] Equal elements do not count as greater. The pop condition uses >= so equals get removed from the stack, ensuring duplicates never answer each other.Single element — Input: [7] Output: [-1] Nothing to the right, always -1.Why only 32.95% accuracy on GFG? Most people either forget to reverse the result at the end, use the wrong comparison in the while loop, or submit a brute force O(n²) solution that times out on large inputs.Problem 2 — Next Greater Element to Left / Previous Greater Element (NGL)GFG Problem: Search "Previous Greater Element" on GeeksForGeeks Difficulty: Medium | Accuracy: 68.93% | Submissions: 7K+The QuestionFor each element in the array, find the first element to its left that is strictly greater than it. If none exists, return -1.Input: [10, 4, 2, 20, 40, 12, 30] Output: [-1, 10, 4, -1, -1, 40, 40]Real World ExampleImagine you are a junior employee at a company. For each person in the office, you want to know — who is the first senior person sitting to their left who earns more? This is NGL. It is used in organizational hierarchy systems, salary band analysis tools, and even in database query optimizers to find the nearest dominant record on the left side.The IntuitionThis is the mirror image of NGR. Instead of traversing right to left, we traverse left to right. The stack holds elements we have already seen from the left side — these are candidates for being the previous greater element. For each new element, pop everything from the stack that is smaller than or equal to it. Whatever remains on top is the first greater element to its left. Then push the current element for future use.No reverse is needed here because we are already going left to right and building the result in order.Step-by-Step Dry RunArray: [10, 4, 2, 20, 40, 12, 30], traversing left to right.i=0, element is 10. Stack is empty. Answer is -1. Push 10. Stack: [10]i=1, element is 4. Top is 10, greater than 4. Answer is 10. Push 4. Stack: [10, 4]i=2, element is 2. Top is 4, greater than 2. Answer is 4. Push 2. Stack: [10, 4, 2]i=3, element is 20. Top is 2, not greater than 20. Pop 2. Top is 4, not greater. Pop 4. Top is 10, not greater. Pop 10. Stack is empty. Answer is -1. Push 20. Stack: [20]i=4, element is 40. Top is 20, not greater. Pop 20. Stack empty. Answer is -1. Push 40. Stack: [40]i=5, element is 12. Top is 40, greater than 12. Answer is 40. Push 12. Stack: [40, 12]i=6, element is 30. Top is 12, not greater than 30. Pop 12. Top is 40, greater than 30. Answer is 40. Push 30. Stack: [40, 30]Result: [-1, 10, 4, -1, -1, 40, 40] ✓ No reverse needed.The Code// NGL — Next Greater Element to Left (Previous Greater Element)class Solution {static ArrayList<Integer> preGreaterEle(int[] arr) {Stack<Integer> st = new Stack<>();ArrayList<Integer> result = new ArrayList<>();// Traverse LEFT to RIGHT — no reverse neededfor (int i = 0; i <= arr.length - 1; i++) {// Pop all elements smaller than or equal to currentwhile (!st.empty() && arr[i] >= st.peek()) {st.pop();}// Top of stack is the previous greater elementif (!st.empty() && st.peek() > arr[i]) {result.add(st.peek());} else {result.add(-1);}// Push current for future elementsst.push(arr[i]);}return result;}}Edge CasesStrictly increasing array — Input: [10, 20, 30, 40] Output: [-1, -1, -1, -1] Each new element is larger than everything before it, so the stack always gets fully cleared. No previous greater exists for any element.First element is always -1 — regardless of its value, the first element has nothing to its left. The stack is empty at i=0, so the answer is always -1 for index 0. This is guaranteed by the logic.Duplicate values — Input: [5, 5, 5] Output: [-1, -1, -1] Equal elements do not qualify as greater. The pop condition uses >= so duplicates get removed from the stack and never answer each other.Problem 3 — Next Smaller Element to Right (NSR)GFG Problem: Search "Next Smaller Element" on GeeksForGeeks Difficulty: Medium | Accuracy: 36.26% | Submissions: 225K+The QuestionFor each element in the array, find the first element to its right that is strictly smaller than it. If none exists, return -1.Input: [4, 8, 5, 2, 25] Output: [2, 5, 2, -1, -1]Input: [13, 7, 6, 12] Output: [7, 6, -1, -1]Real World ExampleYou work at a warehouse. Shelves have items of weights: [4, 8, 5, 2, 25] kg. For each item, the system needs to find the first lighter item sitting to its right on the shelf — this is used to optimize load balancing and shelf arrangement algorithms. Item of 4 kg — first lighter to the right is 2 kg. Item of 8 kg — first lighter is 5 kg. Item of 5 kg — first lighter is 2 kg. Items of 2 kg and 25 kg have no lighter item to their right, so -1.The IntuitionNSR is structurally identical to NGR — we traverse right to left and collect answers, then reverse. The only change is the pop condition. In NGR we popped elements smaller than or equal to current because we wanted greater. Here we want smaller, so we pop elements greater than or equal to current. After popping, whatever remains on top is the first smaller element to the right.Step-by-Step Dry RunArray: [4, 8, 5, 2, 25], traversing right to left.i=4, element is 25. Stack is empty. Answer is -1. Push 25. Stack: [25]i=3, element is 2. Top is 25, which is greater than or equal to 2. Pop 25. Stack is empty. Answer is -1. Push 2. Stack: [2]i=2, element is 5. Top is 2, which is less than 5. Answer is 2. Push 5. Stack: [2, 5]i=1, element is 8. Top is 5, which is less than 8. Answer is 5. Push 8. Stack: [2, 5, 8]i=0, element is 4. Top is 8, which is greater than or equal to 4. Pop 8. Top is 5, which is greater than or equal to 4. Pop 5. Top is 2, which is less than 4. Answer is 2. Push 4. Stack: [2, 4]Answers collected right to left: [-1, -1, 2, 5, 2] After Collections.reverse(): [2, 5, 2, -1, -1] ✓The Code// NSR — Next Smaller Element to Rightclass Solution {static ArrayList<Integer> nextSmallerEle(int[] arr) {Stack<Integer> st = new Stack<>();ArrayList<Integer> result = new ArrayList<>();// Traverse RIGHT to LEFTfor (int i = arr.length - 1; i >= 0; i--) {// Pop elements greater than or equal to current// Opposite of NGR — we want smaller, so clear the bigger oneswhile (!st.empty() && arr[i] <= st.peek()) {st.pop();}// Top is now the next smaller elementif (!st.empty() && st.peek() < arr[i]) {result.add(st.peek());} else {result.add(-1);}st.push(arr[i]);}Collections.reverse(result);return result;}}Edge CasesStrictly decreasing array — Input: [5, 4, 3, 2, 1] Output: [4, 3, 2, 1, -1] Each element's next smaller is simply the next element in the array. Last element is always -1.Strictly increasing array — Input: [1, 2, 3, 4, 5] Output: [-1, -1, -1, -1, -1] No element has a smaller element to its right since the array only grows.Last element is always -1 — nothing exists to its right regardless of its value.Single element — Input: [42] Output: [-1]Why 36.26% accuracy on GFG? The most common mistake is keeping the NGR pop condition (arr[i] >= st.peek()) and only changing the problem description in your head. The pop condition must flip to arr[i] <= st.peek() for NSR. Forgetting this gives completely wrong answers that look plausible, which makes the bug hard to spot.Problem 4 — Next Smaller Element to Left / Previous Smaller Element (NSL)GFG Problem: Search "Previous Smaller Element" on GeeksForGeeksThe QuestionFor each element in the array, find the first element to its left that is strictly smaller than it. If none exists, return -1.Input: [4, 8, 5, 2, 25] Output: [-1, 4, 4, -1, 2]Real World ExampleSame warehouse. Now the system looks left instead of right. For the item weighing 8 kg, the first lighter item to its left is 4 kg. For 25 kg, the first lighter to its left is 2 kg. For 4 kg, nothing lighter exists to its left so -1. For 2 kg, nothing lighter to its left so -1. This kind of lookback query appears in time-series analysis, price history tracking, and sensor data processing.The IntuitionNSL is the mirror of NSR, exactly as NGL was the mirror of NGR. We traverse left to right (no reverse needed). We maintain a stack of candidates from the left. For each element, pop all elements greater than or equal to it — they cannot be the answer since they are not smaller. Whatever remains on top is the first smaller element to the left. Push current and move on.Step-by-Step Dry RunArray: [4, 8, 5, 2, 25], traversing left to right.i=0, element is 4. Stack is empty. Answer is -1. Push 4. Stack: [4]i=1, element is 8. Top is 4, which is less than 8. Answer is 4. Push 8. Stack: [4, 8]i=2, element is 5. Top is 8, which is greater than or equal to 5. Pop 8. Top is 4, which is less than 5. Answer is 4. Push 5. Stack: [4, 5]i=3, element is 2. Top is 5, greater than or equal to 2. Pop 5. Top is 4, greater than or equal to 2. Pop 4. Stack is empty. Answer is -1. Push 2. Stack: [2]i=4, element is 25. Top is 2, which is less than 25. Answer is 2. Push 25. Stack: [2, 25]Result: [-1, 4, 4, -1, 2] ✓ No reverse needed.The Code// NSL — Next Smaller Element to Left (Previous Smaller Element)class Solution {static ArrayList<Integer> prevSmallerEle(int[] arr) {Stack<Integer> st = new Stack<>();ArrayList<Integer> result = new ArrayList<>();// Traverse LEFT to RIGHT — no reverse neededfor (int i = 0; i < arr.length; i++) {// Pop elements greater than or equal to currentwhile (!st.empty() && arr[i] <= st.peek()) {st.pop();}// Top is the previous smaller elementif (!st.empty() && st.peek() < arr[i]) {result.add(st.peek());} else {result.add(-1);}st.push(arr[i]);}return result;}}Edge CasesFirst element is always -1 — nothing exists to its left. Stack is empty at i=0 every time.All same elements — Input: [5, 5, 5, 5] Output: [-1, -1, -1, -1] Equal elements do not qualify as smaller. The condition arr[i] <= st.peek() ensures equals are popped and never answer each other.Single element — Input: [9] Output: [-1]The Master Cheat SheetThis is the one table to save and refer to whenever you encounter any of these four problems.VariantTraverse DirectionPop ConditionReverse Result?NGR — Next Greater RightRight to Leftarr[i] >= st.peek()YesNGL — Next Greater LeftLeft to Rightarr[i] >= st.peek()NoNSR — Next Smaller RightRight to Leftarr[i] <= st.peek()YesNSL — Next Smaller LeftLeft to Rightarr[i] <= st.peek()NoTwo rules to remember forever:Rule 1 — Direction. If you are looking to the right, traverse right to left and reverse at the end. If you are looking to the left, traverse left to right and no reverse is needed.Rule 2 — Pop Condition. If you want a greater element, pop when arr[i] >= st.peek() to clear out smaller useless candidates. If you want a smaller element, pop when arr[i] <= st.peek() to clear out bigger useless candidates.Mix these two rules and you derive all four variants instantly without memorizing anything separately.Common Mistakes to AvoidWrong pop condition — Using > instead of >= in the while loop. This causes duplicate values to wrongly answer each other. Always use >= for greater problems and <= for smaller problems inside the while loop.Forgetting to reverse — For right-to-left traversals (NGR and NSR), you collect answers from right to left. You must call Collections.reverse() before returning. Skipping this is the single most common reason for wrong answers on these problems.Not checking empty stack before peek — Always check !st.empty() before calling st.peek(). An empty stack peek throws EmptyStackException at runtime and will crash your solution.Wrong if-condition after the while loop — After the while loop, the if-condition must use strict comparison. For NGR use st.peek() > arr[i]. For NSR use st.peek() < arr[i]. These must be strict — no equals sign here.Confusing traversal direction with answer direction — You traverse right to left for NGR but the answer array is filled left to right. The reverse at the end handles this. Do not try to index directly into the result array to compensate — just use reverse.Time and Space ComplexityAll four problems run in O(n) time and use O(n) space.Even though there is a while loop nested inside the for loop, each element is pushed into the stack exactly once and popped from the stack at most once. So across the entire traversal, the total number of push and pop operations combined is at most 2n — which gives O(n) overall. This is the beauty of the monotonic stack.Why These Four Problems Matter Beyond GFGThese four patterns are not just textbook exercises. They appear as the hidden sub-problem inside some of the hardest stack questions:-Largest Rectangle in Histogram uses NSR and NSL to find the left and right boundaries of each bar.Trapping Rain Water uses NGR and NGL to determine the water level above each position.Stock Span Problem is literally NGL applied directly to stock prices.Sum of Subarray Minimums uses NSR and NSL together to count contributions of each element.Once you master these four patterns deeply, a whole family of hard problems that previously seemed unapproachable suddenly becomes a matter of recognizing the pattern and applying it.Also on This BlogIf you are building your stack foundation from scratch, check out the complete deep-dive here → Stack Data Structure in Java: The Complete Guide — covering everything from what a stack is, LIFO principle, all three implementations, every operation with code, and six practice problems.

MonotonicStackNextGreaterElementStackProblemsJavaGeeksForGeeksStackPattern

Stack Data Structure in Java: The Complete In-Depth Guide

1. What Is a Stack?A Stack is a linear data structure that stores elements in a sequential order, but with one strict rule — you can only insert or remove elements from one end, called the top.It is one of the simplest yet most powerful data structures in computer science. Its strength comes from its constraint. Because everything happens at one end, the behavior of a stack is completely predictable.The formal definition: A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle — the element inserted last is the first one to be removed.Here is what a stack looks like visually: ┌──────────┐ │ 50 │ ← TOP (last inserted, first removed) ├──────────┤ │ 40 │ ├──────────┤ │ 30 │ ├──────────┤ │ 20 │ ├──────────┤ │ 10 │ ← BOTTOM (first inserted, last removed) └──────────┘When you push 60 onto this stack, it goes on top. When you pop, 60 comes out first. That is LIFO.2. Real-World AnalogiesBefore writing a single line of code, it helps to see stacks in the real world. These analogies will make the concept permanently stick.A Pile of Plates In a cafeteria, clean plates are stacked on top of each other. You always pick the top plate. You always place a new plate on top. You never reach into the middle. This is a stack.Browser Back Button Every time you visit a new webpage, it gets pushed onto a history stack. When you press the Back button, the browser pops the most recent page off the stack and takes you there. The page you visited first is at the bottom — you only reach it after going back through everything else.Undo Feature in Text Editors When you type in a document and press Ctrl+Z, the most recent action is undone first. That is because every action you perform is pushed onto a stack. Undo simply pops from that stack.Call Stack in Programming When a function calls another function, the current function's state is pushed onto the call stack. When the inner function finishes, it is popped off and execution returns to the outer function. This is the literal stack your programs run on.A Stack of Books Put five books on a table, one on top of another. You can only take the top book without knocking the pile over. That is a stack.3. The LIFO Principle ExplainedLIFO stands for Last In, First Out.It means whatever you put in last is the first thing to come out. This is the exact opposite of a Queue (which is FIFO — First In, First Out).Let us trace through an example step by step:Start: Stack is empty → []Push 10 → [10] (10 is at the top)Push 20 → [10, 20] (20 is at the top)Push 30 → [10, 20, 30] (30 is at the top)Pop → returns 30 (30 was last in, first out) Stack: [10, 20]Pop → returns 20 Stack: [10]Peek → returns 10 (just looks, does not remove) Stack: [10]Pop → returns 10 Stack: [] (stack is now empty)Every single operation happens only at the top. The bottom of the stack is never directly accessible.4. Stack Operations & Time ComplexityA stack supports the following core operations:OperationDescriptionTime Complexitypush(x)Insert element x onto the top of the stackO(1)pop()Remove and return the top elementO(1)peek() / top()Return the top element without removing itO(1)isEmpty()Check if the stack has no elementsO(1)isFull()Check if the stack has reached its capacity (Array only)O(1)size()Return the number of elements in the stackO(1)search(x)Find position of element from top (Java built-in only)O(n)All primary stack operations — push, pop, peek, isEmpty — run in O(1) constant time. This is what makes the stack so efficient. It does not matter whether the stack has 10 elements or 10 million — these operations are always instant.Space complexity for a stack holding n elements is O(n).5. Implementation 1 — Using a Static ArrayThis is the most fundamental way to implement a stack. We use a fixed-size array and a variable called top to track where the top of the stack currently is.How it works:top starts at -1 (stack is empty)On push: increment top, then place the element at arr[top]On pop: return arr[top], then decrement topOn peek: return arr[top] without changing it// StackUsingArray.javapublic class StackUsingArray { private int[] arr; private int top; private int capacity; // Constructor — initialize with a fixed capacity public StackUsingArray(int capacity) { this.capacity = capacity; arr = new int[capacity]; top = -1; } // Push: add element to the top public void push(int value) { if (isFull()) { System.out.println("Stack Overflow! Cannot push " + value); return; } arr[++top] = value; System.out.println("Pushed: " + value); } // Pop: remove and return top element public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } return arr[top--]; } // Peek: view the top element without removing public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return arr[top]; } // Check if stack is empty public boolean isEmpty() { return top == -1; } // Check if stack is full public boolean isFull() { return top == capacity - 1; } // Return current size public int size() { return top + 1; } // Display all elements public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); for (int i = top; i >= 0; i--) { System.out.print(arr[i] + " "); } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingArray stack = new StackUsingArray(5); stack.push(10); stack.push(20); stack.push(30); stack.push(40); stack.push(50); stack.push(60); // This will trigger Stack Overflow stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 10Pushed: 20Pushed: 30Pushed: 40Pushed: 50Stack Overflow! Cannot push 60Stack (top → bottom): 50 40 30 20 10Peek: 50Pop: 50Pop: 40Stack (top → bottom): 30 20 10Size: 3Key Points about Array Implementation:Fixed size — you must declare capacity upfrontVery fast — direct array index accessStack Overflow is possible if capacity is exceededMemory is pre-allocated even if stack is not full6. Implementation 2 — Using an ArrayListAn ArrayList-based stack removes the fixed-size limitation. The ArrayList grows dynamically, so you never have to worry about stack overflow due to capacity.How it works:The end of the ArrayList acts as the topadd() is used for pushremove(size - 1) is used for popget(size - 1) is used for peek// StackUsingArrayList.javaimport java.util.ArrayList;public class StackUsingArrayList { private ArrayList<Integer> list; // Constructor public StackUsingArrayList() { list = new ArrayList<>(); } // Push: add to the end (which is our top) public void push(int value) { list.add(value); System.out.println("Pushed: " + value); } // Pop: remove and return the last element public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } int top = list.get(list.size() - 1); list.remove(list.size() - 1); return top; } // Peek: view the last element public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return list.get(list.size() - 1); } // Check if stack is empty public boolean isEmpty() { return list.isEmpty(); } // Return size public int size() { return list.size(); } // Display elements from top to bottom public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); for (int i = list.size() - 1; i >= 0; i--) { System.out.print(list.get(i) + " "); } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingArrayList stack = new StackUsingArrayList(); stack.push(5); stack.push(15); stack.push(25); stack.push(35); stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Is Empty: " + stack.isEmpty()); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 5Pushed: 15Pushed: 25Pushed: 35Stack (top → bottom): 35 25 15 5Peek: 35Pop: 35Pop: 25Stack (top → bottom): 15 5Is Empty: falseSize: 2Key Points about ArrayList Implementation:Dynamic size — grows automatically as neededNo overflow riskSlight overhead compared to raw array due to ArrayList internalsExcellent for most practical use cases7. Implementation 3 — Using a LinkedListA LinkedList-based stack is the most memory-efficient approach when you do not know the stack size in advance. Each element (node) holds data and a pointer to the next node. The head of the LinkedList acts as the top of the stack.How it works:Each node stores a value and a reference to the node below itPush creates a new node and makes it the new headPop removes the head node and returns its valuePeek returns the head node's value without removing it// StackUsingLinkedList.javapublic class StackUsingLinkedList { // Inner Node class private static class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } private Node top; // Head of the linked list = top of stack private int size; // Constructor public StackUsingLinkedList() { top = null; size = 0; } // Push: create new node and link it to top public void push(int value) { Node newNode = new Node(value); newNode.next = top; // new node points to current top top = newNode; // new node becomes the new top size++; System.out.println("Pushed: " + value); } // Pop: remove and return top node's data public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } int value = top.data; top = top.next; // move top pointer to next node size--; return value; } // Peek: return top node's data without removing public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return top.data; } // Check if empty public boolean isEmpty() { return top == null; } // Return size public int size() { return size; } // Display elements from top to bottom public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); Node current = top; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingLinkedList stack = new StackUsingLinkedList(); stack.push(100); stack.push(200); stack.push(300); stack.push(400); stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 100Pushed: 200Pushed: 300Pushed: 400Stack (top → bottom): 400 300 200 100Peek: 400Pop: 400Pop: 300Stack (top → bottom): 200 100Size: 2Key Points about LinkedList Implementation:Truly dynamic — each node allocated only when neededNo wasted memory from pre-allocationSlightly more memory per element (each node carries a pointer)Ideal for stacks where size is completely unknown8. Java's Built-in Stack ClassJava provides a ready-made Stack class inside java.util. It extends Vector and is thread-safe by default.// JavaBuiltinStack.javaimport java.util.Stack;public class JavaBuiltinStack { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); // Push elements stack.push(10); stack.push(20); stack.push(30); stack.push(40); System.out.println("Stack: " + stack); // Peek — look at top without removing System.out.println("Peek: " + stack.peek()); // Pop — remove top System.out.println("Pop: " + stack.pop()); System.out.println("After pop: " + stack); // Search — returns 1-based position from top System.out.println("Search 20: position " + stack.search(20)); // isEmpty System.out.println("Is Empty: " + stack.isEmpty()); // Size System.out.println("Size: " + stack.size()); }}```**Output:**```Stack: [10, 20, 30, 40]Peek: 40Pop: 40After pop: [10, 20, 30]Search 20: position 2Is Empty: falseSize: 3Important Note: In modern Java development, it is often recommended to use Deque (specifically ArrayDeque) instead of Stack for better performance, since Stack is synchronized and carries the overhead of Vector.// Using ArrayDeque as a stack (modern preferred approach)import java.util.ArrayDeque;import java.util.Deque;public class ModernStack { public static void main(String[] args) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(10); // pushes to front stack.push(20); stack.push(30); System.out.println("Top: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Stack: " + stack); }}9. Comparison of All ImplementationsFeatureArrayArrayListLinkedListJava StackArrayDequeSizeFixedDynamicDynamicDynamicDynamicStack Overflow RiskYesNoNoNoNoMemory UsagePre-allocatedAuto-growsPer-node overheadAuto-growsAuto-growsPush TimeO(1)O(1) amortizedO(1)O(1)O(1)Pop TimeO(1)O(1)O(1)O(1)O(1)Peek TimeO(1)O(1)O(1)O(1)O(1)Thread SafeNoNoNoYesNoBest ForKnown size, max speedGeneral useUnknown/huge sizeLegacy codeModern Java10. Advantages & DisadvantagesAdvantagesAdvantageExplanationSimple to implementVery few rules and operations to worry aboutO(1) operationsPush, pop, and peek are all constant timeMemory efficientNo extra pointers needed (array-based)Supports recursionThe call stack is itself a stackEasy undo/redoNatural fit for reversible action trackingBacktrackingPerfectly suited for maze, puzzle, and game solvingExpression evaluationPowers compilers and calculatorsDisadvantagesDisadvantageExplanationLimited accessCannot access elements in the middle directlyFixed size (array)Array-based stacks overflow if size is exceededNo random accessYou cannot do stack[2] — only top is accessibleMemory waste (array)Pre-allocated array wastes space if underusedNot suitable for all problemsMany problems need queues, trees, or graphs insteadStack overflow in recursionVery deep recursion can overflow the JVM call stack11. Real-World Use Cases of StackUnderstanding when to use a stack is just as important as knowing how to implement one. Here is where stacks show up in real software:Function Call Management (Call Stack) Every time your Java program calls a method, the JVM pushes that method's frame onto the call stack. When the method returns, the frame is popped. This is why you see "StackOverflowError" when you write infinite recursion.Undo and Redo Operations Text editors, image editors (Photoshop), and IDEs use two stacks — one for undo history and one for redo history. Every action pushes onto the undo stack. Ctrl+Z pops from it and pushes to the redo stack.Browser Navigation Your browser maintains a back-stack and a forward-stack. Visiting a new page pushes to the back-stack. Pressing Back pops from it and pushes to the forward-stack.Expression Evaluation and Conversion Compilers use stacks to evaluate arithmetic expressions and convert between infix, prefix, and postfix notations. For example: 3 + 4 * 2 must be evaluated considering operator precedence — this is done with a stack.Balanced Parentheses Checking Linters, compilers, and IDEs use stacks to check if brackets are balanced: {[()]} is valid, {[(])} is not.Backtracking Algorithms Maze solving, N-Queens, Sudoku solvers, and depth-first search all use stacks (explicitly or via recursion) to backtrack to previous states when a path fails.Syntax Parsing Compilers parse source code using stacks to match opening and closing constructs like if/else, try/catch, { and }.12. Practice Problems with Full SolutionsHere is where things get really interesting. These problems will sharpen your stack intuition and prepare you for coding interviews.Problem 1 — Reverse a String Using a StackDifficulty: EasyProblem: Write a Java program to reverse a string using a Stack.Approach: Push every character of the string onto a stack, then pop them all. Since LIFO reverses the order, the characters come out reversed.// ReverseString.javaimport java.util.Stack;public class ReverseString { public static String reverse(String str) { Stack<Character> stack = new Stack<>(); // Push all characters for (char c : str.toCharArray()) { stack.push(c); } // Pop all characters to build reversed string StringBuilder reversed = new StringBuilder(); while (!stack.isEmpty()) { reversed.append(stack.pop()); } return reversed.toString(); } public static void main(String[] args) { System.out.println(reverse("hello")); // olleh System.out.println(reverse("java")); // avaj System.out.println(reverse("racecar")); // racecar (palindrome) System.out.println(reverse("datastructure")); // erutcurtasatad }}Problem 2 — Check Balanced ParenthesesDifficulty: Easy–MediumProblem: Given a string containing (, ), {, }, [, ], determine if the brackets are balanced.Approach: Push every opening bracket onto the stack. When you see a closing bracket, check if it matches the top of the stack. If it does, pop. If it does not, the string is unbalanced.// BalancedParentheses.javaimport java.util.Stack;public class BalancedParentheses { public static boolean isBalanced(String expr) { Stack<Character> stack = new Stack<>(); for (char c : expr.toCharArray()) { // Push all opening brackets if (c == '(' || c == '{' || c == '[') { stack.push(c); } // For closing brackets, check the top of stack else if (c == ')' || c == '}' || c == ']') { if (stack.isEmpty()) return false; char top = stack.pop(); if (c == ')' && top != '(') return false; if (c == '}' && top != '{') return false; if (c == ']' && top != '[') return false; } } // Stack must be empty at the end for a balanced expression return stack.isEmpty(); } public static void main(String[] args) { System.out.println(isBalanced("{[()]}")); // true System.out.println(isBalanced("{[(])}")); // false System.out.println(isBalanced("((()))")); // true System.out.println(isBalanced("{]")); // false System.out.println(isBalanced("")); // true (empty is balanced) }}Problem 3 — Reverse a Stack (Without Extra Data Structure)Difficulty: Medium–HardProblem: Reverse all elements of a stack using only recursion — no array or extra stack allowed.Approach: This is a classic recursion problem. You need two recursive functions:insertAtBottom(stack, item) — inserts an element at the very bottom of the stackreverseStack(stack) — pops all elements, reverses, and uses insertAtBottom to rebuild// ReverseStack.javaimport java.util.Stack;public class ReverseStack { // Insert an element at the bottom of the stack public static void insertAtBottom(Stack<Integer> stack, int item) { if (stack.isEmpty()) { stack.push(item); return; } int top = stack.pop(); insertAtBottom(stack, item); stack.push(top); } // Reverse the stack using insertAtBottom public static void reverseStack(Stack<Integer> stack) { if (stack.isEmpty()) return; int top = stack.pop(); reverseStack(stack); // reverse the remaining stack insertAtBottom(stack, top); // insert popped element at bottom } public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println("Before: " + stack); // [1, 2, 3, 4, 5] reverseStack(stack); System.out.println("After: " + stack); // [5, 4, 3, 2, 1] }}Problem 4 — Evaluate a Postfix ExpressionDifficulty: MediumProblem: Evaluate a postfix (Reverse Polish Notation) expression. Example: "2 3 4 * +" should return 14 because it is 2 + (3 * 4).Approach: Scan left to right. If you see a number, push it. If you see an operator, pop two numbers, apply the operator, and push the result.// PostfixEvaluation.javaimport java.util.Stack;public class PostfixEvaluation { public static int evaluate(String expression) { Stack<Integer> stack = new Stack<>(); String[] tokens = expression.split(" "); for (String token : tokens) { // If it's a number, push it if (token.matches("-?\\d+")) { stack.push(Integer.parseInt(token)); } // If it's an operator, pop two and apply else { int b = stack.pop(); // second operand int a = stack.pop(); // first operand switch (token) { case "+": stack.push(a + b); break; case "-": stack.push(a - b); break; case "*": stack.push(a * b); break; case "/": stack.push(a / b); break; } } } return stack.pop(); } public static void main(String[] args) { System.out.println(evaluate("2 3 4 * +")); // 14 → 2 + (3*4) System.out.println(evaluate("5 1 2 + 4 * + 3 -")); // 14 → 5+((1+2)*4)-3 System.out.println(evaluate("3 4 +")); // 7 }}Problem 5 — Next Greater ElementDifficulty: MediumProblem: For each element in an array, find the next greater element to its right. If none exists, output -1.Example: Input: [4, 5, 2, 10, 8] → Output: [5, 10, 10, -1, -1]Approach: Iterate right to left. Maintain a stack of candidates. For each element, pop all stack elements that are smaller than or equal to it — they can never be the answer for any element to the left. The top of the stack (if not empty) is the next greater element.// NextGreaterElement.javaimport java.util.Stack;import java.util.Arrays;public class NextGreaterElement { public static int[] nextGreater(int[] arr) { int n = arr.length; int[] result = new int[n]; Stack<Integer> stack = new Stack<>(); // stores elements, not indices // Traverse from right to left for (int i = n - 1; i >= 0; i--) { // Pop elements smaller than or equal to current while (!stack.isEmpty() && stack.peek() <= arr[i]) { stack.pop(); } // Next greater element result[i] = stack.isEmpty() ? -1 : stack.peek(); // Push current element for future comparisons stack.push(arr[i]); } return result; } public static void main(String[] args) { int[] arr1 = {4, 5, 2, 10, 8}; System.out.println(Arrays.toString(nextGreater(arr1))); // [5, 10, 10, -1, -1] int[] arr2 = {1, 3, 2, 4}; System.out.println(Arrays.toString(nextGreater(arr2))); // [3, 4, 4, -1] int[] arr3 = {5, 4, 3, 2, 1}; System.out.println(Arrays.toString(nextGreater(arr3))); // [-1, -1, -1, -1, -1] }}Problem 6 — Sort a Stack Using RecursionDifficulty: HardProblem: Sort a stack in ascending order (smallest on top) using only recursion — no loops, no extra data structure.// SortStack.javaimport java.util.Stack;public class SortStack { // Insert element in correct sorted position public static void sortedInsert(Stack<Integer> stack, int item) { if (stack.isEmpty() || item > stack.peek()) { stack.push(item); return; } int top = stack.pop(); sortedInsert(stack, item); stack.push(top); } // Sort the stack public static void sortStack(Stack<Integer> stack) { if (stack.isEmpty()) return; int top = stack.pop(); sortStack(stack); // sort remaining sortedInsert(stack, top); // insert top in sorted position } public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(34); stack.push(3); stack.push(31); stack.push(98); stack.push(92); stack.push(23); System.out.println("Before sort: " + stack); sortStack(stack); System.out.println("After sort: " + stack); // smallest on top }}13. Summary & Key TakeawaysA stack is a simple, elegant, and powerful data structure. Here is everything in one place:What it is: A linear data structure that follows LIFO — Last In, First Out.Core operations: push (add to top), pop (remove from top), peek (view top), isEmpty — all in O(1) time.Three ways to implement it in Java:Array-based: fast, fixed size, risk of overflowArrayList-based: dynamic, easy, slightly more overheadLinkedList-based: truly dynamic, memory-efficient per-element, best for unknown sizesWhen to use it:Undo/redo systemsBrowser navigationBalancing brackets and parenthesesEvaluating mathematical expressionsBacktracking problemsManaging recursive function callsDepth-first searchWhen NOT to use it:When you need random access to elementsWhen insertion/deletion is needed from both ends (use Deque)When you need to search efficiently (use HashMap or BST)Modern Java recommendation: Prefer ArrayDeque over the legacy Stack class for non-thread-safe scenarios. Use Stack only when you need synchronized access.The stack is one of those data structures that once you truly understand, you start seeing it everywhere — in your browser, in your IDE, in recursive algorithms, and deep within the operating system itself.This article covered everything from the fundamentals of the Stack data structure to multiple Java implementations, time complexity analysis, real-world applications, and six practice problems of increasing difficulty. Bookmark it as a reference and revisit the practice problems regularly — they are the real test of your understanding.

DataStructuresJavaStackDataStructureLIFO