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

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)