Data Structures and Algorithms C programming. help please.

This is the framework provided to implement and use a queue. One file main.c is a collection of tests for the queue (the first one below). The other file is the prototypes and data structures necessary for the problem (the queue.h down below). Can show me how the queue.c pseudocode along with line comments that can implement all the functions described in queue.h file look like?

main.c:

/* A collection of tests for the student's Queue Data Structure */

//-----------You May NOT change this file------ #include "queue.h" #include #include #include

/** Check if creating a new queue works @return 1 on success and 0 on failure */ char testNewQueue(); /** Check the Enqueue functionality @return 1 on success and 0 on failure */ char testEnqueue(); /** Check the front functionality @return 1 on success and 0 on failure */ char testFront(); /** Check the isEmpty functionality @return 1 on success and 0 on failure */ char testIsEmpty(); /** Check the Dequeue functionality @return 1 on success and 0 on failure */ char testDequeue(); /** Finalize a series of random tests to stress test Queue @return 1 on success and 0 on failure */ char testRandom(); /** Check if target is the last value in the queue @param Q is the Queue to Check @param target is the value to look for at the end of the queue @return 1 on success and 0 on failure */ char checkTail(struct Queue *Q, int target); /** Run the Josephus Puzzle */ void testJosephus();

/** Ask user for inputs to test. Run all tests requested. @param argv is not used @param argc is not used @return 1 on menu error and 0 otherwise */ int main(int argv, char **argc) { srand(time(0)); // Ask the user what to do printf("Select Option from list. "); printf("0.) Run All Tests "); printf("1.) Test New Queue "); printf("2.) Test Enqueue "); printf("3.) Test Front "); printf("4.) Test isEmpty "); printf("5.) Test Dequeue "); printf("6.) Run Randomized Tests "); printf("7.) Josephus Puzzle "); printf("Enter Number of test to run: "); // Get the Users Option int testToRun = -1; int result = scanf("%d", &testToRun); if (result != 1 || testToRun < 0 || testToRun > 7) { printf("Invalid Menu Selection. "); return 1; } // Run Tests based on input switch (testToRun) { case 7: testJosephus(); break; case 0: printf("Running ALL Tests "); case 1: if (!testNewQueue()) { return 1; } if (testToRun != 0) { break; }; case 2: if (!testEnqueue()) { return 1; } if (testToRun != 0) { break; }; case 3: if (!testFront()) { return 1; } if (testToRun != 0) { break; }; case 4: if (!testIsEmpty()) { return 1; } if (testToRun != 0) { break; }; case 5: if (!testDequeue()) { return 1; } if (testToRun != 0) { break; }; case 6: if (!testRandom()) { return 1; } if (testToRun != 0) { break; }; } return 0; }

// Test Creation // Inputs: None // Outputs: 1 if passed 0 if failed // Side Effects: Prints reason for failure or success char testNewQueue() { struct Queue *Q = newQueue(); if (Q == NULL) { printf("newQueue: FAILED "); printf("Calling newQueue returned NULL. "); return 0; } if (Q->head != NULL) { printf("newQueue: FAILED "); printf("Calling newQueue return object that did not have NULL head. "); return 0; } if (Q->tail != NULL) { printf("newQueue: FAILED "); printf("Calling newQueue return object that did not have NULL tail. "); return 0; } printf("newQueue: PASSED "); return 1; }

// Test Enqueue // Inputs: None // Outputs: 1 if passed 0 if failed // Side Effects: Prints reason for failure or success char testEnqueue() { struct Queue *Q = newQueue(); int tests = 10; // Check that elements are added in for (int i = 0; i < tests; i++) { enqueue(i, Q); // Sanity Check if (Q->head == NULL) { printf("enqueue: FAILED "); printf("Head Null After Enqueue Call! "); return 0; } if (Q->tail == NULL) { printf("enqueue: FAILED "); printf("Tail Null After Enqueue Call! "); return 0; } // Check for Value if (!checkTail(Q, i)) { printf("enqueue: FAILED "); printf("enqueue(%d,Q) did not add %d to tail of queue. ", i, i); printf("Tail Pointer must point to number. "); printQueue(Q); return 0; } } // Check the Whole List struct Node *ptr = Q->head; int count = 0; while (ptr != NULL) { if (ptr->value != count) { printf("Inserted Numbers from 0 to %d into Q. ", tests); printf("Did not find %d in correct location. ", count); printQueue(Q); return 0; } count++; ptr = ptr->next; } printf("enqueue: PASSED "); return 1; }

// Test Front of Queue // Inputs: None // Outputs: 1 if passed 0 if failed // Side Effects: Prints reason for failure or success char testFront() { struct Queue *Q = newQueue(); if (front(Q) != -1) { printf("Front must return -1 on empty queue. "); printQueue(Q); printf("front: FAILED "); return 0; } enqueue(9, Q); if (front(Q) != 9) { printf("Called enqueue(9,Q) and 9 was not front afterwards. "); printQueue(Q); printf("front: FAILED "); return 0; } enqueue(7, Q); if (front(Q) != 9) { printf("Called enqueue(7,Q) after enqueue(9,Q) and 9 was not front " "afterwards. "); printQueue(Q); printf("front: FAILED "); return 0; } printf("front: PASSED "); return 1; }

// Test isEmpty // Inputs: None // Outputs: 1 if passed 0 if failed // Side Effects: Prints reason for failure or success char testIsEmpty() { struct Queue *Q = newQueue(); if (!isEmpty(Q)) { printf("Called isEmpty on a new Queue. "); printf("Function did not return true. "); printQueue(Q); printf("isEmpty: FAILED "); return 0; } enqueue(8, Q); if (isEmpty(Q)) { printf("Called isEmpty on Queue Containing 8. "); printf("Function did not return false. "); printQueue(Q); printf("isEmpty: FAILED "); return 0; } printf("isEmpty: PASSED "); return 1; }

// Test Dequeue // Inputs: None // Outputs: 1 if passed 0 if failed // Side Effects: Prints reason for failure or success char testDequeue() { struct Queue *Q = newQueue(); // Insert 1-5 for (int i = 1; i < 6; i++) { enqueue(i, Q); } int expected = 1; while (!isEmpty(Q)) { if (front(Q) != expected) { printf("Expected %d at front of Queue but saw %d. ", expected, front(Q)); printf("Possible error in dequeue. "); printQueue(Q); printf("dequeue: FAILED "); return 0; } dequeue(Q); expected++; } if (expected != 6) { printf("Dequeue should have removed %d things but only removed %d. ", 6, expected); printf("Possible error in dequeue. "); printQueue(Q); printf("dequeue: FAILED "); return 0; }

printf("dequeue: PASSED "); return 1; }

