Leetcode skimming: stack and queue 01 (realizing queue with stack)

Force button topic link

Use the stack to implement the following operations of the queue ：

push(x) – Put an element at the end of the queue .
pop() – Remove elements from the head of the queue .
peek() – Return the elements of the queue header .
empty() – Whether the return queue is empty .

Example :

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  //  return  1
queue.pop();   //  return  1
queue.empty(); //  return  false

explain :

• You can only use standard stack operations – It's just push to top, peek/pop from top, size, and is empty Operation is legal .
• The language you use may not support stacks . You can use list perhaps deque（ deque ） To simulate a stack , As long as it's a standard stack operation .
• Suppose all operations are valid （ for example , An empty queue will not call pop perhaps peek operation ）.

Ideas ： Just two stacks , One is used to receive data , One is used to output data , advanced Later Backward First out .
Directly enter the stack of data Connect data push 了 .
Getting out of the stack is similar to checking the stack , First, see whether the stack of data is empty , If it's empty , Push the stack of incoming data to the stack of outgoing data , advanced +（ Later + Backward ）+ First out = advanced First out
It's better to judge the space , Look at the two stacks. If they are empty, they are empty .

package com.programmercarl.stacks_queues;

import java.util.Stack;

/** * @ClassName MyQueue * @Descriotion TODO * @Author nitaotao * @Date 2022/6/29 10:57 * @Version 1.0 * 232.  Using stack to realize queue  * https://leetcode.cn/problems/implement-queue-using-stacks/ *  Ideas ： *  Stack , First in, then out  *  queue , fifo  *  Stack simulation queue , An element is pushed from the first stack , Push the second stack after coming out , be   advanced   Later   Backward   First out  ==  advanced   First out  **/
public class MyQueue {
    
    private Stack stackIn;
    private Stack stackOut;

    public MyQueue() {
    
        stackIn = new Stack();
        stackOut = new Stack();
    }

    /** *  Push an element  * * @param x */
    public void push(int x) {
    
        stackIn.push(x);
    }

    /** *  Back to top of stack element  * * @return */
    public int pop() {
    
        int lenIn = stackIn.size();
        int lenOut = stackOut.size();
        // The old area comes out first , New Area re-entry 
        if (lenOut > 0) {
    
            return (int) stackOut.pop();
        } else {
    
            // There are no elements in the old area , The new area enters the old area 
            while (lenIn > 0) {
    
                stackOut.push(stackIn.pop());
                lenIn--;
            }
            return (int) stackOut.pop();
        }
    }

    /** *  Look at the top of the stack elements  * * @return */
    public int peek() {
    
        int lenIn = stackIn.size();
        int lenOut = stackOut.size();
        // The old area comes out first , New Area re-entry 
        if (lenOut > 0) {
    
            return (int) stackOut.peek();
        } else {
    
            // There are no elements in the old area , The new area enters the old area 
            while (lenIn > 0) {
    
                stackOut.push(stackIn.pop());
                lenIn--;
            }
            return (int) stackOut.peek();
        }
    }

    /** *  Sentenced to empty  * * @return */
    public boolean empty() {
    
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}


/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */