Question
package algs11; import java.util.NoSuchElementException; import stdlib.StdOut; import stdlib.Trace; // CSC Homework 7 version 1.2 // mainDebug commented out // mainTests commented in // A queue
package algs11;
import java.util.NoSuchElementException;
import stdlib.StdOut;
import stdlib.Trace;
// CSC Homework 7 version 1.2
// mainDebug commented out
// mainTests commented in
// A queue is implemented using a slngly linked list.
// the variable: back "points" at the first node in the linked list
// new elements ( enqueued) are added at the back
// the variable: front "points" at the last node in the linked list.
// elements are removed (dequeued) from the front
// this is the OPPOSITE of the implementation we reviewed in class; the one in the book
// This is NOT a good way to implement a queue, but makes a good exercise
// in practicing coding with linked lists
//
// Several queue instance methods are provided for you; do not change these
// Other instance methods are left for you as "ToDo" tasks
//
// You may not use any other Java classes or algorithms in completing the ToDo items
// You may not add any instance variables to the class
// You may add your own private instance methods for modularity sake
//
public class CSC300Queue {
private Node back, front;
static boolean showMeSuccess = false; // change to true to also show tests that pass
static class Node {
public Node (char item, Node next) { this.item = item; this.next = next; }
public char item;
public Node next;
}
// isEmpty
// determine if the queue is empty
// since back is the first node in the linked list, if back is null - there is no linked list, hence the queue is empty
public boolean isEmpty() {
return back==null;
}
// frontItem
// return the item at the front of the queue without removing it
// this is often called 'peek'
// precondition: queue is not empty
//
// this example illustrates checking to see if the precondition is satisfied and
// handling the error if it is not
//
public char frontItem() {
if ( back == null) // there are no nodes - so the queue is empty, client failed!
throw new NoSuchElementException("there is no front item in an empty queue!");
else if (front == null) // this should not happen, if so the programmer failed!
throw new NoSuchElementException("an internal error has occurred in CSC300Queue: null front pointer");
else
return front.item;
}
// backItem
// return the item at the back of the queue without altering the queue
// precondition: queue is not empty
//
// this example illustrates checking to see if the precondition is satisfied and
// handling the error if it is not
//
public char backItem() {
if ( back == null) // queue is empty, user failed!
throw new NoSuchElementException("the queue is empty!");
else
return back.item;
}
// enqueue
// add an item to the back of the queue
public void enqueue( char item) {
Node aNode = new Node( item, back); // create new node with item AND
// tack existing queue onto end of new node using constructor
if ( back == null) { // queue was empty
back = front = aNode; // so the new node is both front and back
}
else // new node is now at the 'back'
back = aNode;
}
******
// removeEveryKthNode
//
// this function will remove every kth element in the original queue
//
// your function should start at the BACK of the queue and work toward the front.
// here are some conceptual examples ( they also mirror what your linked lists will look like)
// the back is on the left and the front is on the right.
// Example 1. A B C D E F G H I J, k = 2
// Result: original queue is now: A C E G I
// Example 2. A B C D E F G H I J, k = 3
// Result: original queue is now: A B D E G H J
//
// Your solution must work directly on the underlying linked structure
// You may not use any other containers or Java classes to solve the problem
// precondition: k >= 1
public void removeEveryKthNode(int k) {
*******TODO#1
*******// isOrdered
//
// return true if the queue contents are in increasing order (back to front)
// Queue may be empty ; in which case the function should return true
// You must solve this USING RECURSION; you will need to use a helper function
// You may not use:
// any other Java classes, algorithms,
// the toString instance method
// You may not alter the invoking queue
//
// here are some conceptual examples ( they also mirror what your linked lists will look like)
// the back is on the left and the front is on the right.
// Example 1. A B C D E F G H I J --> answer true ,
// Example 2. C B A --> answer false
// Example 3. C --> answer true
//
public boolean isOrdered() {
*******TODO#2
// for debugging purposes, you may comment/uncomment the two calls in main below
// you should restore the call to mainRunTests as below when you submit your solution
public static void main( String[] args) {
//mainDebug();
mainRunTests();
}
private static void mainDebug () {
// Use this for debugging!
// Add the names of helper functions if you use them.
Trace.drawStepsOfMethod ("sizeRecursive");
Trace.drawStepsOfMethod ("toString");
Trace.drawStepsOfMethod ("removeEveryKthNode");
Trace.drawStepsOfMethod ("dequeue");
Trace.run ();
// To Use: Put the test here you want to debug:
testRemoveEveryKthNode( "abcdef",3,"abde"); // source queue data, value of k
}
private static void mainRunTests () {
testDequeue("abcd",'d','c'); // source data, dequeued value, new front value
testDequeue("abc",'c','b');
testDequeue("ab",'b','a');
testDequeue("a",'a',' ');
testSizeRecursive (0, ""); // expected queue size, queue source data
testSizeRecursive (1, "a");
testSizeRecursive (2, "ab");
testSizeRecursive (4, "abcd");
testToString("a","a"); // queue source , expected value of toString
testToString("ab","ba");
testToString("abc","cba");
testToString("abcd","dcba");
testRemoveEveryKthNode( "abcdef",2,"ace"); // source queue data, value of k, expected queue
testRemoveEveryKthNode( "abcdef",3,"abde");
testRemoveEveryKthNode( "abcdefg",2,"aceg");
testRemoveEveryKthNode( "abcdefgh",3,"abdegh");
testRemoveEveryKthNode( "abcdefghijkl",4,"abcefgijk");
testRemoveEveryKthNode("abcdef",1,"");
testIsOrdered("abcde",true); // source queue data, expected answer
testIsOrdered("eabcd",false);
testIsOrdered("aebcd",false);
testIsOrdered("abecd",false);
testIsOrdered("abced",false);
testIsOrdered("a",true);
testIsOrdered("ba",false);
}
// lots of copy and paste in these tests!
private static void testSizeRecursive (int expected, String qData) {
CSC300Queue aQueue = CSC300Queue.of (qData); // create queue from string data using *of* function
int actual = aQueue.sizeRecursive(); // invoke function to be tested
boolean status = true;
if (expected != actual) { // compare actual to expected answer
StdOut.format ("Failed sizeRecursive(): SourceData [%s] Expecting [%d] Actual [%d] ", qData, expected, actual);
status = false;
}
if ( status && showMeSuccess)
StdOut.format ("Success sizeRecursive(): SourceData [%s] Result: %d ", qData,actual);
}
private static void testToString ( String qData, String expected) {
CSC300Queue aQueue = CSC300Queue.of (qData); // create queue from string data using *of* function
String actual = aQueue.toString (); // invoke function to be tested
boolean status = true;
if (!actual.equals(expected)) { // compare actual to expected answer
StdOut.format ("Failed toString: Expecting [%s] Actual [%s] ", expected, actual);
status = false;
}
if ( status && showMeSuccess)
StdOut.format ("Success toString: Expecting [%s] Actual [%s] ", expected, actual);
}
// testDequeue
// check 1: length decreases by 1
// check 2: dequeued character is correct
// check 3: new front char is correct
private static void testDequeue ( String qData, char expectedRemoved, char expectedNewFront) {
CSC300Queue aQueue = CSC300Queue.of (qData);
char actualRemoved = aQueue.dequeue(); // invoke function to be tested
boolean status = true;
int expectedSize = qData.length()-1;
int actualSize = aQueue.sizeIterative();
if ( actualSize != expectedSize) { // compare actual to expected answer
StdOut.format ("Failed dequeue: Expected size [%d] Actual size [%d] ", expectedSize, actualSize);
status = false;
}
if ( actualRemoved != expectedRemoved) { // compare actual to expected answer
StdOut.format ("Failed dequeue: Expected char [%c] Actual char [%c] ", expectedRemoved, actualRemoved);
status = false;
}
if ( actualSize >=1 ) {
char actualFront = aQueue.frontItem(); // check the front
if( expectedNewFront != actualFront ) {
StdOut.format ("Failed dequeue: Expected front [%c] Actual char [%c] ", expectedNewFront, actualFront);
status = false;
}
}
if ( status && showMeSuccess)
StdOut.format ("Success dequeue: Source: [%s], dequeued value [%c] ", qData, actualRemoved);
}
private static void testRemoveEveryKthNode( String qData, int k, String expected) {
CSC300Queue aQueue = CSC300Queue.of (qData);
aQueue.removeEveryKthNode(k); // invoke function to be tested
String r = extra(aQueue);
boolean status = true;
if (!r.equals(expected)) {
StdOut.format ("Failed removeEveryKthNode: Expecting [%s] Actual [%s] ", expected, r);
status = false;
}
if ( status && showMeSuccess)
StdOut.format ("Success removeEveryKthNode: Source= [%s] k= [%d] Result= [%s] ", qData,k, r);
}
private static void testIsOrdered( String qData, boolean expected) {
CSC300Queue aQueue = CSC300Queue.of (qData);
boolean status = true;
if ( aQueue.isOrdered() != expected) { // invoke function to be tested
StdOut.format ("Failed isOrdered: Source= [%s] Expecting [%b] ",qData, expected);
status = false;
}
if ( status && showMeSuccess)
StdOut.format ("Success isOrdered: Source= [%s] Expecting [%b] ",qData, expected);
}
/* Method to create populate queues */
public static CSC300Queue of(String s) {
Node first = null;
CSC300Queue result = new CSC300Queue ();
for (int i = s.length()-1; i >= 0; i--) {
first = new Node (s.charAt(i), first);
if ( i==s.length()-1 ) result.front=first;
}
result.back =first;
return result;
}
// extra method
public static String extra( CSC300Queue q) {
String t = "";
for ( Node tmp=q.back; tmp != null; tmp = tmp.next)
t += tmp.item;
return t;
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started