Design a data structure to find minimum and maximum value in java

Problem: Design a data structure to find minimum and maximum value in the structure in an efficient way.

How to implement it?

 Create a deque with a stack.

Program:

• ·       First, include the built in packages java.util.Deque, java.util.LinkedList;
• ·       Write a class “stackDeque”. Develop three deque objects. One is for stack; remaining twos are minimum and maximum stack.
• ·       Write the functions for Push and pop.
• ·       Minimum stack and maximum stack implementation are written separately.
• ·       Finally, call the functions to display the minimum and maximum values in the data structure.

Java Program:

import java.util.Deque;

import java.util.LinkedList;

public class stackDeque {

    private Deque<Integer> stack1;

    private Deque<Integer> minStackDeque;

    private Deque<Integer> maxStackDeque;

    public stackDeque() {

        stack1= new LinkedList<>();

       minStackDeque =new LinkedList<>();

        maxStackDeque = new LinkedList<>();

    }

    // insert an element onto the stack (Push).

    public void push(int value) {

        stack1.push(value);

        // min stack implementation

        if (minStackDeque.isEmpty() || value <= minStackDeque.peek()) {

            minStackDeque.push(value);

        } else {

           minStackDeque.push(minStackDeque.peek());

        }

        // max stack implementation

        if (maxStackDeque.isEmpty() || value >= maxStackDeque.peek()) {

           maxStackDeque.push(value);

        } else {

            maxStackDeque.push(maxStackDeque.peek());

        }

    }

    // delete an element from stack (Pop)

    public int pop() {

        if (stack1.isEmpty()) {

            throw new RuntimeException("Stack is empty");

        }

        minStackDeque.pop();

        maxStackDeque.pop();;

        return stack1.pop();

    }

 

    // Minimum stack value extraction

    public int getMin() {

        if (minStackDeque.isEmpty()) {

            throw new RuntimeException("Stack is empty");

        }

        return minStackDeque.peek();

    }

 

    // Maximum stack value extraction

    public int getMax() {

        if (maxStackDeque.isEmpty()) {

            throw new RuntimeException("Stack is empty");

        }

        return maxStackDeque.peek();

    }

 

    // check for stack emptiness

    public boolean isEmpty() {

        return stack1.isEmpty();

    }

 

    public static void main(String[] args) {

        stackDeque stackd1= new stackDeque();

        stackd1.push(23);

        stackd1.push(34);

        System.out.println("Current Max: " + stackd1.getMax());

        System.out.println("Current Min: " + stackd1.getMin());

        stackd1.push(45);

        stackd1.push(56);

        System.out.println("Current Max: " + stackd1.getMax());

        System.out.println("Current Min: " + stackd1.getMin());

        stackd1.pop();

        System.out.println("Current Max: " +stackd1.getMax());

        System.out.println("Current Min: " +  stackd1.getMin());

        stackd1.pop();

        System.out.println("Current Max: " + stackd1.getMax());

        System.out.println("Current Min: " +  stackd1.getMin());

    }

}

Output:

C:\raji\blog>javac stackDeque.java

 C:\raji\blog>java stackDeque

Current Max: 34

Current Min: 23

Current Max: 56

Current Min: 23

Current Max: 45

Current Min: 23

Current Max: 34

Current Min: 23

These are the ways to implement the data structure using deque and stack efficiently. Keep coding!!!

java implementation of Deque

 Deque(double ended Queue) is a type of queue. The elements can be inserted and deleted in both the ends. Deque is implemented in java by the concept of ‘ArrayDeque’.

What is ArrayDeque?

              It is a class available in java. ArrayDeque -Array Double Ended Queue which implement deque in java. It creates a resizable array for storing the queue elements.

Features of ArrayDeque:

• ·       It holds light weight memory.
• ·       Fast access to elements.
• ·       Time performance is constant.
• ·       Resizable.

Implementation of deque in java:

It uses built in packages java.util.ArrayDeque, java.util.deque.

Steps to follow:

