Created
December 2, 2012 01:17
-
-
Save codelance/4186347 to your computer and use it in GitHub Desktop.
Java Stack Based Linked List
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class DataNode { | |
/*DataNode Constructor | |
Description: Called when an object is instantiated | |
Parameters: | |
Object Elem : object stored as data in this class | |
Pre: None | |
Post: Initialized element | |
Returns: None | |
Called by: Application | |
Calls: itself | |
*/ | |
public DataNode( Object elem) | |
{ | |
this(elem, null); | |
} | |
/*DataNode Constructor | |
Description: Called when an object is instantiated | |
Parameters: | |
Object Elem : object stored as data in this class | |
DataNode nextNode: a pointer to the next object | |
Pre: None | |
Post: Initialized element | |
Returns: None | |
Called by: Application | |
Calls: itself | |
*/ | |
public DataNode(Object elem, DataNode nextNode) | |
{ | |
this.data = elem; | |
this.next = nextNode; | |
} | |
/*getData | |
Description: Gets the data stored in this object | |
Parameters: None | |
Pre: None | |
Post: None | |
Returns: Data element stored in object | |
Called by: Outside application | |
Calls: None | |
*/ | |
public Object getData() { | |
return data; | |
} | |
/*setData | |
Description: Sets the data to be stored in the object | |
Parameters: | |
Object data: data to be stored | |
Pre: Initialized object | |
Post: Data passed in is stored in the class object | |
Returns: None | |
Called by: Outside Application | |
Calls: None | |
*/ | |
public void setData(Object data) { | |
this.data = data; | |
} | |
/*getNext | |
Description: Returns the "pointer" reference to the next object | |
Parameters: None | |
Pre: None | |
Post: None | |
Returns: DataNode object that is stored/pointed to | |
Called by: Outside Application | |
Calls: None | |
*/ | |
public DataNode getNext() { | |
return next; | |
} | |
/*setNext | |
Description: sets the DataNode object to be pointer to | |
Parameters: | |
DataNode next: object that the current node points to | |
Pre: Initialized object | |
Post: Pointer to next DataNode is stored | |
Returns: None | |
Called by: outside Application | |
Calls: None | |
*/ | |
public void setNext(DataNode next) { | |
this.next = next; | |
} | |
public Object data; // data stored | |
public DataNode next;// pointer to next DataNode element | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.PrintStream; | |
public class LinkedStack implements Stack{ | |
private DataNode TopPtr; | |
/* public static void main(String[] args) { | |
LinkedStack s = new LinkedStack(); | |
//Random generator = new Random(); | |
System.out.println("Stack is empty: "+ s.isEmpty()); | |
//Push Data onto Stack | |
for(int i = 0; i< 32215; i++) | |
{ | |
s.push(i*3); | |
//s.displayStack(System.out); | |
} | |
System.out.println("------------------------"); | |
System.out.print("(Size: "+s.size() +") "); //s.displayStack(System.out); | |
System.out.println("------------------------"); | |
//Pop Data off Stack | |
for(int i = 0; i< 32215; i++) | |
{ | |
s.pop(); | |
//s.displayStack(System.out); | |
} | |
System.out.println("Stack is empty: "+ s.isEmpty()); | |
}*/ | |
/*LinkedStack Class Constructor | |
Description: Initializes the scope of the object and the TopPtr | |
Parameters: None | |
Pre: None | |
Post: TopPtr is initialized to null | |
Returns: None | |
Called by: Outside Application | |
Calls: None | |
*/ | |
public LinkedStack() | |
{ | |
TopPtr = null; | |
} | |
/*isEmpty | |
Description: Return true or false if the stack is empty | |
Parameters: None | |
Pre: None | |
Post: None | |
Returns: True or False if stack is empty | |
Called by: Outside Application | |
Calls: None | |
*/ | |
public boolean isEmpty() { | |
//if TopPtr is equal to null then true is returned | |
return (TopPtr == null) ? true : false; | |
} | |
/*peek | |
Description: gets the top element of the stack | |
Parameters: None | |
Pre: Initialized Stack | |
Post: None | |
Returns: the Data of the Top element | |
Called by: Outside Application | |
Calls: DataNode.getData() | |
*/ | |
public Object peek() { | |
if(TopPtr == null) | |
return "NULL"; | |
else | |
return TopPtr.getData(); | |
} | |
/*pop | |
Description: Removes the Top element from the stack | |
Parameters: None | |
Pre: Stack has to be non empty | |
Post: Possible top element is removed from the stack and | |
TopPtr points to the next element | |
Returns: The object that has been removed | |
Called by: Outside Application | |
Calls: DataNode.getNext, DataNode.getData, isEmpty() | |
*/ | |
public Object pop() { | |
if( isEmpty() ) | |
{ | |
return null; | |
} | |
//this case checks if there is only one node in the stack | |
//if so then we just set the topptr to null | |
else if( TopPtr.getNext() == null) | |
{ | |
Object data = TopPtr.getData(); | |
TopPtr = null; | |
return data; | |
} | |
//this case auto handles removed the top pointer and | |
//points to the next element in the stack | |
else | |
{ | |
DataNode poppednode = TopPtr; | |
TopPtr = poppednode.getNext(); | |
return poppednode.getData(); | |
} | |
} | |
/*push | |
Description: Puts an element into the stack | |
Parameters: | |
Object element: element to be stored in the list | |
Pre: Initialized Stack Structure | |
Post: Element is stored in the stack | |
Returns: None | |
Called by: Outside Application | |
Calls: isEmpty(), DataNode(), DataNode.setNext(); | |
*/ | |
public void push(Object element) { | |
if( isEmpty() ) | |
{ | |
//instantiate the TopPtr if nothing in list | |
TopPtr = new DataNode(element); | |
} | |
else | |
{ | |
DataNode newnode = new DataNode(element); | |
newnode.setNext(TopPtr); | |
TopPtr = newnode; | |
} | |
} | |
/*size | |
Description: Return the size of the list | |
Parameters: None | |
Pre: None | |
Post: None | |
Returns: number representing the size of the list | |
Called by: Outside Application | |
Calls: DataNode.getNext() | |
*/ | |
public int size() { | |
int count = 0; | |
DataNode cur = TopPtr; | |
//iterate through the list | |
while( cur != null ) | |
{ | |
cur = cur.getNext(); | |
count++; | |
} | |
return count; | |
} | |
/*getNext | |
Description: | |
Parameters: displayStack (for debugging purposes) | |
Pre: Initialized Stack with elements | |
Post: Printed contents of the list | |
Returns: None | |
Called by: Outside Application | |
Calls: DataNode.getData(), DataNode.getNext(); | |
*/ | |
public void displayStack(PrintStream out) | |
{ | |
DataNode cur = TopPtr; | |
while( cur != null ) | |
{ | |
out.print(cur.getData() + " "); | |
cur = cur.getNext(); | |
} | |
out.println(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public interface Stack { | |
public int size(); | |
public boolean isEmpty(); | |
public Object peek(); | |
public void push (Object element); | |
public Object pop(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment