Specification Design and implement a class Stack that supports stacks that are i
ID: 3770263 • Letter: S
Question
Specification
Design and implement a class Stack that supports stacks that are implemented using a linked-list.
TestLinkList.java which is below can be modified to provide the linked-list functionality. If this code is not used, then you are required to implement your own linked-list code.
The implementation of class Stack is not allowed use arrays, ArrayList, of Vector objects. In other words, it must be implemented using a linked-list.
class Stack must support the following instance methods.
You must define a class StackEmptyException that extends class Exception.
The linked-list does not have any maximum capacity for class Stack objects.
The main() method of your program should contain code to test class Stack objects. This program can use your Menu and MenuItem classes.
TestLinkList.java
Explanation / Answer
package current;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.StreamTokenizer;
public class TestStackLL {
public static void main(String[] args) throws StackEmptyException {
StackLL sl = new StackLL();
sl.push((Object)new String("1"));
sl.push(new String("2"));
sl.print();
System.out.println("Top element: "+sl.top());
sl.pop();
sl.print();
}
}
class StackLL {
private LinkList ll;
public StackLL() {
ll = new LinkList();
}
public void push(Object elem) {
ll.addNodeAtFront((String)elem);
}
// puts an object on top of this stack...
public Object pop() throws StackEmptyException {
String elem = null;
try {
elem = ll.getHeadNode();
ll.deleteNodeFront();
} catch(NullPointerException e) {
throw new StackEmptyException("Stack is empty");
}
return elem;
}
// removes the top object from this stack...
public Object top() throws StackEmptyException {
String elem = null;
try {
elem = ll.getHeadNode();
} catch(NullPointerException e) {
throw new StackEmptyException("Stack is empty");
}
return elem;
}
// returns, but does not remove, the top object from this stack...
public void print() throws StackEmptyException {
try {
ll.printForwards();
} catch(NullPointerException e) {
throw new StackEmptyException("Stack is empty");
}
}
// prints the contents of this stack...
}
class StackEmptyException extends Exception{
public StackEmptyException(){
super();
};
public StackEmptyException(String msg) {
super(msg);
}
}
/*
* An <code>class LLIndex</code> object is used used to keep track of the
* front of the link list, the end of the link list, and the current
* location in the link list.
*/
class LLIndex {
public LLNode head; //points to the front of the list
public LLNode tail; //points to the rear of the list
public LLNode current; //this is the cursor
public LLIndex() {}
}
/*
* <code>class LLNode</code> is used to instantiate objects that are
* elements of as a doubly linked-list. This is not a "generic" node
* (i.e. it only stores references to String objects).
*/
class LLNode {
public String token;
public LLNode next;
public LLNode prev;
public LLNode(String token) { this.token = token; }
}
class LinkList {
private LLIndex list;
public LinkList() { /*do nothing*/ }
public void addNodeAtFront(String token) {
if (list != null)
System.out.println("1. Current Node: "+list.current);
LLNode newNode = new LLNode(token);
if (list == null) {
list = new LLIndex();
list.head = list.tail = newNode;
} else { //add the new node - on the end
newNode.next = list.head;
newNode.prev = null;
//newNode.next = null; //set to null when instantiated
list.head.prev = newNode;
list.head = newNode;
}
System.out.println("2. Current Node: "+list.current);
}
public void addNode(String token) {
LLNode newNode = new LLNode(token);
if (list == null) {
list = new LLIndex();
list.head = list.tail = newNode;
list.current = null;
} else { //add the new node - on the end
list.tail.next = newNode;
newNode.prev = list.tail;
//newNode.next = null; //set to null when instantiated
list.tail = newNode;
}
}
public String getHeadNode() {
return list.head.token;
}
public void deleteNodeFront() {
if(list == null)
return;
list.current = list.head.next;
list.current.prev = null;
list.head = list.current;
}
public void deleteNode() {
System.out.println("4. Current Node: "+list.current);
System.out.println(list.head);
if (list.current == null) return; //empty list
if (list.head == list.tail) { //list of length one
list.head = list.tail = list.current = null;
} else if (list.current == list.tail) {
list.tail = list.current.prev;
list.tail.next = null;
list.current = null;
} else if (list.current == list.head) {
list.head = list.current.next;
list.head.prev = null;
list.current = list.head;
} else {
list.current.prev.next = list.current.next;
list.current.next.prev = list.current.prev;
list.current = list.current.next;
}
}
public void printForwards() {
if (list == null) return; //empty link-list
list.current = list.head;
while (list.current != null) {
System.out.println(list.current.token);
list.current = list.current.next;
}
System.out.println("--- end of print forwards ---");
}
public void printBackwards() {
if (list == null) return; //No List
list.current = list.tail;
while (list.current != null) {
System.out.println(list.current.token);
list.current = list.current.prev;
}
System.out.println("--- end of print backwards ---");
}
public void deleteOddNodes() {
if (list == null) return;
list.current = list.head;
while (list.current != null) {
deleteNode();
if (list.current != null)
list.current = list.current.next; //skip a node
}
}
public void freeList() { list = null; } //rely on gc()
/**
* This method uses <code>class StreamTokenizer</code> to break an
* <code>InputStream</code> into a sequence of "tokens." The tokens
* are "added" to <code>this</code> link-list object.
*/
public void loadTokens(String fname) {
try {
//FileInputStream f = new FileInputStream(fname); //deprecated
BufferedReader f = new BufferedReader(new FileReader(fname));
StreamTokenizer tokens = new StreamTokenizer(f);
tokens.resetSyntax(); //all characters are "ordinary"
tokens.wordChars('a', 'z');
tokens.wordChars('A', 'Z');
tokens.wordChars('0', '9');
tokens.wordChars(160, Character.MAX_VALUE);
tokens.wordChars(''', ''');
tokens.whitespaceChars(0, ' ');
int type;
while ((type = tokens.nextToken()) != StreamTokenizer.TT_EOF) {
if (type != StreamTokenizer.TT_WORD) continue;
addNode(tokens.sval); //sval is public
}
}
catch (FileNotFoundException foo) { /* thrown by FileReader(...) */ }
catch (IOException junk) { /* thrown by nextToken() */ }
}
}
-----------output-------------
2. Current Node: null
1. Current Node: null
2. Current Node: null
2
1
--- end of print forwards ---
Top element: 2
1
--- end of print forwards ---
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.