Java * implement a non-member method for the stack adt called

 

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;
}

}

Calculate the price of your order

550 words
We'll send you the first draft for approval by September 11, 2018 at 10:52 AM
Total price:
$26
The price is based on these factors:
Academic level
Number of pages
Urgency
Basic features
  • Free title page and bibliography
  • Unlimited revisions
  • Plagiarism-free guarantee
  • Money-back guarantee
  • 24/7 support
On-demand options
  • Writer’s samples
  • Part-by-part delivery
  • Overnight delivery
  • Copies of used sources
  • Expert Proofreading
Paper format
  • 275 words per page
  • 12 pt Arial/Times New Roman
  • Double line spacing
  • Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Our guarantees

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.

Money-back guarantee

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 more

Zero-plagiarism guarantee

Each 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 more

Free-revision policy

Thanks 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 more

Privacy policy

Your 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 more

Fair-cooperation guarantee

By 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