Can you modify the program to use an ArrayQueue and LinkedQueue instead of the A
ID: 3853198 • Letter: C
Question
Can you modify the program to use an ArrayQueue and LinkedQueue instead of the ArrayStack and LinkedStack
___________________________________________________________________________________
/**
Main driver that tests the InfixExpression class's methods function. Also tests that the
ArrayStack and LinkedStack are working correctly for the InfixExpression class.
@author Jae Kim
@version 1.0
@date 5/11/2017
@system windows/eclipse
*/
import java.io.*;
import java.util.Scanner;
public class Main {
/**
* calls the openInputFile method and testHW method to see if those methods
* are working correctly. It will keep reading until the line in the file is
* blank.
*
* @param args
*/
public static void main(String[] args) {
Scanner Scanning = openInputFile(); // the return of Scanned file of the
// openInputFile
while (Scanning.hasNextLine()) {
String lineRead = Scanning.nextLine(); //The next line of the file read.
InfixExpression inputLineCalculation = new InfixExpression();
inputLineCalculation.setWholeExpr(lineRead);
System.out.println(inputLineCalculation.toString());
}
testHW1();
}
public static Scanner userScanner = new Scanner(System.in);
/**
* Declares a new instance of the InfixExpression to test the null parameter
* and a string parameter to see if the InfixExpression class works
* correctly. It also tests if the ArrayStack and the LinkedStack classes
* are working correctly.
*/
public static void testHW1() { // testing InfixExpression more:
InfixExpression infix1, infix2;
infix1 = new InfixExpression(null);
infix2 = new InfixExpression("( 234.5 * ( 5.6 + 7.0 ) ) / 100.2");
System.out.println(" Testing InfixExpression:");
System.out.println("When passing null, the String and double = " + infix1.toString());
System.out.println("When passing a valid String, the String and double = " + infix2.toString());
// testing ArrayStack and LinkedStack more:
ArrayStack<String> arrStack = new ArrayStack<>();
LinkedStack<String> linkStack = new LinkedStack<>();
String[] strArray = { "First", "Second", "Third", "Fourth", "Fifth", "Sixth", "Seventh", "Eighth", "Ninth",
"Tenth" };
// Testing ArrayStack
System.out.println(" Testing the ArrayStack:");
for (int i = 0; i < strArray.length; ++i) {
if (!arrStack.push(strArray[i] + " 1"))
System.out.println("Error: couldn't push " + strArray[i] + " 1");
}
for (int i = 0; i < strArray.length; ++i) {
if (!arrStack.push(strArray[i] + " 2")) {
System.out.println("Out of space, removing " + arrStack.pop());
if (!arrStack.push(strArray[i] + " 2"))
System.out.println("Error pushing!" + strArray[i] + " 2");
}
}
System.out.println("The size of the ArrayStack is now " + arrStack.size());
while (!arrStack.isEmpty()) {
System.out.println("Popping " + arrStack.pop());
}
System.out.println("The size of the ArrayStack is now " + arrStack.size());
if (!arrStack.push(strArray[0] + " 3"))
System.out.println("Error: couldn't push " + strArray[0] + " 3");
else
System.out.println(
"After pushing " + arrStack.peek() + ", the size of the ArrayStack is now " + arrStack.size());
// testing LinkedStack
System.out.println(" Testing the LinkedStack:");
for (int i = 0; i < strArray.length; ++i)
linkStack.push(strArray[i] + " 4");
System.out.println("The size of the LinkedStack is " + linkStack.size());
for (int i = 0; i < strArray.length / 2; ++i) {
System.out.println("Popping " + linkStack.pop());
}
System.out.println("The size of the LinkedStack is now " + linkStack.size());
while (!linkStack.isEmpty()) {
System.out.println("Popping " + linkStack.pop());
}
System.out.println("The size of the LinkedStack is now " + linkStack.size());
if (!linkStack.push(strArray[0] + " 5"))
System.out.println("Error: couldn't push " + strArray[0] + " 5");
else
System.out.println(
"After pushing " + linkStack.peek() + ", the size of the LinkedStack is now " + linkStack.size());
} // end stackTester
/**
* This method reads the file that is typed in from the console so that the
* file is read.
*
* @return Scanner
*/
public static Scanner openInputFile() {
String filename;
Scanner scanner = null;
System.out.print("Enter the input filename: ");
filename = userScanner.nextLine();
File file = new File(filename);
try {
scanner = new Scanner(file);
} // end try
catch (FileNotFoundException fe) {
System.out.println("Can't open input file ");
return null; // array of 0 elements
} // end catch
return scanner;
} // end openInputFile
}
___________________________________________________________________________
/**
* A class of stacks whose entries are stored in a chain of nodes.
* @author Jae Kim
* @version 1.0
* @date 5/11/2017
* @system windows/eclipse
*/
/**
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0 UPDATED by C. Lee-Klawender
*/
public class LinkedStack<T> implements StackInterface<T> {
private Node topNode; // References the first node in the chain
private int numOfEntries;
// ADD A PRIVATE INT FOR COUNTER THAT INDICATES HOW MANY NODES ARE IN THE
// STACK
public LinkedStack() {
topNode = null;
numOfEntries = 0;
} // end default constructor
public boolean push(T newEntry) {
topNode = new Node(newEntry, topNode);
numOfEntries++;
// ADD CODE SO THE COUNTER IS CORRECT
return true;
} // end push
public T peek() {
if (isEmpty())
return null;
else
return topNode.getData();
} // end peek
public T pop() {
T top = peek();
if (topNode != null) {
topNode = topNode.getNextNode();
numOfEntries--;
// ADD CODE SO THE COUNTER IS CORRECT
}
return top;
} // end pop
public boolean isEmpty() {
if (topNode == null) {
return true;
} else
return false;
} // end isEmpty
public int size() {
return numOfEntries;
}
// WRITE THE "MISSING" METHOD, REQUIRED FOR THIS CLASS SO IT'S NOT ABSTRACT
// (also Ex. 2.2):
private class Node {
private T data; // Entry in stack
private Node next; // Link to next node
private Node(T dataPortion) {
this(dataPortion, null);
} // end constructor
private Node(T dataPortion, Node linkPortion) {
data = dataPortion;
next = linkPortion;
} // end constructor
private T getData() {
return data;
} // end getData
private void setData(T newData) {
data = newData;
} // end setData
private Node getNextNode() {
return next;
} // end getNextNode
private void setNextNode(Node nextNode) {
next = nextNode;
} // end setNextNode
} // end Node
} // end LinkedStack
_______________________________________________________________
import java.util.StringTokenizer;
import java.util.ArrayList;
/**
* InfixExpression breaks the line that is passed into tokens so that it can be
* stored in an arraylist and seperates the token into a value or an operator so
* that it can calculate the expression which is a string and turn it into a
* double value.
*
* @author Jae Kim
* @version 1.0
* @date 5/11/2017
* @system windows/eclipse
*/
public class InfixExpression {
private String wholeExpr; // whole line that is being read for calculation
private ArrayList<String> tokenizedArrayList; // Arraylist of the tokenized
// line.
private double finalResult; // result of the calculation done by the methods
public InfixExpression() {
wholeExpr = " ";
tokenizedArrayList = new ArrayList<String>();
finalResult = 0;
}
/**
* Calls the default constructor and sets the wholeExpr to the parameter
* expression
*
* @param expression
*/
public InfixExpression(String expression) {
this();
setWholeExpr(expression);
}
/**
* Sets the wholeExpr to the parameter Expr.
*
* @param Expr
*/
public void setWholeExpr(String Expr) {
wholeExpr = Expr;
if (wholeExpr != null) {
Tokenize();
Evaluate();
}
}
/**
* It returns the String wholeExpr.
*
* @return
*/
public String getWholeExpr() {
return wholeExpr;
}
/**
* This method returns the finalResult.
*
* @return
*/
public double getFinalResult() {
return finalResult;
}
/**
* This method splits the line by " " into tokens and stores in the Array
* which later is added into the ArrayList
*/
private void Tokenize() {
String[] tokenizedArray = wholeExpr.split("[ ]+");
tokenizedArrayList.clear(); // clear the ArrayList
for (int i = 0; i < tokenizedArray.length; ++i) {
tokenizedArrayList.add(tokenizedArray[i]); // add the next token to
// the ArrayList
}
}
/**
* This method seperates the tokens into operators or operands and stores it
* into opStack if it is an operator and valStack if it is a numeral value.
* It then calls the execute method in the value of precedence.
*/
private void Evaluate() {
StackInterface<String> opStack = new ArrayStack<>();
StackInterface<Double> valStack = new LinkedStack<>();
for (int i = 0; i < tokenizedArrayList.size(); i++) {
String token = tokenizedArrayList.get(i);
if (OpChecker(token)) {
if (opStack.isEmpty()) {
opStack.push(token);
} else if (Precedence(token) > Precedence(opStack.peek())) {
opStack.push(token);
} else {
while (!opStack.isEmpty() && Precedence(token) <= Precedence(opStack.peek())) {
execute(opStack, valStack);
}
opStack.push(token);
}
} else if (token.equals("(")) {
opStack.push(token);
} else if (token.equals(")")) {
// added a condition to check if the stack is empty
while (opStack.peek() != "(" && !opStack.isEmpty()) {
execute(opStack, valStack);
}
} else {
valStack.push(Double.parseDouble(token));
}
}
while (!opStack.isEmpty()) {
execute(opStack, valStack);
}
if (valStack.size() == 1) {
finalResult = valStack.peek();
} else {
finalResult = 0;
}
}
/**
* This method brings in the parameter opStack and valStack from the
* Evaluate() and does the actual calculations that returns the value and
* restores into the valStack and removes an operation from the opStack.
*
* @param opStack
* @param valStack
*/
private void execute(StackInterface<String> opStack, StackInterface<Double> valStack) {
double rightOperand = 0;// the top value of the valStack
double leftOperand = 0;// the second top value of the valStack
double temp = 0;// the value of the operation of the right and
// leftOperand
String op = opStack.pop();
if (valStack.isEmpty()) {
return;
} else {
rightOperand = valStack.pop();
}
if (valStack.isEmpty()) {
valStack.push(rightOperand);
return;
} else {
leftOperand = valStack.pop();
}
switch (op) {
case "+":
temp = leftOperand + rightOperand;
break;
case "-":
temp = leftOperand - rightOperand;
break;
case "*":
temp = leftOperand * rightOperand;
break;
case "/":
temp = leftOperand / rightOperand;
break;
// I added the default just in case that it is not any of the cases up
// above
default:
valStack.push(leftOperand);
valStack.push(rightOperand);
return;
}
valStack.push(temp);
}
/**
* This method returns true if the parametere String is an operator, false
* if not.
*
* @param operator
* @return
*/
private boolean OpChecker(String operator) {
if (operator.equals("+") || operator.equals("-") || operator.equals("*") || operator.equals("/")) {
return true;
} else
return false;
}
/**
* This returns the int value of the operators so it can be determined which
* operator to execute first
*
* @param operator
* @return
*/
private int Precedence(String operator) {
if (operator.equals("(") || operator.equals(")")) {
return 1;
} else if (operator.equals("/") || operator.equals("*")) {
return 2;
} else
return 3;
}
/**
* This method returns the String form of the wholeExpr and the final
* result.
*/
public String toString() {
return "Infix String: " + wholeExpr + ", " + "result: " + finalResult;
}
}
______________________________________________________________
import java.util.*;
/**
* A class of stacks whose entries are stored in an array.
* @author Jae Kim
* @version 1.0
* @date 5/11/2017
* @system windows/eclipse
*/
/**
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0 UPDATED by C. Lee-Klawender
*/
public class ArrayStack<T> implements StackInterface<T> {
private T[] stack; // Array of stack entries
private int topIndex; // Index of top entry
private static final int DEFAULT_CAPACITY = 15;
private static final int MAX_CAPACITY = 100;
public ArrayStack() {
this(DEFAULT_CAPACITY);
} // end default constructor
public ArrayStack(int initialCapacity) {
if (initialCapacity > MAX_CAPACITY)
initialCapacity = MAX_CAPACITY;
else if (initialCapacity < DEFAULT_CAPACITY)
initialCapacity = DEFAULT_CAPACITY;
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempStack = (T[]) new Object[initialCapacity];
stack = tempStack;
topIndex = -1;
} // end constructor
public boolean push(T newEntry) {
if (topIndex + 1 < stack.length) {
stack[topIndex + 1] = newEntry;
topIndex++;
return true;
}
return false;
} // end push
public T peek() {
if (isEmpty()) // UPDATE FOR HW#1
return null;
else
return stack[topIndex];
} // end peek
public T pop() {
if (isEmpty()) // UPDATE FOR HW#1
return null;
else {
T top = stack[topIndex];
stack[topIndex] = null;
topIndex--;
return top;
} // end if
} // end pop
public boolean isEmpty() {
if (stack[0] == null) {
return true;
} else
return false;
}
public int size() {
return 0;
}
// TWO MORE METHODS ARE REQUIRED HERE (PART OF EXERCISE 2.1)
} // end ArrayStack
______________________________________________________________________
public interface StackInterface<T> {
/**
* Adds a new entry to the top of this stack.
*
* @param newEntry
* An object to be added to the stack.
*/
public boolean push(T newEntry);
/**
* Removes and returns this stack's top entry.
*
* @return The object at the top of the stack. or null if the stack is empty
*/
public T pop();
/**
* Retrieves this stack's top entry (without removing).
*
* @return The object 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 isEmpty();
/**
* Returns number of items in this stack
*
* @return: Number of items
*/
public int size();
} // end StackInterface
____________________________________________________________________
/**
A class that implements the ADT queue by using a chain of nodes
that has both head and tail references.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
UPDATED by C. Lee-Klawender
NOTE: the LinkedQueue class includes the Node class as an inner class
*/
public class LinkedQueue<T> implements QueueInterface<T>
{
private Node frontNode; // References node at front of queue
private Node backNode; // References node at back of queue
private int count = 0;
public LinkedQueue()
{
frontNode = null;
backNode = null;
} // end default constructor
public boolean enqueue(T newEntry)
{
if(count == 0){
frontNode = new Node(newEntry);
backNode = frontNode;
} else {
if(backNode == frontNode){
backNode = frontNode.next;
backNode = new Node(newEntry);
} else {
backNode = backNode.next;
backNode = new Node(newEntry);
}
}
// ADD CODE TO add data to linked list HERE!
// In addition to updating the backNode, also
// make sure you check if the list was empty before adding this
// and update the correct variable if so
++count;
return true;
} // end enqueue
public T peekFront()
{
if (isEmpty())
return null;
else
return frontNode.getData();
} // end getFront
public T dequeue()
{
T front = peekFront();
if( count > 0 )
{
frontNode.data = null;
frontNode = frontNode.next;
// ADD CODE TO remove data from linked list HERE!
// In addition to updating the frontNode, also
// make sure to check if the list becomes empty and
// update the correct variable if so
--count;
}
return front;
} // end dequeue
public boolean isEmpty()
{
if(frontNode == null)
return true;
else
return false;
} // end isEmpty
public int size()
{
return count;
}
private class Node
{
private T data; // Entry in queue
private Node next; // Link to next node
private Node(T dataPortion)
{
data = dataPortion;
next = null;
} // end constructor
private Node(T dataPortion, Node linkPortion)
{
data = dataPortion;
next = linkPortion;
} // end constructor
private T getData()
{
return data;
} // end getData
private void setData(T newData)
{
data = newData;
} // end setData
private Node getNextNode()
{
return next;
} // end getNextNode
private void setNextNode(Node nextNode)
{
next = nextNode;
} // end setNextNode
} // end Node
} // end Linkedqueue
________________________________________________________________________
/**
* A class that implements the ADT queue by using an expandable circular array
* with one unused location after the back of the queue.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.1 UPDATED BY C. Lee-Klawender
*/
public final class ArrayQueue<T> implements QueueInterface<T> {
private T[] queue; // Circular array of queue entries
private int frontIndex; // Index of front entry
private int backIndex; // Index of back entry
private int count;
private static final int DEFAULT_CAPACITY = 5;
private static final int MAX_CAPACITY = 100;
public ArrayQueue() {
this(DEFAULT_CAPACITY);
} // end default constructor
public ArrayQueue(int initialCapacity) {
if (initialCapacity < DEFAULT_CAPACITY)
initialCapacity = DEFAULT_CAPACITY;
else if (initialCapacity > MAX_CAPACITY)
initialCapacity = MAX_CAPACITY;
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempQueue = (T[]) new Object[initialCapacity];
queue = tempQueue;
frontIndex = 0;
backIndex = queue.length - 1;
count = 0;
} // end constructor
public boolean enqueue(T newEntry) {
if (count < queue.length) {
backIndex = (backIndex + 1) % queue.length;
queue[backIndex] = newEntry;
++count;
return true;
} else
return false;
} // end enqueue
public T peekFront() {
if (isEmpty())
return null;
return queue[frontIndex];
} // end getFront
public T dequeue() {
if (isEmpty())
return null;
else {
--count;
T frontItem = queue[frontIndex];
queue[frontIndex] = null;
frontIndex = (frontIndex + 1) % queue.length; // Index of new front
// of queue
return frontItem;
} // end if
} // end dequeue
public boolean isEmpty() {
return count == 0;
} // end isEmpty
public int size() {
return count;
}
} // end ArrayQueue
Explanation / Answer
Find the program below:
/**
Main driver that tests the InfixExpression class's methods function. Also tests that the
LinkedQueue and LinkedQueue are working correctly for the InfixExpression class.
@author Jae Kim
@version 1.0
@date 5/11/2017
@system windows/eclipse
*/
import java.io.*;
import java.util.Scanner;
public class Main {
/**
* calls the openInputFile method and testHW method to see if those methods
* are working correctly. It will keep reading until the line in the file is
* blank.
*
* @param args
*/
public static void main(String[] args) {
Scanner Scanning = openInputFile(); // the return of Scanned file of the
// openInputFile
while (Scanning.hasNextLine()) {
String lineRead = Scanning.nextLine(); //The next line of the file read.
InfixExpression inputLineCalculation = new InfixExpression();
inputLineCalculation.setWholeExpr(lineRead);
System.out.println(inputLineCalculation.toString());
}
testHW1();
}
public static Scanner userScanner = new Scanner(System.in);
/**
* Declares a new instance of the InfixExpression to test the null parameter
* and a string parameter to see if the InfixExpression class works
* correctly. It also tests if the LinkedQueue and the LinkedQueue classes
* are working correctly.
*/
public static void testHW1() { // testing InfixExpression more:
InfixExpression infix1, infix2;
infix1 = new InfixExpression(null);
infix2 = new InfixExpression("( 234.5 * ( 5.6 + 7.0 ) ) / 100.2");
System.out.println(" Testing InfixExpression:");
System.out.println("When passing null, the String and double = " + infix1.toString());
System.out.println("When passing a valid String, the String and double = " + infix2.toString());
// testing LinkedQueue and LinkedQueue more:
LinkedQueue<String> arrStack = new LinkedQueue<>();
LinkedQueue<String> linkStack = new LinkedQueue<>();
String[] strArray = { "First", "Second", "Third", "Fourth", "Fifth", "Sixth", "Seventh", "Eighth", "Ninth",
"Tenth" };
// Testing LinkedQueue
System.out.println(" Testing the LinkedQueue:");
for (int i = 0; i < strArray.length; ++i) {
if (!arrStack.push(strArray[i] + " 1"))
System.out.println("Error: couldn't push " + strArray[i] + " 1");
}
for (int i = 0; i < strArray.length; ++i) {
if (!arrStack.push(strArray[i] + " 2")) {
System.out.println("Out of space, removing " + arrStack.pop());
if (!arrStack.push(strArray[i] + " 2"))
System.out.println("Error pushing!" + strArray[i] + " 2");
}
}
System.out.println("The size of the LinkedQueue is now " + arrStack.size());
while (!arrStack.isEmpty()) {
System.out.println("Popping " + arrStack.pop());
}
System.out.println("The size of the LinkedQueue is now " + arrStack.size());
if (!arrStack.push(strArray[0] + " 3"))
System.out.println("Error: couldn't push " + strArray[0] + " 3");
else
System.out.println(
"After pushing " + arrStack.peek() + ", the size of the LinkedQueue is now " + arrStack.size());
// testing LinkedQueue
System.out.println(" Testing the LinkedQueue:");
for (int i = 0; i < strArray.length; ++i)
linkStack.push(strArray[i] + " 4");
System.out.println("The size of the LinkedQueue is " + linkStack.size());
for (int i = 0; i < strArray.length / 2; ++i) {
System.out.println("Popping " + linkStack.pop());
}
System.out.println("The size of the LinkedQueue is now " + linkStack.size());
while (!linkStack.isEmpty()) {
System.out.println("Popping " + linkStack.pop());
}
System.out.println("The size of the LinkedQueue is now " + linkStack.size());
if (!linkStack.push(strArray[0] + " 5"))
System.out.println("Error: couldn't push " + strArray[0] + " 5");
else
System.out.println(
"After pushing " + linkStack.peek() + ", the size of the LinkedQueue is now " + linkStack.size());
} // end stackTester
/**
* This method reads the file that is typed in from the console so that the
* file is read.
*
* @return Scanner
*/
public static Scanner openInputFile() {
String filename;
Scanner scanner = null;
System.out.print("Enter the input filename: ");
filename = userScanner.nextLine();
File file = new File(filename);
try {
scanner = new Scanner(file);
} // end try
catch (FileNotFoundException fe) {
System.out.println("Can't open input file ");
return null; // array of 0 elements
} // end catch
return scanner;
} // end openInputFile
}
--------------------------------
/**
* A class of stacks whose entries are stored in a chain of nodes.
* @author Jae Kim
* @version 1.0
* @date 5/11/2017
* @system windows/eclipse
*/
/**
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0 UPDATED by C. Lee-Klawender
*/
public class LinkedQueue<T> implements StackInterface<T> {
private Node topNode; // References the first node in the chain
private int numOfEntries;
// ADD A PRIVATE INT FOR COUNTER THAT INDICATES HOW MANY NODES ARE IN THE
// STACK
public LinkedQueue() {
topNode = null;
numOfEntries = 0;
} // end default constructor
public boolean push(T newEntry) {
topNode = new Node(newEntry, topNode);
numOfEntries++;
// ADD CODE SO THE COUNTER IS CORRECT
return true;
} // end push
public T peek() {
if (isEmpty())
return null;
else
return topNode.getData();
} // end peek
public T pop() {
T top = peek();
if (topNode != null) {
topNode = topNode.getNextNode();
numOfEntries--;
// ADD CODE SO THE COUNTER IS CORRECT
}
return top;
} // end pop
public boolean isEmpty() {
if (topNode == null) {
return true;
} else
return false;
} // end isEmpty
public int size() {
return numOfEntries;
}
// WRITE THE "MISSING" METHOD, REQUIRED FOR THIS CLASS SO IT'S NOT ABSTRACT
// (also Ex. 2.2):
private class Node {
private T data; // Entry in stack
private Node next; // Link to next node
private Node(T dataPortion) {
this(dataPortion, null);
} // end constructor
private Node(T dataPortion, Node linkPortion) {
data = dataPortion;
next = linkPortion;
} // end constructor
private T getData() {
return data;
} // end getData
private void setData(T newData) {
data = newData;
} // end setData
private Node getNextNode() {
return next;
} // end getNextNode
private void setNextNode(Node nextNode) {
next = nextNode;
} // end setNextNode
} // end Node
} // end LinkedQueue
--------------------------------------
import java.util.*;
/**
* A class of stacks whose entries are stored in an array.
* @author Jae Kim
* @version 1.0
* @date 5/11/2017
* @system windows/eclipse
*/
/**
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0 UPDATED by C. Lee-Klawender
*/
public class ArrayQueue<T> implements StackInterface<T> {
private T[] stack; // Array of stack entries
private int topIndex; // Index of top entry
private static final int DEFAULT_CAPACITY = 15;
private static final int MAX_CAPACITY = 100;
public ArrayQueue() {
this(DEFAULT_CAPACITY);
} // end default constructor
public ArrayQueue(int initialCapacity) {
if (initialCapacity > MAX_CAPACITY)
initialCapacity = MAX_CAPACITY;
else if (initialCapacity < DEFAULT_CAPACITY)
initialCapacity = DEFAULT_CAPACITY;
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempStack = (T[]) new Object[initialCapacity];
stack = tempStack;
topIndex = -1;
} // end constructor
public boolean push(T newEntry) {
if (topIndex + 1 < stack.length) {
stack[topIndex + 1] = newEntry;
topIndex++;
return true;
}
return false;
} // end push
public T peek() {
if (isEmpty()) // UPDATE FOR HW#1
return null;
else
return stack[topIndex];
} // end peek
public T pop() {
if (isEmpty()) // UPDATE FOR HW#1
return null;
else {
T top = stack[topIndex];
stack[topIndex] = null;
topIndex--;
return top;
} // end if
} // end pop
public boolean isEmpty() {
if (stack[0] == null) {
return true;
} else
return false;
}
public int size() {
return 0;
}
// TWO MORE METHODS ARE REQUIRED HERE (PART OF EXERCISE 2.1)
} // end ArrayQueue
-----------------------------------------
public interface StackInterface<T> {
/**
* Adds a new entry to the top of this stack.
*
* @param newEntry
* An object to be added to the stack.
*/
public boolean push(T newEntry);
/**
* Removes and returns this stack's top entry.
*
* @return The object at the top of the stack. or null if the stack is empty
*/
public T pop();
/**
* Retrieves this stack's top entry (without removing).
*
* @return The object 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 isEmpty();
/**
* Returns number of items in this stack
*
* @return: Number of items
*/
public int size();
} // end StackInterface
____________________________________________________________________
/**
A class that implements the ADT queue by using a chain of nodes
that has both head and tail references.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
UPDATED by C. Lee-Klawender
NOTE: the LinkedQueue class includes the Node class as an inner class
*/
public class LinkedQueue<T> implements QueueInterface<T>
{
private Node frontNode; // References node at front of queue
private Node backNode; // References node at back of queue
private int count = 0;
public LinkedQueue()
{
frontNode = null;
backNode = null;
} // end default constructor
public boolean enqueue(T newEntry)
{
if(count == 0){
frontNode = new Node(newEntry);
backNode = frontNode;
} else {
if(backNode == frontNode){
backNode = frontNode.next;
backNode = new Node(newEntry);
} else {
backNode = backNode.next;
backNode = new Node(newEntry);
}
}
// ADD CODE TO add data to linked list HERE!
// In addition to updating the backNode, also
// make sure you check if the list was empty before adding this
// and update the correct variable if so
++count;
return true;
} // end enqueue
public T peekFront()
{
if (isEmpty())
return null;
else
return frontNode.getData();
} // end getFront
public T dequeue()
{
T front = peekFront();
if( count > 0 )
{
frontNode.data = null;
frontNode = frontNode.next;
// ADD CODE TO remove data from linked list HERE!
// In addition to updating the frontNode, also
// make sure to check if the list becomes empty and
// update the correct variable if so
--count;
}
return front;
} // end dequeue
public boolean isEmpty()
{
if(frontNode == null)
return true;
else
return false;
} // end isEmpty
public int size()
{
return count;
}
private class Node
{
private T data; // Entry in queue
private Node next; // Link to next node
private Node(T dataPortion)
{
data = dataPortion;
next = null;
} // end constructor
private Node(T dataPortion, Node linkPortion)
{
data = dataPortion;
next = linkPortion;
} // end constructor
private T getData()
{
return data;
} // end getData
private void setData(T newData)
{
data = newData;
} // end setData
private Node getNextNode()
{
return next;
} // end getNextNode
private void setNextNode(Node nextNode)
{
next = nextNode;
} // end setNextNode
} // end Node
} // end Linkedqueue
-------------------------------------------
/**
* A class that implements the ADT queue by using an expandable circular array
* with one unused location after the back of the queue.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.1 UPDATED BY C. Lee-Klawender
*/
public final class ArrayQueue<T> implements QueueInterface<T> {
private T[] queue; // Circular array of queue entries
private int frontIndex; // Index of front entry
private int backIndex; // Index of back entry
private int count;
private static final int DEFAULT_CAPACITY = 5;
private static final int MAX_CAPACITY = 100;
public ArrayQueue() {
this(DEFAULT_CAPACITY);
} // end default constructor
public ArrayQueue(int initialCapacity) {
if (initialCapacity < DEFAULT_CAPACITY)
initialCapacity = DEFAULT_CAPACITY;
else if (initialCapacity > MAX_CAPACITY)
initialCapacity = MAX_CAPACITY;
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempQueue = (T[]) new Object[initialCapacity];
queue = tempQueue;
frontIndex = 0;
backIndex = queue.length - 1;
count = 0;
} // end constructor
public boolean enqueue(T newEntry) {
if (count < queue.length) {
backIndex = (backIndex + 1) % queue.length;
queue[backIndex] = newEntry;
++count;
return true;
} else
return false;
} // end enqueue
public T peekFront() {
if (isEmpty())
return null;
return queue[frontIndex];
} // end getFront
public T dequeue() {
if (isEmpty())
return null;
else {
--count;
T frontItem = queue[frontIndex];
queue[frontIndex] = null;
frontIndex = (frontIndex + 1) % queue.length; // Index of new front
// of queue
return frontItem;
} // end if
} // end dequeue
public boolean isEmpty() {
return count == 0;
} // end isEmpty
public int size() {
return count;
}
} // end ArrayQueue
-----------*--------------------------