// Insert and Delete some random numbers // Inputs: None // Outputs: 1 if passed 0 if failed // Side Effects: Prints reason for failure or success char testRandom() { // This test generates 3 random arrays // It adds then removes all the numbers from the same queue struct Queue *Q = newQueue(); for (int i = 0; i < 3; i++) { // Determine Size int size = rand() % 10 + 1; // Make array int *T = malloc(size * sizeof(int)); // Put random numbers in for (int k = 0; k < size; k++) { T[k] = rand() % 100 + 1; } // Enqueue them all for (int k = 0; k < size; k++) { enqueue(T[k], Q); } // Dequeue them all for (int k = 0; k < size; k++) { if (front(Q) != T[k]) { // Something Bad Happened printf("Attempted to enqueue and dequeue repeatedly from Queue. "); printf("Failed on Repetition %d on Queue. ", i); printf("Tried to enqueue and dequeue: ["); for (int a = 0; a < size; a++) { printf("%d", T[a]); if (a + 1 != size) { printf(", "); } } printf("] "); printQueue(Q); printf("Random Values: FAILED "); return 0; } dequeue(Q); } } printf("Random Values: PASSED "); return 1; }

// Checks for last element in list // Inputs: Pointer to Q and Target // Outputs: 1 if value is at tail and 0 otherwise // Side Effects: None char checkTail(struct Queue *Q, int target) { struct Node *ptr = Q->tail; // Compare to last element return ptr->value == target; }

// Test the student's Josephus Function // Inputs: None // Outputs: None // Side Effects: Reads from stdin and writes to stdout void testJosephus() { int n; int m; printf("Enter Number of People (N): "); scanf("%d", &n); printf("Enter Person to Eliminate (M): "); scanf("%d", &m); int *R = josephus(n, m); // We know the expected number of results is n printf("Order Eliminated: "); for (int i = 0; i < n; i++) { printf("%d", R[i]); if (i + 1 < n) { printf(" "); } } printf(" "); free(R); return; }

------- -----------------------------------------------------------------------------------------

queue.h:

/**

This is the header file for a classic queue data structure. It includes the Queue Structure and all methods needed. */

//-----You May NOT change this file-----

#ifndef _QUEUE_H_ #define _QUEUE_H_

/** A structure to represent a single node in a one directional linked list. */ struct Node { int value; /**< The value stored at this node. */ struct Node *next; /**< A pointer to the next node in the list. */ }; // Give the struct a short name typedef struct Node Node;

/** A structure to represent a classic Queue. */ struct Queue { Node *head; /**< Pointer to the first value in queue. */ Node *tail; /**< Pointer to last value in the queue. */ }; // Give the Queue a short name typedef struct Queue Queue;

/** Develop a new empty queue. @return A pointer to the new queue struct */ Queue *newQueue();

/** Determine if the queue is empty @param Q is the queue to check @return 1 for True and 0 for false */ char isEmpty(Queue *Q);

/** Add a new value to the end of the queue @param v is the value to add @param Q is the Q to add the value to */ void enqueue(int v, Queue *Q);

/** Determine the value at the front of the queue @param Q is the queue to look at @return The first value in the queue or -1 if the queue is empty */ int front(Queue *Q);

/** Remove the first value from the queue @param Q is the queue to remove from */ void dequeue(Queue *Q);

/** Print the Queue to STD out. Used for debugging. @param Q is the queue to print */ void printQueue(Queue *Q);

/** Solve the Josephus Puzzle Using a Queue. Josephus wwould sit at index n-1 in the return array. Is the last person eliminated. @param n is the number of people @param m is the m-th person to kill, m=2 means kill every other person @return a pointer to an array with n elements, the people eliminated in order from first to last */ int *josephus(int n, int m);

#endif

The expected tests and output for the code:

Test 1 -

% ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 1 newQueue: PASSED

Test 2 - % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 2 enqueue: PASSED

Test 03 - % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 3 front: PASSED

Test 04 - % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 4 isEmpty: PASSED

Test 05 - % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 5 dequeue: PASSED

Test 06 - % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 6 Random Values: PASSED

Test 00 - % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 0 Running ALL Tests newQueue: PASSED enqueue: PASSED front: PASSED isEmpty: PASSED dequeue: PASSED Random Values: PASSED