home study engineering computer science questions and an

home / study / engineering / computer science / questions and answers / - you need to implement simplelinkedstack.java ...

Question: - You need to implement SimpleLinkedSta...

Bookmark

/**
An interface for the ADT stack.
Do not modify this file
*/

package PJ2;

public interface StackInterface<T>
{

/** Gets the current number of data in this stack.
@return the integer number of entries currently in the stack*/
public int size();

/** Adds a new data to the top of this stack.
@param aData an object to be added to the stack */
public void push(T aData);
  
/** Removes and returns this stack\'s top data.
@return either the object at the top of the stack or,
if the stack is empty before the operation, null */
public T pop();
  
/** Retrieves this stack\'s top data.
@return either the data at the top of the stack or
null if the stack is empty */
public T peek();
  
/** Detects whether this stack is empty.
@return true if the stack is empty */
public boolean empty();
  
/** Removes all data from this stack */
public void clear();
} // end StackInterface

/**
A class of stacks whose entries are stored in a chain of nodes.
Implement all methods in SimpleLinkedStack class using
the inner Node class.

Main Reference : text book or class notes
Do not change or add data fields
Do not add new methods
You may access Node object fields directly, i.e. data and next
*/

package PJ2;

public class SimpleLinkedStack<T> implements StackInterface<T>
{

// Data fields
private Node topNode; // references the first node in the chain
private int count;     // number of data in this stack
  
public SimpleLinkedStack()
{
// add stataments
} // end default constructor
  
public void push(T newData)
{
// add stataments
} // end push

public T peek()
{
// add stataments
return null;
} // end peek

public T pop()
{
// add stataments
return null;
} // end pop

public boolean empty()
{
// add stataments
return false;
} // end empty

public int size()
{
// add stataments
return -1;
} // end isEmpty

public void clear()
{
// add stataments
} // end clear

public String toString()
{
// add stataments
// note: data class in stack must implement toString() method
// return a list of data in Stack, separate them with \',\'
return \"\";
}

/****************************************************
   private inner node class
Do not modify this class!!
you may access data and next directly
***************************************************/

   private class Node
   {
   private T data; // entry in list
   private Node next; // link to next node
   private Node (T dataPortion)
   {
   data = dataPortion;
   next = null; // set next to NULL
   } // end constructor

