push(int v) This method adds an integer to the top of the stack. pop() This method removes an element from the top of the stack and returns the element. It throws a RuntimeException "pop attempted on an empty stack" if this operation is attempted on an empty stack. size() This method returns the number of elements on the stack. Note that you are only supposed to touch the above three methods. You are NOT allowed to create any other methods, instance variables, or make any changes to methods other than these three methods or files other than "LinkedNumberStack.java". Points will be taken off if you fail to follow this rule. b. Code Testing You are provided with a test driver implemented by "TestStack.java" (Do not make any changes to this file!) so there is no need to write your own.

4 public class LinkedNumberStack implements NumberStack 5 { 7 private LNode m_top; 8 10 public boolean isEmpty() 11 { 12 if (m_top == null) 13 return true; 14 else 15 return false; 16 } 17 19 public boolean isFull() 20 { 21 return false; 22 } 23 25 public int top() 26 { 27 if (isEmpty()) 28 throw new RuntimeException("top attempted on an empty stack"); 29 else 30 return m_top.getInfo(); 31 } 32 33 // push a value onto the stack 34 public void push(int v) 35 { 36 // TODO: implement this method 37 38 } 39 40 // remove and return the value at the top of the stack 41 public int pop() 42 { 43 // TODO: implement this method 44 45 return -1; // replace this statement with your own return 46 47 } 48 49 // return the number of elements on the stack 50 public int size() 51 { 52 // TODO: implement this method 53 54 return -1; // replace this statement with your own return 55 } 56 58 @Override 59 public String toString() 60 { 61 String stackContent = ""; 62 LNode current = m_top; 64 while (current != null) 65 { 66 stackContent += current.getInfo() + " "; 67 current = current.getLink(); 68 } 69 70 return stackContent; 71 } 72 }

5 public interface NumberStack 6 { 7 boolean isEmpty(); // check whether the stack is empty 8 boolean isFull(); // check whether the stack is full 9 int top(); // return the element at the top of the stack 10 int pop(); // remove and return the element at the top of the stack 11 void push(int v); // push a value onto the stack 12 int size(); // return the number of elements on the stack 13 @Override 14 String toString(); // return a string representation of the stack 15 }

5 public class LNode 6 { 8 private int m_info; 9 private LNode m_link; 10 12 public LNode(int info) 13 { 14 m_info = info; 15 m_link = null; 16 } 17 19 public void setLink(LNode link) 20 { 21 m_link = link; 22 } 23 24 public LNode getLink() 25 { 26 return m_link; 27 } 28 29 public int getInfo() 30 { 31 return m_info; 32 } 33 }

5 import java.util.*; 6 import java.io.*; 7 8 public class TestStack 9 { 10 public static void main(String[] args) 11 { 12 System.out.println("================ Problem 1 ================"); 13 TestP1(); 14 System.out.println("================ End of Problem 1 ================ "); 15 16 System.out.print("Press any key to test Problem 2..."); 17 try 18 { 19 System.in.read(); 20 } 21 catch (Exception e) 22 { 23 e.printStackTrace(); 24 } 25 26 System.out.println("================ Problem 2 ================"); 27 TestP2(); 28 System.out.println("================ End of Problem 2 ================"); 29 } 30 31 public static void TestP1() 32 { 33 NumberStack myStack = new LinkedNumberStack(); 34 int numPassedTests = 0; 35 int numTotalTests = 0; 36 String testResult; 37 539 // Test 21 540 numTotalTests++; 541 sReturn = ""; 542 testResult = "[Failed]"; 543 eMsg = "N/A"; 544 try 545 { 546 myStack.push(70); 547 sReturn = myStack.toString(); 548 549 if (sReturn.equals("70 ")) 550 { 551 numPassedTests++; 552 testResult = "[Passed]"; 553 } 554 } 555 catch (RuntimeException e) 556 { 557 eMsg = "RuntimeException - \"" + e.getMessage() + "\""; 558 } 559 560 System.out.println("Test " + numTotalTests + ": push(70) and then toString() ==> " + testResult + " Expected (from top to bottom): 70 "); 561 if (eMsg.equals("N/A")) 562 System.out.println(" Yours (from top to bottom): " + sReturn + " "); 563 else 564 System.out.println(" Yours: " + eMsg + " "); 565 566 // Test 22 567 numTotalTests++; 568 iReturn = -1; 569 testResult = "[Failed]"; 570 eMsg = "N/A"; 571 try 572 { 573 iReturn = myStack.top(); 574 575 if (iReturn == 70) 576 { 577 numPassedTests++; 578 testResult = "[Passed]"; 579 } 580 } 581 catch (RuntimeException e) 582 { 583 eMsg = "RuntimeException - \"" + e.getMessage() + "\""; 584 } 585 586 System.out.println("Test " + numTotalTests + ": top() ==> " + testResult + " Expected: 70"); 587 if (eMsg.equals("N/A")) 588 System.out.println(" Yours: " + iReturn + " "); 589 else 590 System.out.println(" Yours: " + eMsg + " "); 591 592 // Test 23 593 numTotalTests++; 594 iReturn = -1; 595 testResult = "[Failed]"; 596 eMsg = "N/A"; 597 try 598 { 599 iReturn = myStack.pop(); 600 iReturn = myStack.size(); 601 602 if (iReturn == 0) 603 { 604 numPassedTests++; 605 testResult = "[Passed]"; 606 } 607 } 608 catch (RuntimeException e) 609 { 610 eMsg = "RuntimeException - \"" + e.getMessage() + "\""; 611 } 612 613 System.out.println("Test " + numTotalTests + ": pop() and then size() ==> " + testResult + " Expected: 0"); 614 if (eMsg.equals("N/A")) 615 System.out.println(" Yours: " + iReturn + " "); 616 else 617 System.out.println(" Yours: " + eMsg + " "); 618 619 System.out.println("Total test cases: " + numTotalTests + " Correct: " + numPassedTests + " Wrong: " + (numTotalTests - numPassedTests)); 620 }