Реализация стека с функциями getMiddle и getAt

Question

Мне нужно создать структуру данных, действующую как стек (LIFO) с этими функциями: init (), pu sh (Object), pop (), getMiddle (), getAt (k). Все функции, кроме getAt (), должны иметь сложность O (1) и getAt (k) со сложностью времени O (log (k)). Сложность пространства должна быть O (n)

Проблема заключается в функции getAt (k), когда k - это индекс k-го вставленного (в соответствии с порядком вставки) элемента в стеке. Я решил go с DoublyLinkedList, потому что тогда я смогу переместить указатель на средний элемент. Я также делюсь кодом. Если у кого-то есть какие-либо предложения о том, как я могу получить сложность O (k) или даже решение.

class Node {

    Node prev;
    Node next;
    Object data;
    int order; //index of inserted element

    Node(Object data, int order) {
        prev = null;
        next = null;
        this.data = data;
        this.order = order;
    }
}

public class LikeStack {

    Node head;
    Node mid;
    int size;

    //constructor
    public LikeStack() {
        this.size = 0;
        this.head = null;
        this.mid = null;
    }

    //push object to the stack and move the pointer to the middle of the stack if needed
    public void push(Object o) {
        size++;
        Node toPush = new Node(o, size);
        toPush.prev = null;
        toPush.next = head;
        if (size == 1) {
            mid = toPush;
        } else {
            head.prev = toPush;
            {
                if (size % 2 == 1) {
                    mid = mid.prev;
                }
            }
        }
        head = toPush;
    }

    //pop object from the stack and move the pointer to the middle of the stack if needed
    public Object pop() throws Exception {
        if(size<=0)
        {
            throw new Exception("The stack is empty");
        }
        size--;
        Object temp = head.data;
        head=head.next;
        if(head!=null)
        {
            head.prev=null;
        }
        if(size%2==1)
        {
            mid=mid.next;
        }
        return temp;
    }

    //just returning the middle element
    public Object getMiddle(){
        return mid.data;
    }        

Answer 1

• Сначала необходимо сохранить индексную переменную, скажем, от index до 0.
• Когда вы выполните push(), вы добавите элемент на карту как:

   void push(int value){
      // your code
      map.put(index++,your_node);
   }

• В вашем pop() вы бы сделали

int pop(){
   // your code
   your_node.prev.next = null;
   map.remove(index--);
}

• Итак, получение среднего элемента будет просто поиском на карте

int middle(){
   // your code
   return map.get(index / 2).value;
}

• Получение значения в k будет аналогично приведенному выше:

int getKthElement(int K){
   // your code
   return map.get(K-1).value; // If K is above index, you can throw an exception
}