• Creation: An object is created for ‘ArrayDeque’.
• Insertion: To insert the data, ‘addFirst’,’addLast’,’offerFirst’ ,’offerLast’ functions are used.
• Removal: To delete the element, it uses ‘removeFirst’ and ‘removeLast’.
• Peek: It extracts the elements from the queue. ‘peekFirst’ and ‘peekLast’ are used.

Program:

import java.util.ArrayDeque;

import java.util.Deque;

public class ArrayDequeSample {

    public static void main(String[] args) {

        // Create an object for deque using ArrayDeque

        Deque<Integer> deque1 = new ArrayDeque<>();

        // insert the elements to the deque

        deque1.addFirst(21);   // insert element to the front end

        deque1.addLast(34);    // insert element to the rear end

        deque1.offerFirst(10); // insert element to the front

        deque1.offerLast(9);  // insert element to the rear

        deque1.offerFirst(57);// insert element to the front

        deque1.offerLast(80);// insert element to the rear

        // Printing the elements in the deque

        System.out.println("The elements of the Deque: " + deque1);

        // extract and delete the elements from the deque

        System.out.println("First element is deleted: " + deque1.removeFirst());

        System.out.println("Last element is deleted: " + deque1.removeLast());

        // The elements in the deque after removals

        System.out.println("The elements of Deque after removals: " + deque1);

        // Extract the elements without deleting them

        System.out.println("The first element is: " + deque1.peekFirst());

        System.out.println("The last element is: " + deque1.peekLast());

    }

}

Output:

C:\raji\blog>javac ArrayDequeSample.java

C:\raji\blog>java ArrayDequeSample

The elements of the Deque: [57, 10, 21, 34, 9, 80]

First element is deleted: 57

Last element is deleted: 80

The elements of Deque after removals: [10, 21, 34, 9]

The first element is: 10

The last element is: 9

This is the way of implementing the deque using ArrayDeque. This is one of the easiest method. Happy coding!!!

Generate numbers (Permutation) in java

               Numbers are magical elements in the field of mathematics. Generating all possible number combinations from a set of numbers is permutation. Let us generate numbers based on this.

How to generate numbers like permutation in java?

Let us create this program using an integer array.

Steps:

àMain method:

• Include the built in packages java.util.ArrayList and java.util.List.
• First, Write the code for class with main() function.
• Next, Declare an integer array with 3 integers as input.
• Now, call a function generateNos() with input array as arguments.
• Finally, print the number received from the function.

à generateNos():

• It create a list(output) for display.
• It has array as Boolean which stores the  ip_used.
• Call the backtrack_it function.It generates the number combination (Permutation).

àbacktrack_it():

• It checks the current number combination is same as the ip_digits, it is added to output.
• Each number is added and marked as used and recursively calling the array until all numbers are iterated.
• Finally, it backtracks the unmarking digit and deleted from the current number combination.

Program:

import java.util.ArrayList;

import java.util.List;

public class GenerateNos {

    public static void main(String[] args) {

        int[] ip_digits = {4, 3, 7};

        List<String> nos = generateNos(ip_digits);

        for (String number : nos) {

            System.out.println(number);

        }

    }

    public static List<String> generateNos(int[] ip_digits) {

        List<String> output = new ArrayList<>();

        boolean[] ip_used = new boolean[ip_digits.length];

        backtrack_it(output, ip_digits, new StringBuilder(), ip_used);

        return output;

    }

    private static void backtrack_it(List<String> output, int[] ip_digits, StringBuilder ip_current, boolean[] ip_used) {

        if (ip_current.length() == ip_digits.length) {

            output.add(ip_current.toString());

            return;

        }

        for (int i = 0; i < ip_digits.length; i++) {

            if (ip_used[i]) continue;

            ip_used[i] = true;

            ip_current.append(ip_digits[i]);

            backtrack_it(output, ip_digits, ip_current, ip_used);

            ip_used[i] = false;

            ip_current.deleteCharAt(ip_current.length() - 1);

        }

    }

}

Output:

C:\raji\blog>javac GenerateNos.java

C:\raji\blog>java GenerateNos

437

473

347

374

743

734

This is the way of generating numbers in java. Here, we generated number combination as permutation. Keep coding!!!

