问题

{
    static Stack side = new Stack();
    static Object top = new Object();
    static Object bottom = new Object();
    static Stack st = new Stack();

    public static void main(String[] args) {
        st.push(1);
        st.push(2);
        st.push(3);
        st.push(4);
        st.push(5);
        st.push(6);
        st.push(7);
        st.push(8);
        st.push(9);
        reverse(st);
    }

    static void reverse(Stack st) {
        top = st.peek();
        st.pop();
        transfer(st, side, bottom);
        addToBottom(st, top);
        bottom = st.peek();
        transfer(side, st, bottom);
        if (st.peek() != top) reverse(st);
    }

    static void transfer(Stack st, Stack side, Object bottom) {
        while (!st.empty()) {
            if (st.peek() != bottom) {
                side.push(st.peek());
                st.pop();
            } else break;
        }
    }
    
    static void addToBottom(Stack st, Object top) {
        if (st.empty()) {
            st.push(top);
            return;
        }
        
        Object temp = st.peek();
        st.pop();
        addToBottom(st, top);
        st.push(temp);
    }
}

To reverse the stack without creating extra space, the code has been modified to use a recursive approach in the addToBottom function. This approach pushes the top element to the bottom of the stack by recursively popping the elements from the stack, adding the top element when the stack becomes empty, and then pushing the previously popped elements back onto the stack. This ensures the reversal without requiring additional space.

As for optimizing the code to run in O(n) time complexity, the recursive approach already achieves this. The addToBottom function processes each element of the stack exactly once, leading to a linear time complexity of O(n), where n is the number of elements in the stack.

{
                
    static Stack side = new Stack();
    static Object top = new Object();
    static Object bottom=new Object();
    static Stack st = new Stack();

    public static void main(String[] args) {
        st.push(1);
        st.push(2);
        st.push(3);
        st.push(4);
        st.push(5);
        st.push(6);
        st.push(7);
        st.push(8);
        st.push(9);
        reverse(st);
    }
    
  
    
    static void reverse(Stack st){
        top = st.peek();
        st.pop();
        transfer(st,side,bottom);
        addToButtom(st, top);
        bottom=st.peek();
        transfer(side,st,bottom);
        if (st.peek()!=top)reverse(st);
    }
    static void transfer(Stack st, Stack side, Object bottom){
        while (!st.empty()) {
            if (st.peek()!=bottom) {
                side.push(st.peek());
                st.pop();
            }else break;
        }
     }
    static void addToButtom(Stack st, Object top){st.push(top);}     
}

答案1

得分: 0

你可以简单地创建Vector的子类，然后添加一个切换方法，用于决定pop方法是从前面还是后面取出……可以预期这将是O(1)的。