# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/225.-implement-stack-using-queues.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.