剑指 Offer 9. 用两个栈实现队列 && 30. 包含min函数的栈

9题目描述：

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

解析：

1.定义两个栈，一个栈负责进入，一个栈负责出
2.当有元素进入时，第一个栈后面加入，当有元素出队列的时候，分为三种情况
（1）两个栈都是空栈，则证明是空队列
（2）第一个栈有元素，第二个栈没有元素，把第一个栈的元素全部出栈，放入第二个栈，第二个栈出栈
（3）第二个栈还有元素，则第二个栈出栈

Java:

class CQueue {
    LinkedList<Integer> stack1;
	LinkedList<Integer> stack2;

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

JavaScript:

var CQueue = function() {
    this.stack1 = [];
    this.stack2 = [];
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    this.stack1.push(value);
    return null;
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    if(!(this.stack1.length || this.stack2.length)) {
        return -1;
    }
    if(!this.stack2.length) {
        while(this.stack1.length) {
            let val = this.stack1.pop();
            this.stack2.push(val);
        }
    }
    return this.stack2.pop();
};

30题目描述：

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

Java:

class MinStack {
    Stack<Integer> sk1;
    Stack<Integer> sk2;
    /** initialize your data structure here. */
    public MinStack() {
        sk1=new Stack<Integer>();
        sk2=new Stack<Integer>();
    }
    
    public void push(int x) {
        sk1.push(x);
        if(sk2.empty()||sk2.peek()>=x)
            sk2.push(x);
    }
    
    public void pop() {
        var val=sk1.pop();
        if(val.equals(sk2.peek()))
           sk2.pop();
    }
    
    public int top() {
        return sk1.peek();
    }
    
    public int min() {
        return sk2.peek();
    }
}

JavaScript:

var MinStack = function() {
    this.stack = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x)
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.stack.pop()
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1]
};

/**
 * @return {number}
 */
MinStack.prototype.min = function() {
    return Math.min(...this.stack)
};