JAVA

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

//

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