Jianzhi offer 09 realizes queue with two stacks

At first, I didn't understand the meaning of the question , Only when I saw the vernacular explanation in the explanation of the question did I understand .

You should inspect the stack （ First in, then out ）、 queue （ fifo ） Characteristics of .

here 2 Stack , My understanding is , The first is the function stack , The second is the auxiliary stack , According to the characteristics of stack in and out , Use two stacks to realize the function of queue .

Personal summary is , First, press the number into the first stack , here Stack 1 It's empty , Stack 2 It's empty , For example, enter in turn 1、3、5 Three numbers , Now the stack 1、 Stack 2 As shown in the figure

If you want to delete the header element at this time , That is, the first number to enter ：1, Then you need to stack 1 Three elements of , Pop up one by one （pop）, Push to stack 2（push） in , Now the stack 1 It's empty , Stack 2 Not empty , According to the principle of first in, then out , Stack 2 As shown in the figure

            

And then put 1 eject （pop）, In this way, you can delete the header element

therefore , If it is an implementation to add elements , Then all elements are pushed onto the stack first 1

Then the stack should be considered when deleting elements 2 The situation of , Because you want to delete the header element , Must be stack 1 The element pops up first , Then push it into the stack 2, Now the stack 2 Not empty , Note that all elements are on the stack 2, The deletion operation can be directly executed in sequence , There's no need to think otherwise .

According to the meaning , If the stack 1、2 All empty. , Delete operation returns -1

Consider stack 1、 Stack 2 The situation of

①、 Stack 2 It's empty 、 Stack 1 Not empty

This situation is called stack 1 Press in new elements , Now the stack 1、 Stack 2 As shown in the figure

Then the header element becomes 7, To delete 7, First, put the stack 2 Element pop-up push stack 1, Then put the stack 1 Element pop-up push stack 2, that 7 It's on the stack 2 At the top of the , You can delete .

Stack 2 Elements pop up and push onto the stack in turn 1：

Stack 1 Elements pop up and push onto the stack in turn 2：

②、 Stack 1 It's empty 、 Stack 2 Not empty

Pop up the stack directly 2 Top element of stack , Delete it

So far, the solution of personal thinking is over , Write the code according to the idea

class CQueue {
    
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        //  Stack 2 It's empty 
        if (stack2.isEmpty()) {
            // Stack 2 It's empty 、 Stack 1 Not empty 
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        // Stack 2 empty 、 Stack 1 empty 
        if (stack2.isEmpty()) {
            return -1;
        } else { // Stack 2 Not empty 
            return stack2.pop();
        }
    }
}

isEmpty() Determine whether it is null , If the stack is empty , Then return to true, If the stack contains elements , Then return to false