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

# 225. Implement Stack using Queues

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

## 題目:
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack ```(push, top, pop, and empty)```.

Implement the ```MyStack``` class:

* ```void push(int x)``` Pushes element x to the top of the stack.
* ```int pop()``` Removes the element on the top of the stack and returns it.
* ```int top()``` Returns the element on the top of the stack.
* ```boolean empty()``` Returns ```true``` if the stack is empty, ```false``` otherwise.

**Notes:**

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

**Follow-up**: Can you implement the stack using **only one queue**?

**Example 1:**

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

## 解題想法:
兄弟題目: [232. Implement Queue using Stacks](/lJk0M3hZQxWX52Ncfk4Ezg)

* 要求用que做stack且要求只能用一個que
* que: FIFO 先進先出
* stack:FILO 先進後出
* 想法:
* push: 正常push
* pop:
* 若有n個元素，將其面n-1個依序pop再append
* 最後一個即為所求
* top:
* 若有n個元素，將其面n-1個依序pop再append
* 最後一個即為所求，top不會刪除，要再將其append
* 或是直接用que[-1] or que.front()
* 示意圖:

## Python:

from collections import deque
class MyStack(object):

    def __init__(self):
        self.que=deque()

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        #正常加入
        self.que.append(x)
        

    def pop(self):
        """
        :rtype: int
        """
        #若有n個元素，將其面n-1個依序pop再append
        num=len(self.que)
        if num==1:
            res=self.que.popleft()
            return res
        for _ in range(num-1):
            item=self.que.popleft()
            self.que.append(item)
        res=self.que.popleft()
        return res
        

    def top(self):
        """
        :rtype: int
        """
        #若有n個元素，將其面n-1個依序pop再append
        #最後一個即為所求，top不會刪除，要再將其append
        num=len(self.que)
        if num==1:
            res=self.que.popleft()
            self.que.append(res)
            return res
        for _ in range(num-1):
            item=self.que.popleft()
            self.que.append(item)
        res=self.que.popleft()
        self.que.append(res)
        return res
        ''' 
        #也可以
        return self.que[-1]
        '''

    def empty(self):
        """
        :rtype: bool
        """
        return len(self.que)==0

if __name__ == '__main__':
    obj = MyStack()
    obj.push(1)
    obj.push(2)
    print(obj.top())
    print(obj.pop())
    print(obj.empty())

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

## C++:
* 也可以優化
* 每次push時候就將n-1個元素反轉
* push:O(n)
* pop、top、empty(): O(1)

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

class MyStack {
public:
    MyStack() {

    }

    void push(int x) {
        //O(n) 每次push，n-1個元素pop再append
        que.push(x);
        for (int i=0; i<que.size()-1; i++){
            que.push(que.front());
            que.pop();
        }
    }

    int pop() {
        //O(1)
        int res=que.front();
        que.pop();
        return res;
    }

    int top() {
        //O(1)
        return que.front();
    }

    bool empty() {
        //O(1)
        return que.empty();
    }

private:
    queue<int> que;

};

int main(){
    MyStack * obj= new MyStack();
    obj->push(1);
    obj->push(2);
    int topItem=obj->top();
    cout<<"top: "<<topItem<<endl;
    int popItem=obj->pop();
    cout<<"popL "<<popItem<<endl;
    bool CheckEmpty = obj->empty();
    cout<<"Empty "<<CheckEmpty<<endl;
    return 0;
}