Offer 09. Implement queues with two stacks

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

1, the title

Implement a queue with two stacks. Implement appendTail and deleteHead to insert an integer at the end of the queue and delete an integer at the head of the queue. (If there are no elements in the queue, the deleteHead operation returns -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]

Tip:

• 1 <= values <= 10000
• At most 10000 calls are made to appendTail and deleteHead

2, train of thought

Add appendTail() and delete first deleteHead(); add stack adds last element; delete stack removes first element.

• Add the queue appendTail() function: push the number val directly onto the add stack.

• DeleteHead () : there are two cases.

• First check whether the delete stack is empty:

  • If there is an element in the delete stack, you can return the top element of the delete stack.

  • If there is no element in the deleted stack, check whether the added stack has an element

    • If an element is added, push it off the stack into the delete stack, and pop the top element.
    • If no element is added, the column is empty and returns -1.

Less nonsense ~~~~~ on the code!

3, code,

Violent solution:

import java.util.Stack;
class CQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public CQueue(a) {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    
    public void appendTail(int value) {
        while(! stack1.isEmpty()){int num = stack1.pop().intValue();
            stack2.push(num);
        }
        stack2.push(value);
    }
    
    public int deleteHead(a) {
        while(! stack2.isEmpty()){int num = stack2.pop().intValue();
            stack1.push(num);
        }
        if(stack1.isEmpty())
            return -1;
        else
            returnstack1.pop().intValue(); }}/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); * /
Copy the code

Optimization:

I’m just going to take the time order n.

import java.util.Stack;
class CQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public CQueue(a) {
        stack1 = new Stack<Integer>();/ / remove the stack
        stack2 = new Stack<Integer>();/ / add a stack
    }
    
    public void appendTail(int value) {
        stack2.push(value);
    }
    
    public int deleteHead(a) {
        // Check whether the current delete stack is empty
        if(stack1.isEmpty()){// If it is null
            while(! stack2.isEmpty()){// Move all elements added to the stack to the delete stack
                stack1.push(stack2.pop());
            }
            // Check whether the delete stack is empty again
            if(stack1.isEmpty())
                return -1;
            else
                return stack1.pop();// Pops the top element of the stack
        }else{// If it is not empty
            return stack1.pop();// Pops the top element of the stack}}}/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); * /
Copy the code

4, summarize

The biggest difficulty of this topic is that the input and output given by the topic make many beginners very confused, do not know this topic is to carry out such code writing. According to the prompt of the question, we can clearly find that AC can be achieved quickly only by implementing the two functions given in the question.

❤️ from the LeetCode Basic Algorithms column subscribe to ❤️

The original intention of the director to write blog is very simple, I hope everyone in the process of learning less detours, learn more things, to their own help to leave your praise 👍 or pay attention to ➕ are the biggest support for me, your attention and praise to the director every day more power.

If you don’t understand one part of the article, you can reply to me in the comment section. Let’s discuss, learn and progress together!

Offer 09. Implement queue with two stacks.