带getMiddle与getAt函数的LIFO栈实现方案问询

First, let's tackle the core problem: your current doubly linked list setup gives you O(1) push/pop/getMiddle operations, but accessing a node by its insertion index (k) would take O(n) time if we traverse directly. To hit the O(log k) requirement (and even exceed it with O(1) performance), we can add a hash map to map insertion order indices directly to their corresponding nodes. This fits your O(n) space constraint and keeps all other operations strictly O(1).

Why This Works #

• Every node in your stack has a unique order value that exactly matches its insertion index (you increment size and assign it as order during each push).
• A hash map lets us look up the node for any valid k in O(1) time—better than the required O(log k).
• Updating the map during push/pop is trivial and adds no extra time complexity to these core operations.

Modified Complete Code #

import java.util.HashMap;

class Node {
    Node prev;
    Node next;
    Object data;
    int order; // 1-based index of the 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;
    HashMap<Integer, Node> orderToNodeMap; // Maps insertion order to its node

    // Constructor
    public LikeStack() {
        this.size = 0;
        this.head = null;
        this.mid = null;
        this.orderToNodeMap = new HashMap<>();
    }

    // Push object to the stack and maintain pointers/map
    public void push(Object o) {
        size++;
        Node toPush = new Node(o, size);
        toPush.prev = null;
        toPush.next = head;

        // Add new node to the hash map
        orderToNodeMap.put(toPush.order, toPush);

        if (size == 1) {
            mid = toPush;
        } else {
            head.prev = toPush;
            if (size % 2 == 1) {
                mid = mid.prev;
            }
        }
        head = toPush;
    }

    // Pop object from the stack and maintain pointers/map
    public Object pop() throws Exception {
        if (size <= 0) {
            throw new Exception("The stack is empty");
        }
        Node poppedNode = head;
        Object temp = poppedNode.data;
        head = head.next;

        // Remove popped node from the hash map
        orderToNodeMap.remove(poppedNode.order);

        if (head != null) {
            head.prev = null;
        }
        size--;
        if (size % 2 == 1) {
            mid = mid.next;
        }
        return temp;
    }

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

    // Get element by insertion order index k (1-based)
    public Object getAt(int k) throws Exception {
        if (k < 1 || k > size) {
            throw new Exception("Invalid index k: must be between 1 and " + size);
        }
        Node targetNode = orderToNodeMap.get(k);
        return targetNode.data;
    }
}

Alternative: Skip List for Strict O(log k) (If Hash Maps Are Restricted) #

If you can't use hash maps and must stick to linked list structures, you can enhance each node with skip pointers (like a skip list) to enable O(log k) lookups. However, note this makes push take O(log n) amortized time instead of strict O(1), which violates your original push/pop time requirement. For completeness, here's the core idea:

• Add a list of skip pointers to each Node, where skip[i] points to the node 2^i positions toward the stack bottom.
• During push, build these skip pointers by chaining from the previous head's skip pointers.
• For getAt(k), calculate steps needed from the head and use skip pointers to jump in powers of two, reducing steps to O(log k).

But since your problem requires push/pop to stay O(1), the hash map approach is the clear optimal solution.

内容的提问来源于stack exchange，提问作者sirkol123