剑指 Offer 09. 用两个栈实现队列

解题思路：栈

使用两个栈实现先入先出的队列

其中一个栈作为压入栈：data 我们只向这个栈压入数据

另一个栈作为弹出栈：help，这个栈只负责弹出数据

栈作为一种 LIFO 的数据结构，要想实现队列的入队和出队操作，需要定义一个方法，这个方法负责将 data 中的数据全部都“倒入” help 中；

该方法命名为 dataToHelp ，我们需要保证两点：

  1. 倒入的前提是 help 中不能有数据
  2. 需要将 data 中的所有数据都一次性倒完

该方法如下：

  1. private void dataToHelp(){
  2.     while(!data.isEmpty()){
  3.         help.push(data.pop());
  4.     }
  5. }

该方法执行的时机理论上没有要求，只要满足上述两点即可。

代码

  1. class CQueue {
  2.     private Stack<Integer> data;
  3.     private Stack<Integer> help;
  5.     public CQueue() {
  6.         data = new Stack<>();
  7.         help = new Stack<>();
  8.     }
  10.     public void appendTail(int value) {
  11.         data.push(value);
  12.     }
  14.     public int deleteHead() {
  15.         if(data.isEmpty() && help.isEmpty()){
  16.             return -1;
  17.         }
  18.         if(help.isEmpty()){
  19.             dataToHelp();
  20.         }
  21.         return help.pop();
  22.     }
  24.     private void dataToHelp(){
  25.         while(!data.isEmpty()){
  26.             help.push(data.pop());
  27.         }
  28.     }
  29. }
  31. /**
  32.  * Your CQueue object will be instantiated and called as such:
  33.  * CQueue obj = new CQueue();
  34.  * obj.appendTail(value);
  35.  * int param_2 = obj.deleteHead();
  36.  */

复杂度分析

  • 时间复杂度：
    • appendTail ：在末尾添加元素的时间复杂度为 O(1)
    • deleteHead ：删除头节点的时间复杂度是一个均摊复杂度计算问题，我们在这里讨论的是向队列添加了 N 个元素并删除了这 N 个元素的复杂度；如果是上面说的情况，那么 deleteHead 中涉及到了 dataToHelp 操作，该算法的复杂度为 O(N)，所以 deleteHead 的时间复杂度也为 O(N)
  • 空间复杂度：O(N)
    • 栈 data 与 help 共保存 N 个元素

_