Reverse K elements problem solution in java

Problem : You have a ‘n’ number of elements. You want to reverse a set of elements. Let it be ‘K’ number of elements. How will you solve using a queue and stack. Implement it in java.

Solution in java:

• ·       Create a public class with main() function.
• ·       A member function with the input parameters of queue and the ‘k’ value. It checks whether the queue is null or queue’s size is less than k or k is less than 0.
• ·       If any one of the above is true, it returns the queue.
• ·       Create an integer stack. Push ‘n’ number of elements into the stack.
• ·       Delete(enque) the ‘K’ number of elements and store it into queue.
• ·       Move the remaining elements from the front end to the rear end to preserve the order.

Program:

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

public class ReverseFKElements {

    public static Queue<Integer> reverseFirstK(Queue<Integer> queue1, int k) {

        if (queue1 == null || queue1.size() < k || k <= 0) {

            return queue1;

        }

        Stack<Integer> stack1 = new Stack<>();

        // insert(Push) the elements into the stack.  let it be the first 'K' elements

        for (int i = 0; i < k; i++) {

            stack1.push(queue1.poll());

        }

        // Delete(Enqueue) the elements from the stack and store it into queue.

        while (!stack1.isEmpty()) {

            queue1.add(stack1.pop());

        }

        // Move the remaining elements from the front end to the rear end to preserve the order

        int size = queue1.size();

        for (int i = 0; i < size - k; i++) {

            queue1.add(queue1.poll());

        }

        return queue1;

    }

    public static void main(String[] args) {

        Queue<Integer> queue1 = new LinkedList<>();

        queue1.add(23);

        queue1.add(34);

        queue1.add(45);

        queue1.add(56);

        queue1.add(67);

        queue1.add(78);

        queue1.add(89);

        int k =4 ;

        System.out.println("The original queue with elements: " + queue1);

        queue1 = reverseFirstK(queue1, k);

        System.out.println("The elements of Queue after reversing first " + k + " elements: " + queue1);

    }

}

Output is given below…

C:\raji\blog>javac ReverseFKElements.java

C:\raji\blog>java ReverseFKElements

The original queue with elements: [23, 34, 45, 56, 67, 78, 89]

The elements of Queue after reversing first 4 elements: [56, 45, 34, 23, 67, 78, 89]

Note: This is the one of the efficient method to solve this program. Keep coding!!!!

Other queue implementation in java

               A basic queue is a collection of elements with a front end and rear end. Some of the other types of queue’s are listed below.

PriorityQueue: A queue with priority value associated with it. It dequeued according to the priority. Generally, higher priority is dequeued first.

ArrayDeque : This implementation of queue can be resizable. The elements can be added or removed at both front and back ends.

The java implementations of both queues are given below.

1.Priority Queue implementation in java:

              This program uses the built in packages java.util.PriorityQueue and java.util.Queue.

Steps:

• ·       Develop a class with main() function.
• ·       Create an object for Queue class.
• ·       Insert the data elements to the queue by add() function.
• ·       Deque the elements until the last element and print the queue elements.

Program:

import java.util.PriorityQueue;

import java.util.Queue;

public class PriorityQueueEg {

    public static void main(String[] args) {

        Queue<Integer> priorityQueue1 = new PriorityQueue<>();

        // Enqueue elements

        priorityQueue1.add(310);

        priorityQueue1.add(130);

        priorityQueue1.add(253);

        priorityQueue1.add(454);

        priorityQueue1.add(364);

        // printing the queue elements

        System.out.println("The elements in the PriorityQueue is: " + priorityQueue1);

         // deleting the elements until the queue is empty(Deque)

        while (!priorityQueue1.isEmpty()) {

            System.out.println("The Removed element is: " + priorityQueue1.poll());

        }

    }

}

Output:

C:\raji\blog>javac PriorityQueueEg.java

C:\raji\blog>java PriorityQueueEg

The elements in the PriorityQueue is: [130, 310, 253, 454, 364]

The Removed element is: 130

The Removed element is: 253

The Removed element is: 310

The Removed element is: 364

The Removed element is: 454

