> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-08-2022-232.md).

# 02/08/2022 232

Method:

Use two stacks: one is for stackIn and one is for stackOut. When you push element, just push into the stackIn. When you pop, first check if the stackOut is empty. If it is, pop from stackIn and push them into stackOut and finally pop from stackOut. Do the same way when you peek. For checking if the queue is empty, we should check if stackin is empty and stackOut is empty.

push Time O(1) Space O(n)

pop Time Amortized O(1) worst case O(n) Space O(1)

peek Time Amortized O(1) worst case O(n) Space O(1)

empty Time O(1) Space O(1)

```
class MyQueue { 
    Private Stack stackIn; Private Stack stackOut; // 
    Private int front; 
    public MyQueue() { 
    stackIn = new Stack<>(); 
    stackOut = new Stack<>(); }
    
    public void push(int x) {
        //Time O(1) Space O(n) We need additional memory to store the queue elements
       // if(stackIn.isEmpty()) front = x;
        stackIn.push(x);          
    }
    
    public int pop() {
        //Time Amortized O(1), worst case O(n); Space O(1)
        if(stackOut.isEmpty()){
            while(!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.pop();           
    }
    
    public int peek() {
        //Time Amortized O(1), worst case O(n); Space O(1)
        if(stackOut.isEmpty()){
            while(!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.peek(); 
        
    }
    
    public boolean empty() {
        //Time O(1) Space O(1)
        return stackOut.empty() && stackIn.empty();
    }
```

}

/\*\*

* 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(); \*/

Method 2:

private in front: peek method and push method

class MyQueue { private Stack stackIn; private Stack stackOut; private int front;

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

public void push(int x) {
    //Time O(1) Space O(n) We need additional memory to store the queue elements
    if(stackIn.isEmpty()) front = x;
    stackIn.push(x);          
}

public int pop() {
    //Time Amortized O(1), worst case O(n); Space O(1)
    if(stackOut.isEmpty()){
        while(!stackIn.isEmpty()){
            stackOut.push(stackIn.pop());
        }
    }
    return stackOut.pop();           
}

public int peek() {
    //Time Amortized O(1), worst case O(n); Space O(1)
    if(!stackOut.isEmpty()){
       return stackOut.peek();
    }
    return front; 
    
}

public boolean empty() {
    //Time O(1) Space O(1)
    return stackOut.empty() && stackIn.empty();
}
```

}

/\*\*

* 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(); \*/