一、 剑指offer09. 用两个栈实现队列

要求：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

使用Java中的LinkedList和Stack的区别：

使用Stack的方式来做这道题，会造成速度较慢； 原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。 可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。

一般来说用LinkedList表示栈更好一点。

解法1： 使用一个链表

**思路：**定义一个链表，表示该队列。使用addLast实现队列的末尾添加，在实现出队时使用removeFirst。同时对链表进行判断，如果链表长度为空，则返回-1。（但是这么做好像有点不符合题意）

代码：

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
class CQueue {
    private LinkedList<Integer> list;

    public CQueue() {
        this.list = new LinkedList<Integer>(); 
    }
    
    public void appendTail(int value) {
        list.addLast(value);
    }
    
    public int deleteHead() {
        if(list.size() == 0){
            return -1;
        }else{
            return list.removeFirst();
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

解法2： 使用两个栈

思路：

定义两个栈（两个薯片桶），第一个栈，负责添加元素。第二个栈负责将第一个栈的元素倒序排列，倒序后第一个栈的尾结点就直接成了第二个栈的头结点。从而解决栈无法直接删除尾结点的问题。

**思考：**使用完第二个栈后，用不用再将栈2的值移动回栈1呢？用！

代码：

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
class CQueue {
    private Stack<Integer> Stack1;
    private Stack<Integer> Stack2;

    public CQueue() {
        Stack1 = new Stack<>();
        Stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        Stack1.push(value);
    }
    
    public int deleteHead() {
        while(Stack1.size()!=0){
            Stack2.push(Stack1.pop());
        }
        if(Stack2.size()==0){
            return -1;
        }else{
            int result = Stack2.pop();
            while(Stack2.size()!=0){
                Stack1.push(Stack2.pop());
            }
            return result;
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

解法3： 标准答案

使用两个链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class CQueue {
    LinkedList<Integer> A, B;
    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }
    public void appendTail(int value) {
        A.addLast(value);
    }
    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        if(A.isEmpty()) return -1;
        while(!A.isEmpty())
            B.addLast(A.removeLast());
        return B.removeLast();
    }
}

解法4：解法2的优化

在看了答案后明白好像不需要再把栈2数据压回到栈1，会再经历一次循环，时间复杂度明显上升。只需要把栈2pop到空，再把栈1的数据压进来就好了（这样就始终是head的数据），数据留在栈1等着就行了。

解法2的优化代码：

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
class CQueue {
    private Stack<Integer> Stack1;
    private Stack<Integer> Stack2;

    public CQueue() {
        Stack1 = new Stack<>();
        Stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        Stack1.push(value);
    }
    
    public int deleteHead() {
        // 如果栈2是空的，判断栈1是否有数据
        if(Stack2.size()==0){
            // 如果栈1没有数据，整个队列为空，返回-1
            if(Stack1.size() ==0){
                return -1;
            }
            // 如果栈1有数据，压栈1的数据进栈2
            while(Stack1.size()!=0){
                Stack2.push(Stack1.pop());
            }
            // 压完数据后，pop栈2的栈顶值
            return Stack2.pop();
        }else{
            // 如果栈2还有数据，证明还有上一次压入的数据没pop完，优先pop栈2的
            return Stack2.pop();
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

时间复杂度明显降低，但是空间复杂度提升了。

二、 剑指offer30. 包含min函数的栈

要求：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)O(1)。

解法1：维护一个辅助栈储存min

难点就是要让min的时间复杂度为 /O(1)/O(1)。因此不能暴力搜索。

思路：维护一个辅助栈，栈顶存储最小值。如果有多个相同值，就存储多个。

注意判断相等的时候要用.equals()方法，而不是简单的==。 否则会出错。

Java 代码中，由于 Stack 中存储的是 int 的包装类 Integer ，因此需要使用 equals() 代替 == 来比较值是否相等。

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
class MinStack {
    /** initialize your data structure here. */
    private LinkedList<Integer> stack;
    private LinkedList<Integer> tempStack;
    public MinStack() {
        stack = new LinkedList<>();
        tempStack = new LinkedList<>();
    }
    
    public void push(int x) {
        stack.add(x);
        if(tempStack.size()==0){
            tempStack.add(x);
        }else{
            // 注意是大于等于
            if(tempStack.getLast()>=x){
                tempStack.add(x);
            }
        }
    }
    
    public void pop() {
        if(stack.getLast().equals(tempStack.getLast())){
            tempStack.removeLast();
        }
        stack.removeLast();
        
    }
    
    public int top() {
        return stack.getLast();
    }
    
    public int min() {
        if(tempStack.size()==0){
            return -1;
        }
        return tempStack.getLast();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

解法2：标准答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}