> For the complete documentation index, see [llms.txt](https://kongchengzhuge.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://kongchengzhuge.gitbook.io/leetcode/225.-implement-stack-using-queues.md).

# 225. Implement Stack using Queues

## problem description

Implement the following operations of a stack using queues.

* push(x) -- Push element x onto stack.
* pop() -- Removes the element on top of the stack.
* top() -- Get the top element.
* empty() -- Return whether the stack is empty.

**Example:**

```
MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false
```

**Notes:**

* You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
* Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
* You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

## algorithm thought

使用队列实现一个栈。队列和栈的性质是不同的，一个是FIFO一个是FILO。所以使用队列实现的栈，时间效率肯定很低。

主要要实现的是top和pop操作。其他操作不需要改动。

pop操作：首先得到当前的size，然后执行size-1次，将队列头push到队列尾。size-1次之后，队列头就是开始的队列尾了，也就是最后push进队列的数，也就是stack pop操作需要pop的数字。可以看到这里时间复杂度是O(n)，stack的pop操作，时间复杂度是O(1)

top操作：可以像上面一样，使用O(n)时间得到顶元素。但是也可以使用cache减少操作。时间复杂度降低到O(1)，在每次push的时候，将cache设置为push的元素。每次pop的时候，将cache重新设置为队列倒数第二个数。这样top操作直接返回cache即可

## code

```cpp
class MyStack {
public:
    /** Initialize your data structure here. */
    queue<int> qu;
    int cache;

    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        cache=x;
        qu.push(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int res=cache;
        int times=qu.size();
        while(--times){
            cache=qu.front();
            qu.push(cache);
            qu.pop();
        }
        qu.pop();
        return res;
    }

    /** Get the top element. */
    int top() {
        return cache;    
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return qu.empty();
    }
};

/**
 * 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();
 * bool param_4 = obj.empty();
 */
```

## algorithm analysis

这里面只有pop操作时间复杂度是O(n)的，其他操作都是O(1)