剑指OfferT09——用两个栈实现一个队列(Java)

用两个栈实现一个队列。

队列的声明如下：

appendTail ：分别完成在队列尾部插入整数和

deleteHead：在队列头部删除整数的功能。

(若队列中没有元素，deleteHead 操作返回 -1 )

说明：

1. 将队列想象成有两个部分，前半部分是stack2，后半部分是stack1;

   为什么要这样拆：因为这里是将新元素入stack1，按照物理的思想这个新元素在stack1中的位置正好对应在队列的尾部，因为新元素是最后一个入栈（队列）的

2. 将新元素不断的加到stack1的尾部，就相当于是将新元素加到队列的尾部

3. 重点操作：删除

   • 由于这是一个想象的队列结构，那我们就应该在stack2（前半部分）中弹出队头元素

   • 第一次删除时，发现stack2没有元素，所以这个时候看看stack1有没有元素，如果有，就让stack1中的元素有序地向前走，一直走到队头，

• 这个时候stack2即将出栈的元素就是想象的队头元素了

  • 若再有出队列的操作，队列的前半部分（stack2）还有元素，就直接弹出队头元素（将该元素从stack2中弹出栈）。

  • 若队列的前半部分没有元素了，就让后半部分有序的进场，填充前半部分。

  • 如果此时后半部分也没元素了，就代表整个队列都空了。

package com.xiexuanqian.javastudy.jianzhioffer.day01;

import java.util.linkedList;
import java.util.Stack;

public class OfferT09 {
    
    //首
    private linkedList stack1;
    //次
    private linkedList stack2;
    
    public OfferT09() {
       stack1 = new linkedList<>();
       stack2 = new linkedList<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if(stack2.isEmpty()){
            if(stack1.isEmpty()){
                return -1;
            }
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

package com.xiexuanqian.javastudy.jianzhioffer.day01;

public class Application {
    public static void main(String[] args) {
        //T09测试
        OfferT09 offerT09 = new OfferT09();
        offerT09.appendTail(10);
        int res = offerT09.deleteHead();
        System.out.println(res);
    }
}

• 要用到栈结构时，尽量不要直接使用Java已经定义好的Stack，而是使用linkedList结构模拟栈操作

• 使用Stack的运行结果

---

• 使用linkedList的运行结果

原因：

• Stack：基于数组实现，随机访问（查找）效率更高，增删改效率较低
• linkedList：基于链表实现，增删改效率更高，随机访问（查找）效率较低

当我们追求时间效率的时候，如果有大量插入删除操作，不妨利用 linkedList 实现栈的相关功能

不妨：can do worse than…