设计O(1)数据结构

Question

////////////////////////////////////////////////////////////////
// Implement a container that have the following methods:
// Java:
//     public class Container<E>
//     {
//         // data memebers
//         ...
//         public Container();
//             // constructor
//             // Complexity: Constant
//
//         public int size();
//              // return the total number of elements in the container
//              // Complexity: Constant
//
//         public E get(int index);
//              // get an element from the container by its index
//              // Complexity: Constant
//
//         public void set(int index, E element);
//              // set an element in the container by its index. index >= 0 && index < size()
//              // Complexity: Constant
//
//         public void add_front (E element);
//              // add a new element to the front of the container i.e. its index is 0
//              // Complexity: Constant (amortized time)
//
//         public void remove_front ();
//              // remove the element at the front of the container
//              // Complexity: Constant
//
//         public void add_back (E element);
//              // add a new element to the back of the container i.e. its index is size()
//              // Complexity: Constant (amortized time)
//
//         public void remove_back ();
//              // remove the element at the back of the container
//              // Complexity: Constant
//     }
//
// Examples:
//   at beginning   => []

//   add_front(0)   => [0]
//   add_front(-1)  => [-1, 0]
//   add_back(1)    => [-1, 0, 1]
//   add_back(2)    => [-1, 0, 1, 2]
//   get(0)         => -1
//   get(3)         => 2
//   set(3, 8)      => [-1, 0, 1, 8]
//   remove_front() => [0, 1, 8]
//   remove_back()  => [0, 1]
////////////////////////////////////////////////////////////////

null

low--;
storage.put(low, element);

高++；storage.put（high,element）；

低++；

高--；

Answer 1

因为add_front()和add_back()的复杂度需要保持不变，而且remove_front()和remove(back)之后不需要内存效率，所以可以使用数组！它们比哈希表简单，在运行时复杂性中没有“具有高概率”。

您可以从大小为3的数组开始，将第一个元素放在中间，这样就有空间容纳一个add_front和一个add_back。然后当它溢出时，只需移动大小为6的数组中间的元素。通常，在每次溢出时，数组大小会增加一倍。

显然，您需要通过数据结构中的一些整数变量来跟踪数组的开始和结束位置及其当前容量。