难度

简单

思路

双栈实现

  • 从主栈依次 pop 到 副栈中，此时相当于链表反转，直接 pop 副栈即可，
  • 而新增的可以直接添加到主栈，此时删除、新增不受任何影响。

  • 虽然 删除 操作需要遍历集合，但是把时间成本均摊则为 _**O(1)**_。

    1. class CQueue_3 {
    2.   private LinkedList<Integer> normal;
    3.   private LinkedList<Integer> temp;
    4.   public CQueue_3() {
    5.       normal = new LinkedList<>();
    6.       temp = new LinkedList<>();
    7.   }
    9.   public void appendTail(int value) {
    10.       normal.push(value);
    11.   }
    13.   public int deleteHead() {
    14.       if (temp.isEmpty()) {
    15.           while (!normal.isEmpty()) {
    16.               temp.push(normal.pop());
    17.           }
    18.       }
    20.       if (temp.isEmpty()) {
    21.           return -1;
    22.       } else {
    23.           return temp.pop();
    24.       }
    26.   }
    27. }

    | 时间复杂度 | O(1) | | —- | —- | | 空间复杂度 | O(n) |

总结

  • 双栈组合可以轻易实现 队列 需求，其他使用一个栈也可以完成需求，不过时间复杂度很高。
  • 对于优化方面，一是频繁插入新节点的则使用 LinkedList 对象，底层使用 双向链表 存储数据，但相应地，需要消耗一定空间。