本题其实我解出来了,但是不是最优解。
    本题,要跟面试官确认,是push操作更多,还是pop/top操作更多

    • 如果是push操作更多,我之前的方法没有任何问题,用两个Queue<Integer>
    • 如果是pop/top操作更多,那下面这个方法就更好,也更简洁
      • 只用一个Queue<Integer>
      • 每次插入的时候,都将Queue<Integer> rotate,这样就变成了一个Stack<Integer>
      • 时间复杂度
        • push225. Implement Stack using Queues - 图1
        • top/pop:225. Implement Stack using Queues - 图2

    代码如下:

    1. class MyStack {
    2. private Queue<Integer> queue;
    3. /** Initialize your data structure here. */
    4. public MyStack() {
    5. queue = new LinkedList<>();
    6. }
    7. /** Push element x onto stack. */
    8. public void push(int x) {
    9. queue.offer(x);
    10. for (int i = 1; i < queue.size(); ++i) {
    11. queue.offer(queue.poll());
    12. }
    13. }
    14. /** Removes the element on top of the stack and returns that element. */
    15. public int pop() {
    16. return queue.poll();
    17. }
    18. /** Get the top element. */
    19. public int top() {
    20. return queue.peek();
    21. }
    22. /** Returns whether the stack is empty. */
    23. public boolean empty() {
    24. return queue.isEmpty();
    25. }
    26. }
    27. /**
    28. * Your MyStack object will be instantiated and called as such:
    29. * MyStack obj = new MyStack();
    30. * obj.push(x);
    31. * int param_2 = obj.pop();
    32. * int param_3 = obj.top();
    33. * boolean param_4 = obj.empty();
    34. */