Java two-stack push with cycles, rest -- just delegation.


  • 0
    E
    import java.util.Stack;
    
    class MyQueue {
        private Stack<Integer> queue = new Stack<>();
        private Stack<Integer> swap = new Stack<>();
    
        public void push(int x) {
            while (!queue.empty())
            {
                swap.push(queue.pop());
            }
            queue.push(x);
            while (!swap.empty())
            {
                queue.push(swap.pop());
            }
        }
    
        // Removes the element from in front of queue.
        public void pop() {
            queue.pop();
        }
    
        // Get the front element.
        public int peek() {
            return queue.peek();
        }
    
        // Return whether the queue is empty.
        public boolean empty() {
            return queue.empty();
        }
    }

  • 0
    G

    I think it is possible for your code to move around the elements for so many times, that the runtime in worst case can be exponential (Consider One Million times of pushing, it takes 1000000! of time).


  • 0
    E

    Ok. I already know a better solution. What is your proposal?


  • 0
    G

    This question appeared in a past final exam of my college. Basic idea is that pushing a stack into another stack makes it a queue


  • 0
    E

    Yes, and as you can see there is a stack that will give the values out in the order of queue. The problem here is putting the new value to the bottom of the stack. And repacking every time is a bad idea actually.


  • 0
    G

    So why bother repacking? If you have already make one queue that still have elements, the pop or peek are just using the queue. Repacking is only required when the "queue" is out of elements.


  • 0
    E

    Yeah, the simplest solution was put new element underneath. That's why repacking.

    Now I fill outgoing queue only when needed. And do it once only when it has been emptied.

    import java.util.Stack;
    
    class MyQueue {
        private Stack<Integer> out = new Stack<>();
        private Stack<Integer> in = new Stack<>();
    
        public void push(int x) {
            in.push(x);
        }
    
        // Removes the element from in front of out.
        public void pop() {
            peek();
            out.pop();
        }
    
        // Get the front element.
        public int peek() {
            if (out.empty()) {
                while (!in.empty()) {
                    out.push(in.pop());
                }
            }
            return out.peek();
        }
    
        // Return whether the out is empty.
        public boolean empty() {
            return out.empty() && in.empty();
        }
    }
    

  • -1
    Z

    one Stack is enough.

    import java.util.Stack;
    class MyQueue {
    Stack<Integer> s = new Stack<>();
    private Integer first = null;
    // Push element x to the back of queue.
    public void push(int x) {
        if(first == null){
            first = x;
        }
        s.push(x);
    }
    
    // Removes the element from in front of queue.
    public void pop() {
        List<Integer> temp = new ArrayList<>();
        Integer last = null;
        first = null;
        do{
            last = s.pop();
            if(s.isEmpty()){
                break;
            }
            first = last;
            temp.add(last);
        }while (true);
        for(int i = temp.size()-1;i>=0;i--){
            s.push(temp.get(i));
        }
    }
    
    // Get the front element.
    public int peek() {
        return first;
    }
    
    // Return whether the queue is empty.
    public boolean empty() {
        return s.isEmpty();
    }
    }

  • 0
    E

    Yes, I see. But let me give some critics about your solution.

    1. But task says about using stacks and not lists.
    2. Your code is doing the same thing as stack would have done: temp.add() and then reading backwards is exactly the same as push+pop with stack. This solution is even more cryptic.
    3. Your code creates ArrayList without initial size which is bad practice. You should have used LinkedList instead. But on this task you should not use lists at all. Better using two stacks. Anyway you implement your own stack behaviour.
    4. In the end variable first is redundant.
    5. There is a better solution than both our solutions: look for amortized among solution shares.

  • 0
    E

    Also have a look to my solution in the sibling thread -- this is what I am talking about. Think of pushing 1M items into your queue.


  • 0
    Z

    Yes, you are very reasonable, my Solution is indeed contrary to the original intention of the problem.
    your solution in the sibling thread is better.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.