Next implementation is given as follows.

ArrayDeque implementation in java:

              This implementation uses the built in packages java.util.ArrayDeque and java.util.Deque.

Steps:

• ·       write a class with main() function.
• ·        Queue class object is created as integer.
• ·       Enque(insert) the data elements to the queue by add() function.
• ·       Delete the elements until the last element and print the queue elements.

Program:

import java.util.ArrayDeque;

import java.util.Deque;

public class ArrayDequeEg {

    public static void main(String[] args) {

        Deque<Integer> deque1 = new ArrayDeque<>();

        // Enqueue(adding) elements at the end

        deque1.addLast(231);

        deque1.addLast(551);

        deque1.addLast(300);

        deque1.addLast(677);    

        // The elements in deque is displayed here

        System.out.println("ArrayDeque: " + deque1);

        // Dequeue(remove) the  elements from the front

        while (!deque1.isEmpty()) {

            System.out.println("Removed element: " + deque1.pollFirst());

        }

    }

}

Output:

C:\raji\blog>javac ArrayDequeEg.java

C:\raji\blog>java ArrayDequeEg

ArrayDeque: [231, 551, 300, 677]

Removed element: 231

Removed element: 551

Removed element: 300

Removed element: 677

These are the other queue implementation in java. Keep coding!!!

Simple Queue implementation in java

    Queue is a collection of elements stored in sequential manner. It has a principle called FIFO (First In First Out). It means the element added in the queue is removed first.The implementation of queue is done easily using java.

The built-in packages in java for implementing queue is given below.

java.util.LinkedList

java.util.Queue

The implementation of simple queue is as follows.

It has 5 basic operations.

Enqueue : It adds the element to the queue.

Dequeue: It removes the element from the queue.

Size : It finds the size of the queue.

isEmpty: It checks the queue has elements or not.

peek() : It finds the front elements.

Steps to implement the program:

First, include the built-in packages.

Create the class  QueueSimple with main () function.

An object is created from builtin class “Queue” as integer.

Add the elements to the queue by using add() function.

Print the elements in the queue.

Using the peek () function to print the front element.

Pool() function is used to delete the element from the queue. This operation is called “Dequeue”.

To check the queue is empty or not, isEmpty() function is used.

Size() function is used to check the size of the queue.

Java code:

import java.util.LinkedList;

import java.util.Queue;

public class QueueSimple {

    public static void main(String[] args) {

        // let us create a queue

        Queue<Integer> queue1 = new LinkedList<>();

        // Insert elements to the queue(Enqueue)

        queue1.add(34);

        queue1.add(45);

        queue1.add(56);

        queue1.add(75);

        queue1.add(89);

        // Print the elements in the queue

        System.out.println("The elements in the Queue are: " + queue1);

        //Get the front element(Peek) and print it

        int front = queue1.peek();

        System.out.println("Front element of the queue is: " + front);

        // Remove elements(Dequeue) from the queue

        int del = queue1.poll();

        System.out.println("Deleted element: " + del);

        // print the queue elements after deleting (dequeuing) an element

        System.out.println("Queue after deletion: " + queue1);

        // Check whether the queue has no elements

        boolean isEmpty = queue1.isEmpty();

        if(isEmpty)

          System.out.println("The queue is empty");

        else

          System.out.println("The queue is not empty");

        // Find the size of the queue

        int size = queue1.size();

        System.out.println("Size of the queue is: " + size);

    }

}

Output:

C:\raji\blog>javac QueueSimple.java

C:\raji\blog>java QueueSimple

The elements in the Queue are: [34, 45, 56, 75, 89]

Front element of the queue is: 34

Deleted element: 34

Queue after deletion: [45, 56, 75, 89]

The queue is not empty

Size of the queue is: 4

This is the way of implementing  simple queue in java. If you have any queries, just drop a comment below.

Keep coding!!!

Java implementation of trapping the rainwater using stack

 Trapping the Rainwater is a classical algorithmic problem. It finds the trapping water on the elevation map. Here, the elevation map is implemented by an array as stack.

Let us implement this algorithm in Java.

