Here’s a new idea for implementing the sequence class from Section 4.5. Instead of the items being stored on a linked list, they will be stored using two stacks as private member variables with the following:

1. The bottom of the first stack is the beginning of the sequence.

2. The elements of the sequence continue up to the top of the first stack.

3. The next element of the sequence is then the top of the second stack.

4. And the elements of the sequence then continue down to the bottom of the second sequence (which is the end of the sequence).

5. If there is a current element, then that element is at the top of the first stack. Don’t change any of the specifications for any of the public methods. All of the public methods should take constant time, with one exception. Which one takes linear time?