java - 使用 getMiddle 和 getAt 函数实现堆栈

问题描述

我需要使用以下函数创建类似于堆栈 (LIFO) 的数据结构：init()、push(Object)、pop()、getMiddle()、getAt(k)。除了 getAt() 之外的所有函数的复杂度都应该是 O(1)，而 getAt(k) 的时间复杂度应该是 O(log(k))。空间复杂度应该是 O(n)

问题是 getAt(k) 函数，当 k 是堆栈中第 k 个插入（根据插入顺序）元素的索引时。我决定使用 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;
    }

标签： javaalgorithmdata-structuresstacktime-complexity

首先是维护一个索引变量，比如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
}

java - 使用 getMiddle 和 getAt 函数实现堆栈

问题描述

解决方案

推荐阅读