QuestionQuestion

Transcribed TextTranscribed Text

Overview: For problems 2(a) and 2(b) of this assignment, you will need a C++ compiler. In order to receive credit, your programs must compile and run; and you must provide the actual source code file so that I can compile and run your programs (e.g. files ending in .cpp). The remaining problems for the assignment must be written up within a single Microsoft Word document. You must include your name and course number within all files that you submit, including source code files as a comment at the top of each file that you modify. Problem 1. [4 points] Arrays and Linked Lists: Provide solutions to the following: (a) [2 points] Write a brief summary explaining the differences between an array-based list and a linked list data structure. Describe the advantages and disadvantages of both types of lists in comparison to each other. (b) [2 points] Write a brief summary explaining what is meant by a singly linked list data structure and what is meant by a doubly linked list data structure. Mention the advantages and disadvantages of both types of lists in comparison to each other. Problem 2. [6 points] Stacks and Queues: Provide solutions to the following: (a) [3 points] Download the Stack.cpp file. Modify the to implement details for the helper function called reverse(). The prototype for this function is as follows: template <class Object> void reverseStack(stack<Object> myStack); This implementation will also use the C++ Standard Template Library. Specifically the stack API. The function takes a stack called myStack as input, and will reverse the items and store the results back into original stack. Hint: You only need to modify the areas of the code in the Stack.cpp file that are marked with TODO comments. Everything else in the program will remain that same. Use the stack API’s top(), pop(), and push() functions. Consider using a temporary stack to temporarily hold the results. The printStack() function provides an example on how to use a while-loop to walk through the stack using the pop() and top() operations on a temporary stack. For this problem, the while-loop can walk through the main stack by calling top() and pop() operations on the main stack. Within the loop add each item to the temporary stack by calling the push() operation. After the while-loop, set myStack equal to the temporary stack. 2 Output: The output for the program after the function is implemented should appear as follows: The contents of myStack: jumped fox brown quick the The reverse of myStack: the quick brown fox jumped ** Press any key to continue ** (b) [3 points] Download the file Queue.zip and modify the Queue.cpp file by implementing the details for the helper function called highPriority(), which will take the in a queue and an item as parameters, and will insert the item at the front of the queue. The remaining items in the queue will remain unchanged. The prototype for this function is as follows: template <class Object> void highPriority(queue<Object> &myQueue, Object item); Hint: Again, you only need to modify the areas in the Queue.cpp file by adding the necessary code to implement the TODO areas as noted in the comments. The prototype for the function and everything else in the program will remain unchanged. You must use the function signature for your implementation. Consider using another queue called results to hold the results as you are processing the items in the queue: queue<Object> results; Start by adding the passed in item to the results queue by calling results.push(item). Then walk through the queue, which is the passed in myQueue variable using a while loop like the one in the printQueue() function. Add the tmpItem to the queue by calling the push() function on the results queue. Before returning from function, set myQueue equal to the results queue: myQueue = results; Output: The output for the program after the function is implemented should appear as follows: Queue: 26 17 86 90 15 Queue after inserting 30: 3 30 26 17 86 90 15 Queue after inserting 85: 85 30 26 17 86 90 15 Queue after inserting 77: 77 85 30 26 17 86 90 15 ** Press any key to continue **

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

Problem 1. a)
The differences between array-based list and singly linked list data structures can be analyzed from at least the following three perspectives: memory space requirements for storing, access mode and the cost of the basic operations on their items.
The implementations based on arrays have two major drawbacks compared to the implementations based on linked lists: the fixed size (unless it is used the “vector” class) and the cost of basic operations like insertion and deletion (generally these have linear cost which is considered expensive in practice). Because of the fixed size it is needed to allocate the maximum required memory amount – regardless if the application uses it or not...

By purchasing this solution you'll be able to access the following files:
Queue.cpp, Stack.cpp and Solution.docx.

$36.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats