Transcribed 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 **
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...