Contents:

• Overview
• Problems to be Submitted

Topic(s): Organization and Implementation of Sequence Data Structures, including Vectors, Linked Lists, Stacks, and Queues
Related Reading: Class notes and Chapter 4

1.   (5 points)

   Following is a sequence of stack operations, using the List interface from Shaffer's text.

           L2.append(10);
           L2.append(20);
           L2.insert(39);
           L2.append(15);
           L2.moveToStart();
           L2.next();
           L2.insert(12);
   

   1. Assuming all instructions execute in the given sequence, draw four diagrams, showing the contents of the list, after executing the first, third, fifth, and seventh instructions. In each diagram, include the values of all elements in the list, and an indicator -- such as a vertical bar or a pointer -- denoting the "current" element in the list (i.e. the element whose value would be returned by the getValue() method).
   2. Give the C++ code that would implement the same sequence of additions and modifications to a list, using the C++ list class.
2.   (4 points)

   Similar to problem #1, following is a sequence of stack operations, using the Stack interface from Shaffer's text.

           S1.push (12);
           S1.push (-5);
           Int t1 = S1.pop();
           S1.push (-8);
           S1.push (20);
           Int t2 = S1.topValue();
           S1.pop ();
           S1.push (4);
   

   1. Assuming all instructions execute in the given sequence, draw four diagrams, showing the contents of the stack, after executing the second, fourth, sixth, and eighth instructions. In each diagram, include the values of all elements in the stack, and a pointer denoting the current "top" of the stack.
   2. What are the values of t1 and t2 after the code executes?
   3. Finally, give the C++ code that would implement the same sequence of additions and modifications to a stack, using the C++ stack class.
3.   (4 points)

   Similar to problem #1, following is a sequence of queue operations, using the Queue interface from Shaffer's text.

           Q1.enqueue (9);
           Q1.enqueue (2);
           Int t1 = Q1.frontValue ();
           Q1.enqueue (-6);
           Q1.dequeue ();
           Q1.enqueue (14);
           Int t2 = Q1.dequeue ();
           Q1.enqueue (3);
   

   1. Assuming all instructions execute in the given sequence, draw four diagrams, showing the contents of the queue, after executing the second, fourth, sixth, and eighth instructions. In each diagram, include the values of all elements in the queue, and two pointers denoting the current "front" and "rear" of the queue.
   2. What are the values of t1 and t2 after the code executes?
   3. Finally, give the C++ code that would implement the same sequence of additions and modifications to a queue, using the C++ queue class.
4.   (4 points)

   In the text, Shaffer discusses two implementations of the Queue ADT, with either an array or a linked list. The linked list implementation is straightforward and efficient, but in order to achieve efficiency in an array implementation, it is necessary to implement it as a circular array. In such a case, separate "front" and "rear" indices are maintained, that are incremented and move circularly around the array, such that the next index (after an enqueue or dequeue operation, which increments the front or rear indices, respectively) is computed as follows:

         i = (i + 1) % capacity;
   

   where 'capacity' is the allocated size of the array (and the maximum number of elements that can be stored in the queue).

   Assume you've got such a circular array, with a capacity of 10. Imagine that the even integer numbers from 2 to 24 are added to and removed from the queue such that numbers are added in groups of three, followed by one nmber being removed afterwards. For example, 2, 4, and 6 would be added, then one number removed, followed by the next three numbers being added, then one removed, and so on.

   Assuming that the circular array is initially empty, with "front" and "rear" both point to index 0, show the state of the circular array (i.e. the internal state of the queue) at the end, indicating in each of the 10 array positions the number it contains (or nothing, if empty) and the final position of the "front" and "rear" pointers.

5.   (8 points)

   Exercise #4.19, part (a), from Section 4.6 of the Shaffer text (p. 147).

   Using a stack, you can "match" left and right parentheses by adding to the stack when you encounter a left parentheses, and removing from the stack when you find a right parentheses. You may use the C++ stack, or Shaffer's Stack, whichever you prefer.

   You should implement your solution as a function that takes a string input argument and returns a bool result. Assume that the string can be any series of characters -- such as an equation like 3 * (x + 4 / (9 - y)) -- and your method should ignore all characters expect the left, '(', and right, ')', parentheses.

   Provide a main() function that includes a number of test cases. Make sure your code works for a variety of positive examples (those with an equal number of left and right parens) and negative examples (those with mismatching numbers of left and right parens -- be sure to test cases with both extra left parens and extra right parens).