第1天 栈与队列（简单）

发表于 | 分类于
字数统计: 728 | 阅读时长 ≈ 3

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

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

示例 1：

1
2
3
4
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：
1
2
3
4
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

  • 1 <= values <= 10000
  • 最多会对 appendTail、deleteHead 进行 10000 次调用

理解题意

使用两个栈实现队列的入队和出队功能，栈只支持压栈和出栈操作

题解

  1. 直接往stack1里压栈,出栈的时候从stack2里出;
  2. stack2里出没了,再把stack1里的放到stack2里,再接着出
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
class CQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        }else{
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.isEmpty() ? -1 : stack2.pop();
        }
    }
}

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

剑指 Offer 30. 包含min函数的栈

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

示例:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示：

  1. 各函数的调用总次数不超过 20000 次

理解题意

能够实时获得当前栈中的最小值，使用辅助栈存储每个元素入栈时的最小值，当元素出栈，其对应的最小值也相应出栈。

题解

使用一个minSt辅助栈来存放较小的值

每次入栈时,如果要入栈的数小于等于辅助栈顶的数,就把待入栈的数也压入辅助栈中,辅助栈就用来返回当前的最小值.

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
class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minSt;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<Integer>();
        minSt = new Stack<Integer>();
    }
    
    public void push(int x) {
        stack.push(x);
        if(minSt.empty() || x <= minSt.peek()){ 
            // 需要加 ‘=’, 否则“0-1-0”这样的序列中, 辅助栈minSt中只会有1个‘0’,
            // 这样当stack中出栈时, minSt中可能就没元素了
            minSt.push(x);
        }
    }
    
    public void pop() {
        // if(stack.pop() == minSt.peek()){ // == 比的是地址,应该用equals
        if(stack.pop().equals(minSt.peek())){
            minSt.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return minSt.peek();
    }
}

/**
 * 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();
 */