import java.util.EmptyStackException;
import java.util.Iterator;
public class Lab07P2Wrapper {
private static boolean equals(int[] arr1, int[] arr2) {
if(arr1.length != arr2.length) return false;
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int[] example = {-1, 1, 3, 9, 11, 11, 11, 15};
int[] input = {9, 11, 15, 11, 1, -1, 3, 11};
int[] result = stackSort(input);
if(equals(example, result)) {
System.out.println(“Test Passed!”);
} else {
System.out.print(“Test Failed, expected: “);
for(int i = 0; i < example.length; i++) {
if(i == 0) System.out.print(“{” + example[i] + “, “);
else if(i == example.length – 1) System.out.print(example[i] + “}”);
else System.out.print(example[i] + “, “);
}
for(int i = 0; i < result.length; i++) {
if(i == 0) System.out.print(“, got {” + result[i] + “, “);
else if(i == result.length – 1) System.out.print(result[i] + “}”);
else System.out.print(result[i] + “, “);
}
}
}
public static interface Stack<E> {
public void push(E newEntry);
public E pop();
public E top();
public boolean isEmpty();
public int size();
public void clear();
}
public static class SinglyLinkedStack<E> implements Stack<E> {
private static class Node<E> {
private E element;
private Node<E> next;
public Node(E elm, Node<E> next) {
this.element = elm;
this.next = next;
}
public Node(E data) {
this(data, null);
}
public Node() {
this(null, null);
}
public E getElement() {
return element;
}
public Node<E> getNext() {
return next;
}
public void setElement(E elm) {
this.element = elm;
}
public void setNext(Node<E> next) {
this.next = next;
}
public void clear() { // no need to return data
element = null;
next = null;
}
}
// instance variables for the stack object
private Node<E> header; //Note that this is NOT a dummy header
private int currentSize;
public SinglyLinkedStack() {
header = new Node<>();
currentSize = 0;
}
@Override
public void push(E newEntry) {
Node<E> nNode = new Node<>(newEntry, header.getNext());
header.setNext(nNode);
currentSize++;
}
@Override
public E pop() {
E etr = top();
Node<E> ntr = header.getNext();
header.setNext(ntr.getNext());
currentSize–;
ntr.clear();
ntr = null;
return etr;
}
@Override
public E top() {
if (isEmpty())
throw new EmptyStackException();
return header.getNext().getElement();
}
@Override
public boolean isEmpty() {
return size() == 0;
}
@Override
public int size() {
return currentSize;
}
@Override
public void clear() {
while (size() > 0) pop();
}
}
/**
* Implement a non-member method for the Stack ADT called stackSort.
* The function takes as a parameter an array of integers and returns the array sorted in increasing order.
*
* For example consider we have an array A = {9, 11, 15, 11, 1, -1, 3, 11}
* In order to sort values, we will use two stacks which will be called the left and right stacks.
* The values in the stacks will be sorted (in non-descending order) and the values in the left stack
* will all be less than or equal to the values in the right stack.
*
* The following example illustrates a possible state for our two stacks:
*
* left right
* [ ] [ ]
* [ ] [ 9]
* [ 3] [11]
* [ 1] [11]
* [-1] [15]
*
* Notice that the values in the left stack are sorted so that the smallest value is at the bottom of the stack.
* The values in the right stack are sorted so that the smallest value is at the top of the stack.
* If we read the values up the left stack and then down the right stack, we get:
* A = {-1, 1, 3, 9, 11, 11, 11, 15}
* which is in sorted order.
*
*
* Consider the following cases, using the example shown above as a point of reference, to help you design your algorithm:
* 1) If we were to insert the value 5, it could be added on top of either stack and the collection would remain sorted.
* What other values, besides 5, could be inserted in the example without having to move any values?
*
* 2) If we were to insert the value 0, some values must be moved from the left stack to the right stack before we could actually insert 0.
* How many values must actually be moved?
*
* 3) If we were to insert the value 11, first some values must be moved from the right stack to the left stack.
* How many values must actually be moved?
* What condition should we use to determine if enough values have been moved in either of the previous two cases?
*
* YOU MUST USE TWO STACKS, IMPLEMENTATIONS THAT USE Arrays.sort();
* OR ANY SORTING ALGORITHM (BubbleSort, SelectionSort, etc.) WILL NOT BE GIVEN CREDIT
*
* @param array
* @return Sorted array using two stacks
*/
public static int[] stackSort(int[] array) {
/*ADD YOUR CODE HERE*/
return null;
}
}
Delivering a high-quality product at a reasonable price is not enough anymore.
That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.
You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.
Read moreEach paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.
Read moreThanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.
Read moreYour email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.
Read moreBy sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.
Read more