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

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

1.结果

执行结果:通过显示详情>

执行用时:60 ms ,在所有Java提交中击败了28.74%的用户

内存消耗:49.6 MB，在所有Java提交中击败了5.09%的用户

通过测试用例:55/55

2.时间花费

一个小时左右，主要经过了三个历程：

• 第一是，一开始只想到了单次操作，且一次输入多个数的情况，相当于连续多次入栈的意思‘
• 第二是，中途再一次捋顺这个逻辑，多次操作的正确过程在第一次的基础上得到完善
• 第三是，AC

3.思路

栈的特点是先进后出，队列的特点的先进先出。

也就是说，要将第一次入栈的数，都逆序一下，正好出栈再入栈到另一个栈可以实现。

再一个就是，多次连续出入队的问题，这时要考虑什么时候把栈1的元素都pop然后放到栈2。

也就是，当栈2的元素都弹出了（这样不会被后来的元素把最先入栈的元素覆盖），再一次性把栈1的元素逆序拿过来（遍历栈1，栈1pop然后栈2add），以此类推。

4.code

package leecode;

import java.util.Arrays;
import java.util.Stack;

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

 * 用两个栈实现一个队列。
 * 队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，
 * 分别完成在队列尾部插入整数和在队列头部删除整数的功能。
 * (若队列中没有元素，deleteHead操作返回 -1 )
 */
class CQueue {
    /**
     * 思路：
     * 入队：每次入队操作就是，从栈1入栈
     * 出队：每次出队操作就是，清空栈1，并一次入栈2，再pop一个元素
     * 要注意到的是，因为stack2如果还有元素，此时出队操作直接在stack2上执行出栈操作，知道stack2清空了后才可以再把stack1的放进stack2
     * 判断队列为空就是，
     *
     */

    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();

    public CQueue() {

    }

    public void appendTail(int value) {
        this.stack1.add(value);
        //不是进一次就pop再add到stack2，而是等到出队的时候一次性pop
        //this.stack1.pop();
        //this.stack2.add(value);
    }

    public int deleteHead() {

        //stack2d没有元素时入栈
        if (stack2.isEmpty()){
            while (!stack1.isEmpty()){
                int pop = stack1.pop();
                stack2.add(pop);
            }
        }

        //如果入栈后还是没元素，那说明队列空了
        if (stack2.isEmpty()){
            return -1;
        }
        return this.stack2.pop();
    }

    public static void main(String[] args) {
        CQueue cq = new CQueue();
        cq.appendTail(3);
        System.out.println(Arrays.toString(cq.stack1.toArray()));
        System.out.println(cq.deleteHead());
        System.out.println(cq.deleteHead());
        System.out.println(cq.deleteHead());
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70