具体问题

• 使用栈实现一个队列（手写代码），考虑线程安全的实现
  思路：使用2个栈，一个用于存放数据，另外一个用于辅助在取数据或者删除时临时存放。线程安全通过加锁来实现。
  代码：

import java.util.Stack;
import java.util.concurrent.locks.ReentrantLock;
public class StackQueue<T> {
    Stack<T> data = null;
    Stack<T> temp = null;
    ReentrantLock lock = new ReentrantLock();

    public StackQueue() {
        data = new Stack<T>();
        temp = new Stack<T>();
    }

    public T pop() {
        lock.lock();
        if (temp.isEmpty())
            swap(data, temp);
        if (temp.isEmpty()) {
            lock.unlock();
            return null;
        }
        T top = temp.pop();
        lock.unlock();
        return top;

    }

    public T peek() {
        lock.lock();
        if (temp.isEmpty())
            swap(data, temp);
        if (temp.isEmpty()) {
            lock.unlock();
            return null;
        }
        T top = temp.peek();
        lock.unlock();
        return top;
    }

    public void push(T element) {
        lock.lock();
        if (data.isEmpty())
            swap(temp, data);
        data.push(element);
        lock.unlock();
    }
    void swap(Stack<T> src, Stack<T> dest) {
        while (!src.empty()) {
            dest.push(src.pop());
        }
    }
    public boolean isEmpty(){
        return data.isEmpty() && temp.isEmpty();
    }
}

• java线程模型
  线程实现：
• 内核级线程：轻量级进程，会消耗一定的内核空间，由内核来完成线程切换
• 用户线程：完全建立在用户空间上的线程，更加轻量级，开销更低
• 用户线程和内核线程混合

线程调度：

• 抢占式：线程的执行时间由线程自己决定，在自己执行完后需要主动通知系统进行进程切换
• 协同式：线程的切换由系统控制，运行时间由系统分配

线程状态：

• 就绪态 Ready：等待分配运行时间

• 运行态 Running：正在运行

• 阻塞态 Blocking：等待IO等操作

• 等待态 Waiting、Timed Waiting：CPU调度、手动通过sleep()进入等待

• 终止态 Terminated：运行结束

• 线程通信方式

• 共享变量

• 关键字：volatile、synchronized

• 锁：ReentrantLock

• 管道通信：PipedInputStream和PipedOutputStream

• 等待与通知：object.wait()/object.notify()

• 条件变量：Condition

• 倒计时协调器：CountDownLatch

• 复用栅栏：CyclicBarrier

• 信号量：Semaphore

• 阻塞队列：ArrayBolckingQueue

• 交换：Exchanger

• jvm中，eden、s1、s2的作用
  在分代回收的机制中，eden、s1、s2都用于保存新生代的数据（存活时间较短且不会占用很多空间的小对象），其中所分配的空间比例一般为。其中，eden用于存储新创建的对象，s1用于保存上一轮回收后存活的对象，s2用于下一次GC时的辅助空间。

所采用的GC算法是复制算法，具体机制为：在发生垃圾回收时，eden和s1中存活的对象复制到s2中并对eden和s1进行清理，然后交换s2和s1的角色。

在这样的机制下，虚拟机的空间利用率能达到，只有用于下一轮GC的辅助空间会被“浪费”，且由于会在s1和s2交替的使用复制算法，所以不会存在较大的内存碎片，整体的空间利用率较高，。

• 只用eden和s能否解决问题
  能解决问题，但是效率较低。

对比使用eden、s1、s2进行处理的方法，如果去掉其中一个Survivor空间，则每一次GC都只能从eden复制到s中。如果对s本身没有优化处理的话，在s中容易产生内存碎片，导致eden中稍大的存活对象都无法存放于s，最终导致提前触发下一轮GC甚至报错。虽然空间是的用到了，但是整体的效率和可靠性还是较低。

• TCP的拥塞控制机制
  慢开始、拥塞控制、快重传、快恢复

• TCP连接为什么要使用三次握手
  用于确认通信双发的接收和发送能力

连接建立阶段	内容	发送方	接收方
1	发送方发送SYN	发送方： 接收方：	发送方：发送能力 接收方：接受能力
2	接收方发送ACK和SYN	发送方：接受能力、发送能力 接收方：接受能力、发送能力	发送方：发送能力 接收方：接受能力
3	发送方发送ACN和SYN	发送方：接受能力、发送能力 接收方：接受能力、发送能力	发送方：接受能力、发送能力 接收方：接受能力、发送能力

