given NonZeroSumStack.txt //this is the source code of NonZeroNumStack.java impo
ID: 3711649 • Letter: G
Question
given
NonZeroSumStack.txt
//this is the source code of NonZeroNumStack.java
import java.util.*;
public class NonZeroNumStack{
private int[] data;
private int total;
public NonZeroNumStack(){
data=new int[10];
total=0;
}
public int pop(){
if(isEmpty())
return 0;
else{
return data[--total];
}
}
public int top(){
if(isEmpty())
return 0;
else
return data[total-1];
}
public void push(int num){
if(num==0) return;
if(data.length==total){
int[] tmp=new int[total*2];
for(int i=0; i tmp[i]=data[i];
data=tmp;
}
data[total++]=num;
}
public void push(int[] arr){
for(int i=0; i push(arr[i]);
}
public int size(){
return total;
}
public boolean isEmpty(){
return total==0;
}
public boolean isFull(){
return false;
}
}
Explanation / Answer
Here is the required code with the methods mergePair() and removeLastMin(). The working of these two methods are well explained using comments, so that you’ll get a clear idea. I have also defined a method display() in NonZeroNumStack class for displaying the stack without removing elements, just to make sure everything works correctly, so that you can verify the working of the above methods yourself. Thanks
// NonZeroNumStack.java
import java.util.*;
public class NonZeroNumStack {
private int[] data;
private int total;
public NonZeroNumStack() {
data = new int[10];
total = 0;
}
public int pop() {
if (isEmpty())
return 0;
else {
return data[--total];
}
}
public int top() {
if (isEmpty())
return 0;
else
return data[total - 1];
}
public void push(int num) {
if (num == 0)
return;
if (data.length == total) {
int[] tmp = new int[total * 2];
for (int i = 0; i < data.length; i++)
tmp[i] = data[i];
data = tmp;
}
data[total++] = num;
}
public void push(int[] arr) {
for (int i = 0; i < arr.length; i++)
push(arr[i]);
}
public int size() {
return total;
}
public boolean isEmpty() {
return total == 0;
}
public boolean isFull() {
return false;
}
/***
* a method created to display the current stack without removing any
* elements
*/
public void display() {
System.out.print("bottom [");
for (int i = 0; i < total; i++) {
System.out.print(data[i]);
if (i != total - 1) {
System.out.print(",");
}
}
System.out.print("] top ");
}
}
// ManipulatingNumStack.java
public class ManipulatingNumStack {
public static void main(String[] args) {
/**
* creating a NonZeroNumStack and adding a few elements
*/
NonZeroNumStack stack = new NonZeroNumStack();
stack.push(7);
stack.push(2);
stack.push(8);
stack.push(9);
stack.push(4);
stack.push(13);
stack.push(7);
stack.push(1);
stack.push(9);
stack.push(10);
/**
* displaying the stack
*/
stack.display();
/**
* defining a ManipulatingNumStack object and demonstrating merging and
* removing last minimum value
*/
ManipulatingNumStack manipulatingNumStack = new ManipulatingNumStack();
manipulatingNumStack.mergePair(stack);
stack.display();
int n = manipulatingNumStack.removeLastMin(stack);
System.out.println("last occurrence of " + n + " is removed");
stack.display();
n = manipulatingNumStack.removeLastMin(stack);
System.out.println("last occurrence of " + n + " is removed");
stack.display();
}
/**
* This method takes a NonZeroNumStack as a parameter and that merges values
* by replacing each successive pair of integers with the sum of the pair
*/
public void mergePair(NonZeroNumStack stack) {
if (stack.isEmpty()) {
// empty stack
return;
}
/**
* creating an array and adding all elements of the stack to the array
* by popping one by one. To maintain the order, elements are added to
* the array in reverse order
*/
int length = stack.size();
int array[] = new int[length];
int i = length - 1;
while (!stack.isEmpty()) {
array[i] = stack.pop();
i--;
}
/**
* now taking each pair of numbers from the array, adding them and
* pushing the sum into the stack
*/
for (i = 0; i < length; i += 2) {
int num = array[i];
if (i + 1 < length) {
num += array[i + 1];
}
stack.push(num);
}
}
/**
* This method accepts a NonZeroNumStack as a parameter and removes and
* returns the last occurrence of the smallest value from the stack.
*/
public int removeLastMin(NonZeroNumStack stack) {
if (stack.isEmpty()) {
// returning zero in case of empty stack
return 0;
}
/**
* creating an array and adding all elements of the stack to the array
* by popping one by one. To maintain the order, elements are added to
* the array in reverse order
*/
int length = stack.size();
int array[] = new int[length];
int i = length - 1;
int minValue = 0;
while (!stack.isEmpty()) {
array[i] = stack.pop();
/**
* while adding elements to the array, the minimum value is also
* calculated
*/
if (i == length - 1) {
/**
* at this point, assuming current element is the smallest one
*/
minValue = array[i];
} else if (array[i] < minValue) {
/**
* the current element is smaller than what we have assumed, so
* making current element as the minimum value
*/
minValue = array[i];
}
i--;
}
/**
* looping through the array in reverse order to find the last index of
* minimum value
*/
for (i = length - 1; i >= 0; i--) {
if (array[i] == minValue) {
/**
* last index if minimum value is found, shifting the remaining
* elements to occupy the vacant space
*/
for (int j = i; j < length - 1; j++) {
array[j] = array[j + 1];
}
length--;
break;
}
}
/**
* pushing the remaining elements into the stack
*/
for (i = 0; i < length; i++) {
stack.push(array[i]);
}
return minValue;
}
}
/*OUTPUT*/
bottom [7,2,8,9,4,13,7,1,9,10] top
bottom [9,17,17,8,19] top
last occurrence of 8 is removed
bottom [9,17,17,19] top
last occurrence of 9 is removed
bottom [17,17,19] top
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.