数据结构--栈&队列

栈

    栈是一种先进后出(Last In First Out)的数据结构，只允许操作栈顶元素,栈的结构模型如下图所示：

栈中常用方法：

    E push(E item)：将元素压入栈

    E pop()：获取并删除栈顶元素

    E peek()：获取但不删除栈顶元素

    boolean isEmpty()：判断栈是否为空

    栈的数据结构可以由数组或者链表实现，用数组实现的栈叫顺序栈，用链表实现的栈叫链式栈。在Java中，顺序栈使用Java.util.stack类实现，链式栈使用Java.util.LinkedList类实现。

栈的出栈顺序：

    假设A、B、C依次入栈，则A、B、C所有出栈情况如下图所示：

    假设A、B、C、D依次入栈，则A、B、C、D所有出栈情况如下图所示： 

栈的常见应用场景：

场景一：浏览器的回退与前进

    要实现浏览器的回退与前进这个功能只需要两个栈，其中一个栈为前进栈而另一个栈为后退栈，假设依次访问了1、2、3、4个页面，我们就需要将1、2、3、4个页面依次压入前进栈，如果要回头看2这个页面，当点击回退按钮时，首先会从前进栈中弹出4、3页面然后压入后退栈中，假设又需要访问3页面，则在点击前进按钮，这时后退栈中首先会弹出3页面然后压入前进栈，以此规律来实现浏览器的回退与前进功能

场景二：虚拟机栈

    每个线程都有一块独立的结构为栈的内存空间，这块空间被称为“虚拟机栈”。

    JVM虚拟机栈是由若干栈帧组成，而每个栈帧中保存有：局部变量表、操作数栈、动态链接、方法出口信息。每一次方法调用都会有一个栈帧被压入虚拟机栈，当方法调用结束之后，该栈帧则会被弹出虚拟机栈。

队列

    队列与栈恰好相反，队列是一种先进先出(First In First Out)的数据结构，队列只允许对队头的元素进行出队操作，在队尾进行元素入队操作，且根据不同的实现机制可将队列区分为：单队列与循环队列

队列的常用方法：

     int size()：获取队列长度

    boolean offer(E)：添加元素到队尾

    E poll()：获取队首元素并从队列中删除

    E peek()：获取队首元素但并不从队列中删除

     队列的数据结构可以由数组或者链表实现，用数组实现的队列叫顺序队列，用链表实现的队列叫链式队列。在Java中，顺序队列使用Java.util.Queue类实现，链式队列使用Java.util.LinkedList类实现。

单队列

    只允许在一端进行插入操作，而在另一端进行删除操作的线性表。而使用数组实现的单队列(顺序队列)容易发生“假溢出”。假溢出是指：当进行入队、出队操作的时候，队头和队尾都会持续往后移动，当队尾移动到最后的时候,即使数组中还有空余空间我们也无法再往队列中添加数据。

循环队列

    为了避免发生假溢出，可以采用循环队列。循环队列是利用**（队尾下标+1）%数组长度** 来动态得到添加元素的下标位置。当**（队尾下标+1）%数组长度 = 队头下标 **时代表队列已满。

手写队列：

//循环队列
public class MyCircularQueue {
    private int[] array;
    private int front;// 对头
    private int rear;// 队尾

    public MyCircularQueue(int capicity) {
        array = new int[capicity];
    }

    // 入队
    public void enQueue(int element) throws Exception {
        if ((rear + 1) % array.length == front) {
            deQueue();
        }
        array[rear] = element;
        rear = (rear + 1) % array.length;
    }

    //出队
    public int deQueue() throws Exception {
        if (rear == front) {
            throw new Exception("队列为空!");
        }
        int element = array[front];
        front = (front + 1) % array.length;
        return element;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        for (int begin = front; begin != rear; begin = (begin + 1) % array.length) {
            builder.append(array[begin]);
            if (begin != (rear + array.length - 1) % array.length) {
                builder.append(",");
            }
        }
        builder.append("]");
        return builder.toString();
    }
}

队列的常见应用场景：

场景一：KTV点歌列表

     使用队列保存已点歌曲列表，每次点歌时，将歌曲放入队尾。播放歌曲时，从队头取出。符合先进先出的存取特点。

场景二：阻塞队列

     阻塞队列是在队列基础上加了阻塞操作的队列。所有的阻塞队列都是线程安全的，当队列为空的时候，出队操作阻塞，当队列满的时候，入队操作阻塞。使用阻塞队列我们可以很容易实现“生产者 - 消费者“模型。

场景三：线程池的任务队列

    线程池中没有空闲线程时，新的线程任务请求线程资源时，线程池会将这些线程任务放在队列中，当有空闲线程的时候，会循环中反复从队列中获取任务来执行。队列分为无界队列(基于链表)和有界队列(基于数组)。无界队列的特点就是可以一直入列，除非系统资源耗尽，比如 ：FixedThreadPool 使用无界队列 LinkedBlockingQueue。而有界队列是当队列已满时，后面再有线程任务就会判断是否超出最大线程数，如果超出则执行拒绝策略。