1. First, create an integer array for storing the stack. Each element represents a bar in the elevation map. The bar represents the count of trapping water after the rain.
2. Initialize the two pointers. One points to the left side, and another points to the right side of the array.
3. Find the maximum height of the right and left side of the array and store it in two variables.
4. Finally, calculate the trapped water value by moving the pointers towards the center. It’s time to find the maximum and minimum values from the left and right.

Java Implementation

public class TrapitRainWater {

    public static int trapit(int[] h) {

        if (h == null || h.length == 0) {

            return 0;

        }

        int Tleft = 0, Tright = h.length - 1;

        int TleftMax = 0, TrightMax = 0;

        int trappedvalue = 0;

        while (Tleft < Tright) {

            if (h[Tleft] < h[Tright]) {

                if (h[Tleft] >= TleftMax) {

                    TleftMax = h[Tleft];

                } else {

                    trappedvalue += TleftMax - h[Tleft];

                }

                Tleft++;

            } else {

                if (h[Tright] >= TrightMax) {

                    TrightMax = h[Tright];

                } else {

                    trappedvalue += TrightMax - h[Tright];

                }

                Tright--;

            }

        }

        return trappedvalue;

    }

    public static void main(String[] args) {

        int[] h = {1, 0, 2, 3, 4, 1, 0, 3, 1, 0, 3, 2};

        int finalvalue = trapit(h);

        System.out.println("The count of the trapped water is: " + finalvalue);

    }

}

Output:

C:\raji\blog>javac TrapitRainWater.java

C:\raji\blog>java TrapitRainWater

The count of the trapped water is: 11

This is the way of implementing trapping the rain water using stack in Java. Keep coding!!!

If you need any more help with this algorithm or others, feel free to ask!

Largest Rectangle in histogram using java

              It is a classic problem in histogram which finds the largest rectangle. The histogram has a collection of integers represented by an array. Each element denotes the height of the bar.

Here, a stack is used to implement the largest rectangle in histogram.

Let us implement the largest rectangle in histogram.

• ·       First, create a integer stack for storing the histogram.
• ·       Declare an integer variable maxiArea and n.
• ·       Iterate the stack for finding the largest bar in the histogram.
• ·       If the current bar is greater than the bar in the top of the stack, insert the current value to the stack.
• ·       Else the value is popped. Check until the last element.
• ·       Calculate the largest area of the value and display it.

Program:

import java.util.Stack;

public class LargestRectangleHistogram1 {

    public static int largestRectArea(int[] hts) {

        Stack<Integer> stack1 = new Stack<>();

        int maxiArea = 0;

        int n = hts.length;

        for (int i = 0; i < n; i++) {

            while (!stack1.isEmpty() && hts[i] < hts[stack1.peek()]) {

                int ht = hts[stack1.pop()];

                int wth = stack1.isEmpty() ? i : i - stack1.peek() - 1;

                maxiArea = Math.max(maxiArea, ht * wth);

            }

            stack1.push(i);

        }

        while (!stack1.isEmpty()) {

            int ht = hts[stack1.pop()];

            int wth = stack1.isEmpty() ? n : n - stack1.peek() - 1;

            maxiArea = Math.max(maxiArea, ht * wth);

        }

         return maxiArea;

    }

    public static void main(String[] args) {

        int[] hts = {23, 10, 15,46, 72, 50};

        int maxiArea = largestRectArea(hts);

        System.out.println("The area of Largest Rectangle is: " + maxiArea);

    }

}

While executing this program,you will get the below output.

C:\raji\blog>javac LargestRectangleHistogram1.java

C:\raji\blog>java LargestRectangleHistogram1

The area of Largest Rectangle is: 138

That’s all. This is the way of implementing largest rectangle in histogram. Keep coding!!!!

Valid parenthesis checking using Stack in java

     Let us solve a common problem called “Valid parentheses”. It is a problem which checks a given string has a valid parenthesis. It means that the parentheses are nested and closed properly. If you use stack for solving this problem, it is good to be effective.

List of parentheses:

‘(‘ , ’)’ , ’[‘ , ’]’ , ’{‘ , ’}’.

