leetcode 剑指offer刷题（1）

剑指offer09:用两个栈实现队列

首先看到这个题我也是一脸懵，看了好几遍也没看懂题目是什么意思，然后就去看了评论区的解释，然后才看懂，看懂题目之后就比较好做了，所以首先解释一下题目。

示例的输入一共有两行，第一行是要做的操作，第二行则是操作对应的参数。比如"CQueue"初始化一个队列，不需要参数，所以第二行对应的是[ ]，对应输出为null；"appendTail"在队列尾部插入整数，对应的参数为[3]，即在队尾插入整数3，同样地输出也为null；"deleteHead"在队列头部删除整数，对应的参数为[ ],即不需要参数，但是现在队头为3，执行删除操作之后，会输出删除的队头，所以输出为3；再执行deleteHead，此时队列中没有元素，所以返回为-1。

我是采用java语言写的，看完题目之后，首先想到了初始化两个stack,一个栈用来存放插入的元素，另一个栈用来记录弹出的元素。"appendTail"在尾部插入，对应的为压栈操作，即stack1.push()；而删除队头"deleteHeada"则可以将stack1的队头（即栈顶）弹出，并压入stack2。

但是在实现的时候没有考虑时间和空间的因素，也算是一种暴力解法，看了题解和评论区的大佬，发现自己要改进的地方还有很多。

具体实现代码如下：

class CQueue {
    private Stack stk1;
    private Stack stk2;

    public CQueue() {
       stk1 = new Stack();
       stk2 = new Stack();       
    }
    
    public void appendTail(int value) {
        stk1.push(value);
    }
    
    public int deleteHead() {
        if(stk2.isEmpty()){
            if(stk1.isEmpty()){
                return -1;
            }else{
                while(!stk1.isEmpty()){
                    stk2.push(stk1.pop());
                }
                return stk2.pop();
            }
            
        }else{
            return stk2.pop();
        }
    }
}

剑指offer30：包含min函数的栈

这道题同样是实现一个栈，但他额外要求实现一个min函数，返回栈的最小元素。这道题也比较简单（也可能是我考虑的太简单了，没考虑别的光想着怎么通过了5555），直接上代码：

class MinStack {

    
    private Stack stack = new Stack();
    int min = Integer.MAX_VALUE;
    public MinStack() {

    }
    
    public void push(int x) {
        if(x < min) min=x;
        stack.push(x);
    }
    
    public void pop() {
       stack.pop();
       min = Integer.MAX_VALUE;
        for(Integer x:stack){
            if(x < min){
                min=x;
            }
        }  
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return min;
    }
}