剑指 Offer——第一天（栈与队列)）

第一题——用两个栈实现队列

解题思路：

借鉴大佬的清晰思路帮助更好的理解。

栈无法实现队列功能： 栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈。 双栈可实现列表倒序： 设有含三个元素的栈 A = [1,2,3]A=[1,2,3] 和空栈 B = []B=[]。若循环执行 AA 元素出栈并添加入栈 BB ，直到栈 AA 为空，则 A = []A=[] , B = [3,2,1]B=[3,2,1] ，即 栈 BB 元素实现栈 AA 元素倒序 。 利用栈 BB 删除队首元素： 倒序后，BB 执行出栈则相当于删除了 AA 的栈底元素，即对应队首元素。

函数设计： 题目只要求实现 加入队尾appendTail() 和 删除队首deleteHead() 两个函数的正常工作，因此我们可以设计栈 A 用于加入队尾操作，栈 B 用于将元素倒序，从而实现删除队首元素。

加入队尾 appendTail()函数： 将数字 val 加入栈 A 即可。 删除队首deleteHead()函数： 有以下三种情况。 当栈 B 不为空： B中仍有已完成倒序的元素，因此直接返回 B 的栈顶元素。 否则，当 A 为空： 即两个栈都为空，无元素，因此返回 -1−1 。 否则： 将栈 A 元素全部转移至栈 B 中，实现元素倒序，并返回栈 B 的栈顶元素。

代码：

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

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

第二题——包含min函数的栈

问题描述

解题思路

利用双栈解出 pop ，min ，push。首先压栈进值，然后在进栈的时候：比较一下，最小的值在最上面；此时有个缺点就是值是存在两次的，相当于用空间换取了时间；所以在后续的pop 以及push 和 return stack.get(stack.size()-2);都有两次，这个里面的-2的原因就在于此。希望对大家有帮助

代码

class MinStack {
          
   
        Stack <Integer> stack;
    /** initialize your data structure here. */
    public MinStack() {
          
   
        stack = new Stack<>();
    }
    
    public void push(int x) {
          
   
        if(stack.isEmpty()){
          
   
            stack.push(x);
            stack.push(x);
        }
        else {
          
   
            int tmp=stack.peek();
            stack.push(x);
            if(tmp<x){
          
   
                stack.push(tmp);
            }
            else stack.push(x);
        }
    }
    
    public void pop() {
          
   
        stack.pop();
        stack.pop();       
    }
    
    public int top() {
          
   
        return stack.get(stack.size()-2);
    }
    
    public int min() {
          
   
        return stack.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();
 */

结尾

加油！！！冲鸭！希望能坚持下去，欢迎观看！！！