• 解释一下servlet是什么
  本质上就是一个实现了相关接口的类，运行在Tomcat容器中。

维基百科：Servlet（Server Applet），全称Java Servlet，未有中文译文。是用Java编写的服务器端程序。其主要功能在于交互式地浏览和修改数据，生成动态Web内容。狭义的Servlet是指Java语言实现的一个接口，广义的Servlet是指任何实现了这个Servlet接口的类，一般情况下，人们将Servlet理解为后者。

• servlet单例吗？为什么
  不一定。
  默认的情况是单例，如果在web.xml中，给对一个Servlet类进行多个配置，则会有多个实例。但是大部分情况下，只会配置一个，所以是单例的。

对于映射到同一个Servlet类的多个请求，通过创建一个Servlet实例，多个线程执行这个Servlet的service方法的实现。所以在Servlet中，实例变量都不是线程安全的，只有局部变量（request、session等）才是线程安全的。

• servlet在处理请求前，tomcat在底层做了些啥，或者说实现一个Tomcat的大致思路
  Tomcat的结构主要分为Server、Service、Connector、Container四部分。
  Server： Tomcat服务器本身
  Service：服务，默认的是Catalina
Connector：用于处理网络连接，监听端口封装网络协议，屏蔽连接与处理的细节
  Container：管理Servlet并处理请求，由Engine、Host、Context、Warrper四个部分（层级）组成。

参考：

• 聊聊Tomcat的架构设计

• 数据库索引
  B+树索引和哈希索引

• B＋树
  非叶子节点中可以保存多个指针数据，每一个数据都是一个指向其子节点的指针。
  叶子节点用于保存真正的数据，与非叶子节点相同，每个叶子节点也能保存多个数据，且相邻叶子节点之间存在指针连接。

• 聚簇索引与非聚簇索引
  二者的数据结构都是B+树
  聚簇索引：叶子节点保存实际的数据，所以索引的顺序决定了数据的顺序
  非聚簇索引：叶子节点保存指向实际数据的指针，所以数据的顺序与索引无关

• 非聚簇索引怎么指向具体数据
  首先需要明确的是，非聚簇索引（也叫 二级索引 ）中，叶子节点里面指向数据的“指针”，并不是真正意义上的指针，即 不是指向物理位置的指针。
  在非聚簇索引中，数据和索引是分开存储的，索引的叶子节点保存的是索引列和数据列的主键值。在根据保存的主键，在聚簇索引中进行第二次查找。

参考自《高性能MySQL》第三版：
这意味着通过二级索引查找行，存储引擎需要找到二级索引的叶子节点获得对应的主键值，然后更具这个值去聚簇索引中查找到对应的行。

• 什么时候需要建立索引
  考虑如下因素：

• 查询频度：对于查询频度高或常用于连接查询的字段或组合字段，建立索引能提高查询的效率

• 删改频度：每一次删改都有可能需要对索引进行调整，频繁的删改会影响性能

• 重复程度：对于重复度较高的数据，其索引也具有较高的重叠性，对效率的提高不明显却要占用空间

• 数据类型：像blob、clob等用于保存较大对象的特殊类型，不适合建立索引；较大的文本字段，建立索引也会占用较大的空间且效率不高

• 表的规模：在表中数据较多时，使用索引一般能提高检索效率，表规模较小时，索引对效率的影响不大

• 存储介质：当数据保存在内存中时，索引对效率的提升不会很明显

• 如何不使用递归遍历一颗二叉树
  中序遍历思路：对于每一个节点，优先遍历左孩子，一直到最左边的节点遍历完。处理右边的节点，栈中保存的是左子树正在被遍历的节点。当一个节点的子树遍历完后，从栈中取一个节点（该节点的父节点），遍历其右子树。

非递归中序遍历二叉树

中序遍历代码：

    public static void iterate(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (true){
            // 不断往左下方遍历，中间的节点保存在栈中
            while (node.left != null) {
                stack.push(node);
                node = node.left;
            }
            // 处理最左边的节点
            process(node);

            // 从栈中取出父节点，并处理其右子树
            while (!stack.isEmpty() && node.right == null) {
                node = stack.pop();
                process(node);
            }
            if (node.right != null) {
                // 有右孩子，则处理右孩子
                node = node.right;
            } else {
                // 栈空，所有节点处理完毕
                break;
            }
        }
    }

    public static void process(TreeNode node) {
        System.out.print(node.val+ " ");
    }