   private Node (T dataPortion, Node nextNode)
   {
   data = dataPortion;
   next = nextNode; // set next to refer to nextNode
   } // end constructor
   } // end Node

/****************************************************
Do not modify: Stack test
****************************************************/
public static void main (String args[])
{

System.out.println(\"\ \"+
   \"*******************************************************\ \"+
\"Sample Expected output:\ \"+
   \"\ \"+
\"OK: stack is empty\ \"+
\"Push 3 data: 10, 30, 50\ \"+
\"Print stack [50,30,10,]\ \"+
\"OK: stack size is 3\ \"+
\"OK: peek stack top is 50\ \"+
\"OK: stack is not empty\ \"+
\"Pop 2 data: 50, 30\ \"+
\"Print stack [30,10,]\ \"+
\"Print stack [10,]\ \"+
\"OK: stack pop data is 30\ \"+
\"Clear stack\ \"+
\"Print stack []\ \"+
   \"\ \"+
   \"*******************************************************\");

System.out.println(\"\ Your Test output:\ \");
   StackInterface<Integer> s = new SimpleLinkedStack<Integer>();
   if (s.empty())
System.out.println(\"OK: stack is empty\");
   else
System.out.println(\"Error: stack is not empty\");

   s.push(10);
   s.push(30);
   s.push(50);
System.out.println(\"Push 3 data: 10, 30, 50\");
System.out.println(\"Print stack \" + s);

   if (s.size() == 3)
System.out.println(\"OK: stack size is 3\");
   else
System.out.println(\"Error: stack size is \" + s.size());

   if (s.peek() == 50)
System.out.println(\"OK: peek stack top is 50\");
   else
System.out.println(\"Error: peek stack top is \" + s.size());

   if (!s.empty())
System.out.println(\"OK: stack is not empty\");
   else
System.out.println(\"Error: stack is empty\");

System.out.println(\"Pop 2 data: 50, 30\");
s.pop();
System.out.println(\"Print stack \" + s);
   int data=s.pop();
System.out.println(\"Print stack \" + s);
   if (data == 30)
System.out.println(\"OK: stack pop data is 30\");
   else
System.out.println(\"Error: stack pop data is \" + data);

System.out.println(\"Clear stack\");
s.clear();
System.out.println(\"Print stack \" + s);
}

} // end Stack

Solution

/**
An interface for the ADT stack.
Do not modify this file
*/
package PJ2;

public interface StackInterface<T> {
   /**
   * Gets the current number of data in this stack.
   *
   * @return the integer number of entries currently in the stack
   */
   public int size();

   /**
   * Adds a new data to the top of this stack.
   *
   * @param aData
   * an object to be added to the stack
   */
   public void push(T aData);

   /**
   * Removes and returns this stack\'s top data.
   *
   * @return either the object at the top of the stack or, if the stack is
   * empty before the operation, null
   */
   public T pop();

   /**
   * Retrieves this stack\'s top data.
   *
   * @return either the data at the top of the stack or null if the stack is
   * empty
   */
   public T peek();

   /**
   * Detects whether this stack is empty.
   *
   * @return true if the stack is empty
   */
   public boolean empty();

   /** Removes all data from this stack */
   public void clear();
} // end StackInterface

/**
A class of stacks whose entries are stored in a chain of nodes.
Implement all methods in SimpleLinkedStack class using
the inner Node class.
Main Reference : text book or class notes
Do not change or add data fields
Do not add new methods
You may access Node object fields directly, i.e. data and next
*/
package PJ2;

import java.util.NoSuchElementException;

public class SimpleLinkedStack<T> implements StackInterface<T> {

   // Data fields
   private Node topNode; // references the first node in the chain
   private int count; // number of data in this stack

   public SimpleLinkedStack() {
       // add stataments
       topNode = null;
       count = 0;
   } // end default constructor

   public void push(T newData) {
       // add stataments
       Node oldTop = topNode;
       topNode = new Node(newData);
       // topNode.data=newData;
       topNode.next = oldTop;
       count++;

   } // end push

   public boolean isEmpty() {
       return topNode == null;
   }

   public T peek() {
       if (isEmpty())
           throw new NoSuchElementException(\"Stack underflow\");
       return topNode.data;
   } // end peek

   public T pop() {
       // add stataments

       // add stataments
       if (isEmpty())
           throw new NoSuchElementException(\"Stack underflow\");
       T item = topNode.data; // save item to return
       topNode = topNode.next; // delete first node
       count--;
       return item;
   } // end pop

   public boolean empty() {
       // add stataments
       return false;
   } // end empty

   public int size() {
       // add stataments
       return count;
   } // end isEmpty

   public void clear() {
       // add stataments
       topNode = null;
       count = 0;
   } // end clear

   public String toString() {
       // add stataments
       // note: data class in stack must implement toString() method
       // return a list of data in Stack, separate them with \',\'
       StringBuilder builder = new StringBuilder();
       Node current = topNode;
       while (current != null) {
           builder.append(current.data).append(\",\");
           current = current.next;
       }
       return builder.toString();

   }

   /****************************************************
   * private inner node class Do not modify this class!! you may access data
   * and next directly
   ***************************************************/
   private class Node {
       private T data; // entry in list
       private Node next; // link to next node

       private Node(T dataPortion) {
           data = dataPortion;
           next = null; // set next to NULL
       } // end constructor

       private Node(T dataPortion, Node nextNode) {
           data = dataPortion;
           next = nextNode; // set next to refer to nextNode
       } // end constructor
   } // end Node

   /****************************************************
   * Do not modify: Stack test
   ****************************************************/
   public static void main(String args[]) {
       System.out.println(\"\ \"
               + \"*******************************************************\ \"
               + \"Sample Expected output:\ \" + \"\ \" + \"OK: stack is empty\ \"
               + \"Push 3 data: 10, 30, 50\ \" + \"Print stack [50,30,10,]\ \"
               + \"OK: stack size is 3\ \" + \"OK: peek stack top is 50\ \"
               + \"OK: stack is not empty\ \" + \"Pop 2 data: 50, 30\ \"
               + \"Print stack [30,10,]\ \" + \"Print stack [10,]\ \"
               + \"OK: stack pop data is 30\ \" + \"Clear stack\ \"
               + \"Print stack []\ \" + \"\ \"
               + \"*******************************************************\");
       System.out.println(\"\ Your Test output:\ \");
       StackInterface<Integer> s = new SimpleLinkedStack<Integer>();
       if (s.empty())
           System.out.println(\"OK: stack is empty\");
       else
           System.out.println(\"Error: stack is not empty\");
       s.push(10);
       s.push(30);
       s.push(50);
       System.out.println(\"Push 3 data: 10, 30, 50\");
       System.out.println(\"Print stack \" + s);
       if (s.size() == 3)
           System.out.println(\"OK: stack size is 3\");
       else
           System.out.println(\"Error: stack size is \" + s.size());
       if (s.peek() == 50)
           System.out.println(\"OK: peek stack top is 50\");
       else
           System.out.println(\"Error: peek stack top is \" + s.size());
       if (!s.empty())
           System.out.println(\"OK: stack is not empty\");
       else
           System.out.println(\"Error: stack is empty\");
       System.out.println(\"Pop 2 data: 50, 30\");
       s.pop();
       System.out.println(\"Print stack \" + s);
       int data = s.pop();
       System.out.println(\"Print stack \" + s);
       if (data == 30)
           System.out.println(\"OK: stack pop data is 30\");
       else
           System.out.println(\"Error: stack pop data is \" + data);
       System.out.println(\"Clear stack\");
       s.clear();
       System.out.println(\"Print stack \" + s);
   }
} // end Stack

OUTPUT:

*******************************************************
Sample Expected output:

OK: stack is empty
Push 3 data: 10, 30, 50
Print stack [50,30,10,]
OK: stack size is 3
OK: peek stack top is 50
OK: stack is not empty
Pop 2 data: 50, 30
Print stack [30,10,]
Print stack [10,]
OK: stack pop data is 30
Clear stack
Print stack []

*******************************************************

Your Test output:

Error: stack is not empty
Push 3 data: 10, 30, 50
Print stack 50,30,10,
OK: stack size is 3
OK: peek stack top is 50
OK: stack is not empty
Pop 2 data: 50, 30
Print stack 30,10,
Print stack 10,
OK: stack pop data is 30
Clear stack
Print stack