One brush 314 sword finger offer 09 Implement queue (E) with two stacks

 subject ：
 Use two stacks to implement a queue . The declaration of the queue is as follows , Please implement its two functions  appendTail  and  deleteHead ,
 The functions of inserting integers at the end of the queue and deleting integers at the head of the queue are respectively completed .
( If there are no elements in the queue ,deleteHead  Operation return  -1 )
-----------------
 Example ：
 Input ：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
 Output ：[null,null,3,-1]
 Example  2：

 Input ：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
 Output ：[null,-1,null,null,5,2]

 Tips ：
1 <= values <= 10000
 At most  appendTail、deleteHead  Conduct  10000  Secondary call 
----------------
 Ideas ：
 Their thinking ：
 The stack cannot implement the queue function ：  Stack bottom element （ Corresponding to the first element of the team ） Can't delete directly , All the elements above need to be out of the stack .
 Double stack can realize the reverse order of the list ：  There is a stack with three elements  A = [1,2,3] Empty stack  B = []
 If the loop executes  A  Element out of the stack and added into the stack  B , Until the stack  A  It's empty , be  A = []B = [3,2,1],
 namely   Stack  B  Element implementation stack  A  Elements in reverse order  .
 Utilization stack  B  Delete team leader element ：  In reverse order ,B  Executing out of the stack is equivalent to deleting  A  At the bottom of the stack , That is, the corresponding team head element .

 Function design ：
 The title only requires the realization of   To join a party appendTail()  and   Delete team leader deleteHead()  The normal operation of the two functions ,
 So we can design the stack  A  Used to join the end of the queue , Stack  B  Used to reverse the order of elements , So as to delete the team head element .

 To join a party  appendTail() function ：  The digital  val  Join the stack  A  that will do .
 Delete team leader deleteHead() function ：  There are three situations .
 Stack  B  Not empty ： B There are still elements in reverse order , So go straight back  B  Top element of .
 otherwise , When  A  It's empty ：  That is, both stacks are empty , Element free , Therefore return  -1.
 otherwise ：  Stack  A  All elements are transferred to the stack  B  in , Implement elements in reverse order , And return to the stack  B  Top element of .
-----------
 Complexity analysis ：
 Because of the special problem , The following analysis only meets the requirements of adding  N  And delete  N  Elements , That is, the stack is empty in the initial and end states .

 Time complexity ： appendTail() Function is  O(1);deleteHead() 
 Function in  N  A total of... Needs to be completed in the deletion of the first element of the team  N  The reverse order of the elements .
 Spatial complexity  O(N)：  In the worst case , Stack  A  and  B  Keep together N Elements .
---------------------

class CQueue {
    //A  Used to add  B  Used to delete  B yes A In reverse order 
    LinkedList<Integer> A, B;// Define two stacks 
    public CQueue() {
    // initialization 
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }
    public void appendTail(int value) {
    //A Add an element at the end of the 
        A.addLast(value);
    }
    public int deleteHead() {
    
        if (!B.isEmpty()) return B.removeLast();// Special judgement 
        if (A.isEmpty()) return -1;// Special judgement 
        while (!A.isEmpty()) {
    //B It's empty  A Not empty ,  First, let B get A The elements of 
            B.addLast(A.removeLast());
        }
        return B.removeLast();
    }
}
 notes ： return B.removeLast();  To return as a value 
/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */

LC