codehub27

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

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

codehub27

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

java implementation of Deque