> 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-225.md).

# 02/08/2022 225

Method 1:

Using two queues. q2 is to store the new element pushed in. Then pop each element in q1 to q2 and swith them and make q1 has the same order with the stack implemented. 

push Time O(n) Space O(1)

pop Time O(1) Space O(1)

top Time O(1) Space O(1)

empty() Time O(1) Space O(1)

class MyStack { //using two queues private Queue q1; private Queue q2; //private int top;

```
public MyStack() {
    q1 = new LinkedList<>();
    q2 = new LinkedList<>();   
}

public void push(int x) {
//  time O(n) Space O(1)
    q2.offer(x);
    while(!q1.isEmpty()){
        q2.offer(q1.poll());
    }
    Queue<Integer> temp = q1;
    q1 = q2;
    q2 = temp;
}

public int pop() {
//Time O(1) Space O(1)
    return q1.poll();   
}

public int top() {
//Time O(1) Space O(1)
    return q1.peek();
    
}

public boolean empty() {
//Time O(1) Space O(1)
    return q1.isEmpty();
    
}
```

}

/\*\*

* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param\_2 = obj.pop();
* int param\_3 = obj.top();
* boolean param\_4 = obj.empty(); \*/

Method 2:

Use only one queque.  When you push element into this queue. While the queue's size is > 1, then remove the first and add it to the queue again and decrement the size.&#x20;

push Time O(n) Space O(1)

pop Time O(1) Space O(1)

top Time O(1) Space O(1)

empty() Time O(1) Space O(1)

class MyStack { //using one queue private Queue q1; //private int top;

```
public MyStack() {
    q1 = new LinkedList<>();  
}

public void push(int x) {
//  time O(n) Space O(1)
    q1.offer(x);
    int size = q1.size();
    while(size > 1){
        q1.offer(q1.poll());
        size--;
    }
}

public int pop() {
//Time O(1) Space O(1)
    return q1.poll();   
}

public int top() {
//Time O(1) Space O(1)
    return q1.peek();
    
}

public boolean empty() {
//Time O(1) Space O(1)
    return q1.isEmpty();
    
}
```

}

/\*\*

* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param\_2 = obj.pop();
* int param\_3 = obj.top();
* boolean param\_4 = obj.empty(); \*/