session1-solutions.pdf

Double-Ended Sequence Operations

A dynamic array can implement a Sequence interface supporting worst-case O(1)-time indexing as
well as insertion and removal of items at the back of the array in amortized constant time. However,
insertion and deletion at the front of a dynamic array are not efficient as every entry must be shifted
to maintain the sequential order of entries, taking linear time.
On the other hand, a linked-list data structure can be made to support insertion and removal operations
at both ends in worst-case O(1) time (see PS1), but at the expense of linear-time indexing.
Show that we can have the best of both worlds: design a data structure to store a sequence of items
that supports worst-case O(1)-time index lookup, as well as amortized O(1)-time insertion and
removal at both ends. Your data structure should use O(n) space to store n items.
可以用两个栈或者动态数组来解决，详见pdf。