关于数据结构与算法:数据结构与算法分析学习笔记五-队列

露从今夜白，月是故土明。

引言

队列在日常生活中时一个非常常见的名词，比方去食堂打饭时排队，排在最后面的总是最先取到餐。最晚达到这个队列往往排在队列的最初面。也就是先进先出。这种排队的特点同样也被引入到了计算机中，也就是音讯队列，电商在搞大促销的时候，峰值会是平时的好几倍，零碎可能会解决不到位，咱们一边将零碎扩容，一边筹备音讯队列，将超过零碎解决能力的强求放在音讯队列中，零碎顺次解决音讯队列中的申请。这种 ” 先进先出 ” 也别引入到了数据结构中，也就是队列。

队列

由下面的探讨咱们能够总结出队列的逻辑构造，数据结构中的队列，即是把一个一个的结点依照某种顺序排列，对其解决的过程和日常生活中的对了是一样的。队列规定为:

• 排列程序: 结点排成一队，起初的排在队尾。
• 处理过程: 在队头处理事件; 队列中有元素始终解决，直至队空或产生中断事件。

队列的定义:

队列 (Queue) 是只容许在一端进行操作而在另一端进行删除操作的线性表。删除端被称为 ” 队头 ”，插入端被称入 ” 队尾 ”。

与栈的不同之处在于，队列是一种先进先出 (First In First Out FIFO) 的线性表；与栈雷同的是，队列也是一种重要的线性构造。依据队列的定义，队列的基本操作有下列这些:

• 置空队列: 将已有队列置空
• 判空操作: 若队列为空, 则返回的值为 true, 否则为 false.
• 出队操作: 当队列非空时, 返回队列头元素的值, 批改队列头指针。
• 入队操作: 将结点插入队尾，批改队尾指针
• 取队头元素操作: 当队列非空时, 返回队列头元素的值，但不删除队列头元素。

栈应用 top 来指向栈顶元素，便于咱们实现入栈出栈操作。那对于队列这种一端进一端出的数据结构，咱们就须要两个变量来实现入队和出队操作，一个指向队头，一个指向队尾。咱们仍然用链式存储构造和顺序存储构造来别离实现队列。

程序队列

对于程序队列来说有两种类型，一种是无限度的队列, 主动扩容，对入队元素数量无限度。一种是限度容量的队列。对入队元素数量有限度。对于无限度的队列，咱们能够仿照之前做线性表的思路，在原先的根底上进行扩大。在原先的根底上从新提供专属于队列的 API，而后入队操作和出队操作在原先的根底上做包装。像上面这样:

public class SequenceQueue extends SequenceList{public void offer(Integer data) {add(data);
    }
    
    public Integer remove() {return remove(size() - 1);
    }

    public Integer peek() {if (size() > 0){return get(0);
        }
        return null;
    }
    
    public boolean empty(){return size() == 0;
    }
    // 清空操作 在 SequenceList 中实现
}

那对于容量限度的队列来说就有一个假溢出的问题，咱们举一个例子来阐明这个问题，假设限度数组的容量为 10，咱们每次出队就是让头指针迁徙，假如当初头指针曾经到了最初，也就是后面的元素曾经都出队了，然而有新元素过去依然不能出队。
即便后面的空间曾经废除掉了，这样队列就只能应用一次，相当鸡肋，所以这种设计存在不合理之处，咱们当然不能让队列只应用一次，那咱们该如何应用后面的废除的空间呢？有两种思路:

• 队头到队尾的元素向废除空间平移，但这种形式比拟浪费时间。
• 将存储区域看做一个首尾相接的环形区域，入队时判断队列曾经满的时候，这个元素就搁置在 0 地位上。

个别咱们采纳第二种形式来解决队列空间的重复使用问题，在结构上采纳这种技巧来存储的队列被称为循环队列。因为循环队列的元素的空间能够被重复使用，除非队列真的全被占用，否则是不会产生上溢出。基本上除了一些简略的利用外，真正实用的程序队列是循环队列。

