The C++ Standard Template Library list implementation

computer science



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 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: 
The intersection of L2 and L1: 
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: 
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: 

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:


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

Related Questions in computer science category

The ready solutions purchased from Library are already used solutions. Please do not submit them directly as it may lead to plagiarism. Once paid, the solution file download link will be sent to your provided email. Please either use them for learning purpose or re-write them in your own language. In case if you haven't get the email, do let us know via chat support.