package fundamentals.stack.lc232_implementqueueusingstacks;

import java.util.Stack;

/**
 * Stefan's amortized O(1) time solution
 * In my previous impl, either push() or pop() was O(N)
 * But now partial elements are in input and output moved only once.
 *
 * My 2AC
 */
public class MyQueue_O1Amortized {

    private Stack<Integer> input = new Stack<>();

    private Stack<Integer> output = new Stack<>();

    // Push element x to the back of queue.
    public void push(int x) {
        input.push(x);
    }

    // Removes the element from in front of queue.
    public void pop() {
        peek();
        if (!output.isEmpty()) output.pop();
    }

    // Get the front element.
    public int peek() {
        if (output.isEmpty())
            while (!input.isEmpty())
                output.push(input.pop());

        if (output.isEmpty()) return 0;
        return output.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return input.isEmpty() && output.isEmpty();
    }

}

@@ -409,52 +409,8 @@
 );%0A%0A
-    // Push element x to the back of queue.%0A
     
@@ -469,59 +469,8 @@
  %7D%0A%0A
-    // Removes the element from in front of queue.%0A
     
@@ -476,20 +476,19 @@
  public 
-void
+int
  pop() %7B
@@ -500,97 +500,93 @@
     
-peek();%0A        if (!output.isEmpty()) output.pop();%0A    %7D%0A%0A    // Get the front element.
+if (transfer()) %7B%0A            return output.pop();%0A        %7D%0A        return 0;%0A    %7D%0A
 %0A   
@@ -618,33 +618,29 @@
     if (
-output.isEmpty
+transfer
 ())
+ %7B
 %0A       
@@ -648,32 +648,29 @@
     
-while (!input.isEmpty())
+return output.peek();
 %0A   
@@ -674,24 +674,26 @@
         
+%7D%0A
         
 output.p
@@ -688,47 +688,88 @@
     
-output.push(input.pop());%0A%0A        if (
+return 0;%0A    %7D%0A%0A    public boolean empty() %7B%0A        return input.isEmpty() && 
 outp
@@ -784,125 +784,227 @@
 ty()
-) return 0
 ;%0A    
+%7D%0A%0A
     
-return output.peek();%0A    %7D%0A%0A    // Return whether the queue is empty.%0A    public boolean e
+// Transfer each element only once, so pop and peek in O(1) amortized%0A    // Return if transfer successfully (at least one element transferred)%0A    private boolean transfer() %7B%0A        if (output.isE
 mpty()
+)
  %7B%0A 
@@ -1002,39 +1002,44 @@
 ty()) %7B%0A        
-return 
+    while (!
 input.isEmpty() 
@@ -1029,36 +1029,118 @@
 !input.isEmpty()
- && 
+) %7B%0A                output.push(input.pop());%0A            %7D%0A        %7D%0A        return !
 output.isEmpty()

implement queue using stacks