其实在这里仍然有两种设计, 第一种设计是如果队列全副被占用，那么回绝入队，第二种设计就是笼罩掉之前的元素。其实也能够两种设计都要，提供一个办法给调用者，依据参数的不同来采取不同的策略。其实这也是看源码的意义之一，了解设计者的设计思路。上面是我实现的一个简略循环队列:

public class CircularQueue {
    private int start; 
    private int end;
    private Integer[] elements;
    private int maxElements;
    private boolean full;

    public CircularQueue(int size) {elements = new Integer[size];
        maxElements = size;
    }

    public boolean offer(final Integer element){if(element == null){// 禁止空元素退出}
        // 如果队列曾经满了, 则
        if (isAtFullCapacity()){remove();
        }
        return false;
    }
    
    public Integer poll(){if (isEmpty()){
            // 或给提醒
            return null;    
        }
        return remove();}

    /**
     * 移除元素
     */
    private Integer remove() {if (isEmpty()){// 给出提醒}
        Integer element = elements[start];
        if (null != element){elements[start++] = null;
            // 阐明曾经全面出队
            if (start >= maxElements){start = 0;}
        }
        return element;
    }

    public boolean isEmpty(){return size() == maxElements;
    }

    public boolean isAtFullCapacity() {return size() == maxElements;
    }

    public Integer peek(){if (size() == 0){return null;}
        return elements[start];
    }

    // 如何计算 size
    // 循环队列, end 达到最初被清置 0
    // 所以 start 齐全能够大于 end
    // 刚开始 start == end
    // 在一种状况就是 刚超出被笼罩掉
    public int size(){
        int size = 0;
        // 阐明
        if (end  < start){size = maxElements - start + end;}else if (end == start){size = this.full? maxElements:0;}else {size = end - start;}
        return size;
    }

    public boolean empty(){return  size() == maxElements;
    }
    
    public void clear(){
        full = false;
        start = 0;
        end = 0;
    }
}

链式队列

队列是运算受限的线性表，线性表有两种形式进行存储一种是数组，一种是链表。用链表实现的队列咱们个别称之为链队列。
Java 中也封装了队列这种数据结构，Queue 是接口，LinkedList 是他的一个实现类，咱们来大抵的看一下 LinkedList:

Deque 是双向队列，像是栈和队列的集合体，一般队列只能一端进，一端出。而双向队列就能够做到一端进一端出。咱们在设计数据结构也能够参考 LinkedList 的设计。咱们再讨论一下队列的构造，程序队列的相邻能够依附数组的下标，那么对于链式队列来说就须要再有一个变量来维持各个结点的相邻了。所以链式队列的存储构造就像上面这样:

代码实现如下:

public class LinkedQueue {
    private Node first;
    private Node  last;
    private int size;

    public LinkedQueue() {}

    private class Node{
        private int data;
        private Node next;

        public Node(int data , Node next){
            this.data = data;
            this.next = next;
        }
        public int getData() {return data;}

        public Node getNext() {return next;}
    }

    public boolean empty(){return size == 0;}

    public void clear(){
        first = null;
        last = null;
        size = 0;
    }

    /**
     * 入队操作
     * @param data
     * @return
     */
    public boolean offer(Integer data) {
        Node l = last;
        Node node = new Node(data,null);
        if (l == null){first = node;}else {last.next = node;}
        last = node;
        size++;
        return true;
    }
    /**
     * 可扩大该办法, 当头结点为空时, 可返回 null, 而不是抛出异样
     * @return
     */
    public Integer remove() {
        Node f = first;
        if (f == null){// 队列为空 给出正告}
        first = first.next;
        f = null; // help GC
        size--;
        return first.data;
    }

    public Integer peek() {
         Node f = first;
        return f.data;
    }
}

参考资料

• 《数据结构与算法剖析新视角》周幸妮 任智源 马彦卓 编著 中国工信出版团体