Valid usage of parentheses:

• ‘({[]})’
• ‘{[()]}’
• ‘[{()}]’

Let us implement this program in java.

Program:

• ·       Create a stack for finding the opening parenthese.
• ·       Traverse the string character by character.
• ·       Check for opening parenthesis, if occurs,insert(push) the parenthese into stack.
• ·       If it is a closing parenthesis, check the stack is having its opening parenthesis.
• ·       If these two are matching, pop the element from the stack. Otherwise,print the string is invalid.
• ·       Repeat this until the stack become empty.

Here is the program.

import java.util.Stack;

public class ValidParenthesesStackEg {

    public static boolean isValidorNot(String s) {

        Stack<Character> stack1 = new Stack<>();

 

        for (char c : s.toCharArray()) {

            if (c == '(' || c == '{' || c == '[') {

                stack1.push(c);

            } else if (c == ')' || c == '}' || c == ']') {

                if (stack1.isEmpty()) {

                    return false;

                }

                char top = stack1.pop();

                if ((c == ')' && top != '(') ||

                    (c == '}' && top != '{') ||

                    (c == ']' && top != '[')) {

                    return false;

                }

            }

        }

 

        return stack1.isEmpty();

    }

     public static void main(String[] args) {

        String test1 = "({[]})";

        String test2 = "[{()}]";

        String test3 = "{([";

        if(isValidorNot(test1))

        System.out.println(test1 + " is valid");

        else

          System.out.println(test1 + " is invalid");

        if(isValidorNot(test2))

        System.out.println(test2 + " is valid");

        else

          System.out.println(test2 + " is invalid");

       if(isValidorNot(test3))

        System.out.println(test3 + " is valid");

        else

          System.out.println(test3 + " is invalid");

    }

}

Output:

C:\raji\blog>javac ValidParenthesesStackEg.java

C:\raji\blog>java ValidParenthesesStackEg

({[]}) is valid

[{()}] is valid

