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 {
public void push(E newEntry);
public E pop();
public E top();
public boolean isEmpty();
public int size();
public void clear();
}
public static class SinglyLinkedStack implements Stack {
private static class Node {
private E element;
private Node next;
public Node(E elm, Node 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 getNext() {
return next;
}
public void setElement(E elm) {
this.element = elm;
}
public void setNext(Node next) {
this.next = next;
}
public void clear() { // no need to return data
element = null;
next = null;
}
}
// instance variables for the stack object
private Node 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 nNode = new Node<>(newEntry, header.getNext());
header.setNext(nNode);
currentSize++;
}
@Override
public E pop() {
E etr = top();
Node 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;
}
}
