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) {

// 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 ( ) {

// call your helper function here //TODO 5

// nothing for you to change below here except debugging options

// 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;

}

}