Topic link: Force buckle

Catalog

Link to topic: buckle

1. Title

2. Title Analysis

  3. Ideas

  3. java code

1. Title

Implement a queue with two stacks. The queue is declared as follows. Implement its two functions appendTail and deleteHead to insert integers at the end of the queue and delete integers at the head of the queue, respectively. (deleteHead if there are no elements in the queue   Operation Return-1)

Example 1:

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 to   appendTail, deleteHead   10000   Secondary call

2. Title Analysis

The first time I brushed the question, the title did not understand, so first explain what the title means.  

["CQueue","appendTail","deleteHead","deleteHead"] 
Indicates each action to be performed

[[],[3],[],[]]
Indicates the parameters required for each operation
CQueue represents the creation of a new CQueue object, corresponding to the required parameter [], that is, no parameters are required for this operation.
AppendTail means an appendTail() operation is performed, corresponding to 3 elements to be operated on.
A deleteHead indicates that a deleteHead operation is performed and the corresponding required parameter is [], that is, no parameters are required for this operation.
A deleteHead indicates that a deleteHead operation is performed and the corresponding required parameter is [], that is, no parameters are required for this operation.

Output: [null,null,3,-1]   Represents the result returned after an operation has been performed

1. Create a queue with a return value of null

2. Push 3 on the stack and return null

3. Delete the element at the bottom of the stack, which is the advanced element in the message queue, so it is deleteHead, which returns the value of the element, so it is 3

4. Continue deleting elements at the bottom of the stack, but there are no elements, so return -1

  3. Ideas

The stack is characterized by FIFO, the queue is characterized by FIFO, the title requires two stacks to achieve a queue

So the key to this question is to invert the data in stack A, that is, the bottom element becomes the top element

1. Stack A receives the input data, Stack B receives the output, and the first data will be placed at the bottom of Stack A, as shown in Fig.

If an outbound operation is performed, the data from stack A is pushed into stack B, and then stack B is executed.

2. When executing the queue operation, first judge if stack B is empty, if not, directly execute stack operation on stack B. If it is empty, then judge if stack A is empty. If there is data in A, then press all data in A into stack B, then execute stack operation on stack B. If there is no data in A, return 1 directly.

  3. java code

Stacked

class CQueue {
    Stack<Integer> sA;
    Stack<Integer> sB;

    public CQueue() {
        sA=new Stack<>();
        sB=new Stack<>();
    }
    
    public void appendTail(int value) {
        //Add data directly to Stack A
        sA.push(value);
    }
    
    public int deleteHead() {
        //First check to see if stack B is empty
        if(sB.isEmpty()){
            //sB is empty to see if sA is empty
            if(sA.isEmpty()){
                return -1;
            }
            else{
                //Place all values of s1 in s2
                while(!(sA.isEmpty())){
                    sB.push(sA.pop());
                }
                return sB.pop();
            }
        }
        else{
            return sB.pop();
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

With two arrays

class CQueue {
    LinkedList<Integer> A, B;
    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }
    public void appendTail(int value) {
        A.addLast(value);
    }
    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        if(A.isEmpty()) return -1;
        while(!A.isEmpty())
            B.addLast(A.removeLast());
        return B.removeLast();
    }
}