TransWikia.com

Does this method creates extra space?

Stack Overflow Asked on December 5, 2021

I’m trying to reverse a stack without creating extra space.

This is what I came about:

{
                
    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);}     
}

If this method creates extra space, how can I fix it?

Another question is, how can I modify so that the code run in O(n)?

One Answer

You could always just make your own subclass of Vector and add a toggle method that determines whether the pop method to retrieves from either the front or the back... Presumably that would be O(1).

Answered by D.L. on December 5, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP