Description

Question:

Problem 1. Arrays and Linked Lists: Provide solutions to the following:

(a) 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) Download the List.zip file then modify the List.cpp file to implement details for the function called intersection(). Recall that the intersection of two sets consists of only those elements in the first set that are also in the second set. We will use this definition for our two lists. The prototype for this function is as follows:

template <class Object> 

list<Object> intersection(list<Object> L1, list<Object> L2);
for (itr1 = L1.begin(); itr1 != L1.end(); ++itr1) 
{
for (itr2 = L2.begin(); itr2 != L2.end(); ++itr2) 
{ 2
336 706 130 775 919 100 224 352 852 482 
List 2: 
830 895 101 224 755 320 776 728 592 242 
List 3: 
706 562 242 336 592 830 392 100 811 755 
The intersection of L1 and L1: 
336 706 130 775 919 100 224 352 852 482 
The intersection of L1 and L2: 
224 
The intersection of L2 and L1: 
224 
The intersection of L1 and L3: 
336 706 100 
The intersection of L2 and L3: 
830 755 592 242 
** Press any key to continue **
       empty = 1 3 
       max size = 35 
       current size = 0 
       next element = [None]
Queue properties: 
       empty = 0 
       max size = 35 
       current size = 6 
       next element = not
Queue elements: 
       not 
       stop 
       signs 
       they 
       are 
       guidelines
Queue properties: 
       empty = 1 
       max size = 35 
       current size = 0 
       next element = [None]
Queue elements: 
       The queue is empty!
Queue properties: 
       empty = 0 
       max size = 35 
       current size = 15 
       next element = Remember
Queue elements: 
       Remember 
       that 
       life 
       is 
       a 
       succession 
       of 
       lessons 
       which 
       must 
       be 
       lived 
       to 
       be 
       understood

The implementation will use the C++ Standard Template Library list implementation. The print() function provides an example on how to use an iterator for a given list. The result of the intersection() function will be the elements in the intersection of the two lists. If there are no common elements between the two given lists, then function will return NULL.

Hint: Except for using the merge() function, you may implement this function any way you like, but here are a few suggestion:

1. Create two loops, one embedded within the other.

Walk through the first list in the first loop in the outer loop using an iterator:

typename list<Object>::iterator itr1; 

Walk through the second list in the second loop using another iterator:

typename list<Object>::iterator itr2; 

2. Within the second loop, check if the value of itr1 equal itr2. Remember that the iterators are pointer. If they equal, push one of the iterators onto the resultList:

resultList.push_back(*itr1);

Output: After the function is implemented the output of the program will appear as follows. (Note: the order of the elements from the results of intersection and union does not matter as long as all of the elements are listed)

List 1: 

Problem 2. Stacks and Queues: Provide solutions to the following:

(a) When considering the push() and pop() operations for a stack, briefly describe how a compiler program could use a stack to implement delimiter matching. For example, matching delimiter strings could be: "{", "}", "(", ")", and "/*", and "*/".

(b) Download the Queue.zip file, which provides a simple framework for a queue data structure. Implement the details for the operations for this basic queue data structure that will use an array of elements of type string. We will not use templates for this implementation. Provide the implementations details for the following class methods (i.e. operations): initialize(), empty(), enqueue(string element), dequeue(), and nextElement(). Descriptions of most these methods are provided in the source code. The code in the Driver.cpp file will remain the same.

Hint: Again, you only need to modify the areas in the Queue.h file by adding the necessary code to implement the TODO areas as noted in the comments. The prototype for the functions and everything else in the program must remain unchanged. You must use the function signature for your implementation. Remember that the queue variable is an array.

Output: The output for the program after the functions are implemented should appear as follows:

Queue properties: