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
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!!!
No comments:
Post a Comment