LeetCode--225--easy--ImplementStackUsingQueues

package com.app.main.LeetCode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IDEA
 * author:Dingsheng Huang
 * Date:2019/7/22
 * Time:下午8:16
 *
 * id = 225
 *
 * level = easy
 *
 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).

 *
 *
 */
public class ImplementStackUsingQueues {

    // 思路， 用一个队列， pop 时， 队尾要先出， 将 deque 进行 length -1 轮 pop + push 后， 执行最后一次 pop 得到结果
    Deque<Integer> deque = new LinkedList<>();

    /** Initialize your data structure here. */
    public ImplementStackUsingQueues() {

    }

    /** Push element x onto stack. */
    public void push(int x) {
        deque.push(x);

    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int len = deque.size();
        while (len > 1) {
            len--;
            deque.push(deque.pop());
        }
        return deque.pop();

    }

    /** Get the top element. */
    public int top() {
        int len = deque.size();
        while (len > 1) {
            len--;
            deque.push(deque.pop());
        }
        int res = deque.pop();
        deque.push(res);
        return res;

    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return deque.isEmpty();
    }

}