Design and implement a class Stack that supports stacks that are implemented usi
ID: 3773314 • Letter: D
Question
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 Vectorobjects. 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 Stackobjects. This program can use your Menu and MenuItem classes.
TestLinkList.java
Explanation / Answer
Answer:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.StreamTokenizer;
import java.util.Scanner;
/*
* 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<Object>
{
public LLNode<Object> head; // point T the front of the list
public LLNode<Object> tail; // points to the rear of the list
public LLNode<Object> 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<Object>
{
public Object token;
public LLNode<Object> next;
public LLNode<Object> prev;
public LLNode(Object token)
{
this.token = token;
}
}
class LinkList<Object>
{
private LLIndex<Object> list;
public LinkList()
{ /* do nothing */
}
public void addNode(Object token)
{
LLNode<Object> newNode = new LLNode<Object>(token);
if (list == null)
{
list = new LLIndex<Object>();
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 LLNode<Object> deleteNode()
{
LLNode<Object> temp = null;
if (list.head == list.tail)
{
temp = list.head;
System.out.println("head tail: " + temp.token);
list.head = list.tail = list.current = null;
return temp;
}
else if (list.current == list.tail)
{
temp = list.tail;
list.tail = list.current.prev.next;
list.tail.next = null;
list.current = null;
return temp;
}
else
{
temp = list.tail;
list.tail.prev = list.tail.prev.prev;
list.tail.prev.next = list.tail;
list.current = list.tail.prev.next;
list.current.next = list.tail.prev;
list.tail.next = null;
return temp;
}
}
public LLNode<Object> getTail()
{
return list.tail;
}
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((Object) tokens.sval); // sval is public
}
}
catch (FileNotFoundException foo)
{ /* thrown by FileReader(...) */
}
catch (IOException junk)
{ /* thrown by nextToken() */
}
}
}
class StackEmptyException extends Exception
{
StackEmptyException()
{
}
void show()
{
System.out.println("Stack is empty!");
}
}
class StackLinkedList<Object> extends LinkList<Object>
{
LinkList<Object> ll;
public StackLinkedList()
{
ll = new LinkList<Object>();
}
public void push(Object elem)
{
ll.addNode(elem);
}
// puts an object on top of this stack...
public Object pop() throws StackEmptyException
{
if (ll.deleteNode() == null)
{
throw new StackEmptyException();
}
else
return ll.deleteNode().token;
}
// removes the top object from this stack...
public Object top() throws StackEmptyException
{
if (ll.getTail() == null)
{
throw new StackEmptyException();
}
return ll.getTail().token;
}
// returns, but does not remove, the top object from this stack...
public void print() throws StackEmptyException
{
if (ll == null)
{
System.out.println("No objects in the stack");
throw new StackEmptyException();
}
else
ll.printForwards();
}
}
public class TestLinkList
{
public static void main(String[] argv) throws Exception
{
Scanner in = new Scanner(System.in);
String value;
StackLinkedList<String> sll = new StackLinkedList<String>();
sll.ll.loadTokens(argv[0]);
int choice = 0;
do
{
System.out.println("Menu");
System.out.println("1) Push");
System.out.println("2) Pop");
System.out.println("3) Top");
System.out.println("4) Print");
System.out.println("5) Exit");
System.out.print("Enter your choice: ");
choice = in.nextInt();
switch (choice)
{
case 1:
System.out.println("Enter value: ");
value = in.next();
sll.push(value);
break;
case 2:
System.out.println("Poped element: " + sll.pop());
break;
case 3:
System.out.println("Poped element: " + sll.top());
break;
case 4:
sll.print();
break;
case 5:
System.exit(1);
break;
}
} while (true);
}
/*
* isFileUsable() provides an example of using the File class found in the
* java.io package.
*/
private static boolean isFileUsable(String s)
{
File f = new File(s);
if (!f.exists())
{
System.err.println("file " + s + " not found");
return false;
}
if (!f.isFile())
{
System.err.println("file " + s + " is not a file");
return false;
}
if (!f.canRead())
{
System.err.println("file " + s + " cannot be read");
return false;
}
if (f.length() <= 0)
{
System.err.println("file " + s + " is empty read");
return false;
}
return true;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.