{([ is invalid

Using the above implementation, it is efficient to find the string is having valid parenthesis. Keep Coding!!

How to find the Next Greater element in java?

               An array of integers is given. You have to find the next greater element for each element in the array.  This is one of the interview question in java.

Let us find the solution for this problem.

• ·       First, write a class with main function. next, declare an array with some ‘no’ of elements.
• ·       Create a stack with new object “stack1”.
• ·       Check the current element of the array with other elements for greater value. If the value is less, then delete the elements. 
• ·       If the value is greater than the current element, push the current element to stack. otherwise, insert -1 value to stack.
• ·       Finally, print the value. If stack is null, then there is no greater number.

Program:

import java.util.Stack;

public class NextGElement {

    public static int[] nextGElements(int[] arr) {

        int no = arr.length;

        int[] result1 = new int[no];

        Stack<Integer> stack1 = new Stack<>();

        for (int i = no - 1; i >= 0; i--) {

            // delete the elements which are less than or equal to the current element

            while (!stack1.isEmpty() && stack1.peek() <= arr[i]) {

                stack1.pop();

            }

            // If stack is null, there is no bigger number

            result1[i] = stack1.isEmpty() ? -1 : stack1.peek();

            // insert the current element to the stack

            stack1.push(arr[i]);

        }

        return result1;

    }

    public static void main(String[] args) {

        int[] arr1 = {234, 345, 20,530,56};

        int[] result1 = nextGElements(arr1);

         // let us display the output

        System.out.print("The Next Greater Elements are: ");

        for (int value : result1) {

            System.out.print(value + " ");

        }

    }

}

Compile and run the program to get the output.

Here, is the output.

C:\raji\blog>javac NextGElement.java

C:\raji\blog>java NextGElement

The Next Greater Elements are: 345 530 530 -1 -1

Using the above logic, it is easy to implement the next greater element problem in java. Happy coding!!!

The Stock Span Problem in java

    Stocks are everywhere today. This problem deals with stock span calculation for all days. To calculate this, check the stock prices for consecutive days before the day given to you. The logic is to check the stock price on current day with the price on the given day.

This problem can be implemented in java as follows.

• ·       First,use the builtin Stack package.
• ·       Write a public class spanStockCalc with main() function.
• ·       Include a function spanCalculate() with an argument sprices as integer.
• ·       Find the length of the sprices and store it into variable ‘n’.
• ·       Next,create a integer array with the size of n.
• ·       A new object is created for stack.
• ·       Using a for loop, check the two conditions. one is stackis empty or not , another one is check the stack elements with stack’s top elements.
• ·       If these two conditions met, pop the element.
• ·       Repeat the process.
• ·       Finally, insert the element in stack.
• ·       Inside the main function, assign values for array elements.
• ·       Call the function and print the output.

Program:

import java.util.Stack;

public class spanStockCalc {

    // Function to calculate the stock span prices

    public static int[] spanCalculate(int[] sprices) {

        int n = sprices.length;

        int[] span = new int[n];

        Stack<Integer> stack1 = new Stack<>();

        for (int i = 0; i < n; i++) {

            // Calculation

            while (!stack1.isEmpty() && sprices[stack1.peek()] <= sprices[i]) {

                stack1.pop();

            }

            span[i] = (stack1.isEmpty()) ? (i + 1) : (i - stack1.peek());

            // insert the data

            stack1.push(i);

        }

        return span;

    }

    public static void main(String[] args) {

        int[] sprices = {450,30,70, 80, 90,175,120};

        int[] span = spanCalculate(sprices);

        // Final outcome

        System.out.print("Spans: ");

        for (int spans : span) {

            System.out.print(spans + " ");

        }

    }

}

Compile and run the program to get the output.

C:\raji\blog>javac spanStockCalc.java

C:\raji\blog>java spanStockCalc

Spans: 1 1 2 3 4 5 1

Note: Time complexity is O(n).

Stack implementation in java

               Stack is a basic data structure which store the data elements in such a way that LIFO.Stack class is included in java Collections.

The built-in package is: java.util.Stack.

Logic of stack:

• LIFO (Last in First Out): The number which is inserted as last will be removed first.
• Dynamic: The size of stack will be increased or decreased depends on the data.

Operations on Stack:

• push(data) : it is used to add the elements to the stack.
• pop() : It is used to delete a top most data.
• peek() : This is used to view the top element of data.
• search(): It finds a particular data in the stack.
• empty() :It checks whether stack is empty or not.

Java Implementations on Stack Operations:

              This java program implements a stack and its operations. It has following steps.

Steps:

• Include the built in java package.
• A public class is created with main() function.
• A new stack object is created. 5 elements are inserted into stack using push() function.
• The stack elements are displayed using print() statement.
•  peek() function is used to view the top elements without deleting.
• Pop() function deletes the top element of the stack.
• Search() method finds an element in the stack.
• Empty() checks the stack is empty or not.

Program:

import java.util.Stack;

public class StackEg {

    public static void main(String[] args) {

     Stack<Integer> stackobj = new Stack<>();

        // inserting(Pushing) elements

        stackobj.push(100);

        stackobj.push(200);

        stackobj.push(300);

        stackobj.push(400);

        stackobj.push(500);

        // print the stack elements

        System.out.println("Stack : " + stackobj);

        // view the top element(Peek)

        int top1 = stackobj.peek();

        System.out.println("Top element: " + top1);

        // remove the top element in the stack(Pop)

        int popit = stackobj.pop();

        System.out.println("The element which is popped from the stack is: " + popit);

        // printing the stack elements after pop

        System.out.println("Stack after pop: " + stackobj);

        // finding an element

        int pos = stackobj.search(20);

        System.out.println("Position of element: " + pos);

        // finding the stack is empty or not.

        boolean isEmpty = stackobj.empty();

        System.out.println("stack empty " + isEmpty);

    }

}

Output:

C:\raji\blog>javac StackEg.java

C:\raji\blog>java StackEg

Stack : [100, 200, 300, 400, 500]

Top element: 500

The element which is popped from the stack is: 500

Stack after pop: [100, 200, 300, 400]

Position of element: -1

stack empty false

Note: Stack is useful when backtracking is needed and process the elements in last in first out order.