###### tags: `Leetcode` `easy` `design` `stack` `queue` `python` `c++`

# 232. Implement Queue using Stacks

## [題目連結:] https://leetcode.com/problems/implement-queue-using-stacks/

## 題目:
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue ```(push, peek, pop, and empty)```.

Implement the ```MyQueue``` class:

* ```void push(int x)``` Pushes element x to the back of the queue.
* ```int pop()``` Removes the element from the front of the queue and returns it.
* ```int peek()``` Returns the element at the front of the queue.
* ```boolean empty()``` Returns true if the queue is empty, false otherwise.

**Notes:**

* You must use **only** standard operations of a stack, which means only ```push to top, peek/pop from top, size, and is empty``` operations are valid.
* Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

**Follow-up:** Can you implement the queue such that each operation is **amortized O(1) time complexity**? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

**Example 1:**

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

## 解題想法:
兄弟題目: [225. Implement Stack using Queues](/obJJjYNSSsyf8HQ0CBscEg)
* 此題目要求用stack去實作queue
* stack: 先進後出
* queue: 先進先出
* 希望每個函式avg time:O(1)

* 想法:
* 用兩個stack
* stackMy
* stackTmp
* push: O(1)
* 一律正常加到**stackTmp**
* pop:
* worst case: O(n)
* avg case: O(1)
* 若stackMy為空
* 將stackTmp的元素全部逐一pop並append到stackMy
* return **stackMy.pop()**
* peek:
* 同pop()，只是回傳就好，不用刪除
* empty: O(1)
* 當兩個stack都為空才為True

* 示意圖:

## Python:

class MyQueue(object):

    def __init__(self):
        self.stackMy=[]
        self.stackTmp=[]

    def push(self, x): #O(1)
        """
        :type x: int
        :rtype: None
        """
        self.stackTmp.append(x)
        
    # worst case: O(n) 
    # avg case: O(1)
    def pop(self): 
        """
        :rtype: int
        """
        if not self.stackMy: #若stackMy空
            while self.stackTmp:
                item=self.stackTmp.pop()
                self.stackMy.append(item)
        return self.stackMy.pop()
    
    # worst case: O(n) 
    # avg case: O(1)
    def peek(self):
        """
        :rtype: int
        """
        if not self.stackMy: #若stackMy空
            while self.stackTmp:
                item=self.stackTmp.pop()
                self.stackMy.append(item)
        return self.stackMy[-1]

    def empty(self): #O(1)
        """
        :rtype: bool
        """
        #當兩個stack都為空才為True
        return not self.stackMy and not self.stackTmp

if __name__ == '__main__':
    obj = MyQueue()
    obj.push(1)
    obj.push(2)
    param_2 = obj.peek()
    param_3 = obj.pop()
    param_4 = obj.empty()
    print(param_2)
    print(param_3)
    print(param_4)

## C++:

#include<iostream>
#include<stack>
using namespace std;

class MyQueue {
public:
    MyQueue() {

    }

    void push(int x) { //O(1)
        stackTmp.push(x);
    }

    //worse O(n)
    //avg O(1)
    int pop() {
        if (stackMy.empty()){
            while (!stackTmp.empty()){
                stackMy.push(stackTmp.top());
                stackTmp.pop();
            }
        }
        int res=stackMy.top(); stackMy.pop();
        return res;
    }

    //worse O(n)
    //avg O(1)
    int peek() {
        if (stackMy.empty()){
            while (!stackTmp.empty()){
                stackMy.push(stackTmp.top());
                stackTmp.pop();
            }
        }
        return stackMy.top();
    }

    bool empty() {
        return stackMy.empty() && stackTmp.empty();
    }

private:
    stack<int>stackMy;
    stack<int>stackTmp;
};

int main(){
    MyQueue *obj=new MyQueue();
    obj->push(1);
    obj->push(2);
    int itemPop=obj->pop();
    cout<<"pop: "<<itemPop<<endl;
    int itemPeek=obj->peek();
    cout<<"peek: "<<itemPeek<<endl;
    bool checkEmpty=obj->empty();
    cout<<"empty: "<<checkEmpty<<endl;
    return 0;
}