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!!!!