A stack is a basic data structure that insert and remove the items using last in first out (LIFO) strategy. The stack is a very powerful data structure. The stack can used when add or remove the element using last in first out order.
Algorithm Explanation
Stack supports push and pop operations.
Push operation adds the item to the array.
Pop operation removes the item from an array.
Push and pop operation use index to move positions.
The stack data structure can implement using an array and linked list.
Source Code
package com.dsacode.DataStructre.stack;
import java.util.Arrays;
import java.util.Stack;
public class StockSpanProblem {
static void calculateSpan(int price[], int n, Integer[] s)
{
Stack < Integer > st = new Stack< Integer >();
st.push(0);
s[0] = 1;
for (int i = 1; i < n; i++)
{
while (!st.empty() && price[st.peek()] < price[i])
st.pop();
s[i] = (st.empty())? (i + 1) : (i - st.peek());
st.push(i);
}
}
static void printArray(Integer[] s, int n)
{
for (int i = 0; i < n; i++)
if(i==n-1)
System.out.print(s[i] +"]");
else
System.out.print(s[i] +", ");
}
public static void main(String[] args) {
int price[] = {100, 80, 60, 70, 60, 75, 85};
System.out.println("7 days prices of stack:" + Arrays.toString(price) );
Integer []S = new Integer[price.length];
calculateSpan(price, price.length, S );
System.out.print("Print the calculated span values:[");
printArray(S , price.length);
}
}
Output
Push :12
Push :9
Push :24
Pop :24
Pop :9
Pop :12
Source Explanation
The constructor initializes the stack Array and capacity.
Push operation adds element to the stack. If the stack capacity reaches maximum stack size, It double the size.
Push operation removes the element from the stack.
Pop operation checks the size. If it is empty, it does not remove anything. Otherwise, it remove the last Position and returns the element.
Peek returns the top position without remove the element in stack array.
