数据结构-队列

队列是一种特殊的线性表，只能在头尾两端进行操作

  • 队尾（rear）：只能从队尾添加元素，一般叫做 enQueue，入队
  • 队头（front）：只能从队头移除元素，一般叫做 deQueue，出队
  • 先进先出的原则，First In First Out，FIFO

队列的接口设计

◼ int size(); // 元素的数量
◼boolean isEmpty();//是否为空
◼void clear();// 清空
◼void enQueue(E element);//入队
◼E deQueue();// 出队
◼E front();// 获取队列的头元素

队列的内部实现可以直接利用前面章节提到的数据结构（动态数组、链表）

优先使用双向链表，因为队列主要是往头尾操作元素

package com.njf;

public class Queue<E> {
    
    private DoublyLinkedList<E> list = new DoublyLinkedList<>();
    
    public int size() {
        return list.size();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
    
    public void clear() {
        list.clear();
    }

    public void enQueue(E element) {
        list.add(element);
    }

    public E deQueue() {
        return list.remove(0);
    }

    public E front() {
        return list.get(0);
    }
}

代码调用

package com.njf;

public class Main {

    public static void main(String[] args) {
        Queue<Integer> queue = new Queue<>();
        queue.enQueue(11);
        queue.enQueue(22);
        queue.enQueue(33);
        queue.enQueue(44);
        
        while (!queue.isEmpty()) {
            System.out.println(queue.deQueue());
        }

    }
}

出队结果

11
22
33
44

双端队列（Deque）

双端队列是能在头尾两端添加、删除的队列，英文 deque 是 double ended queue 的简称

接口设计

◼ int size();// 元素的数量
◼ boolean isEmpty(); // 是否为空
◼void clear();//清空
◼ void enQueueRear(E element);// 从队尾入队
◼ E deQueueFront(); // 从队头出队
◼ void enQueueFront(E element);// 从队头入队
◼ E deQueueRear(); // 从队尾出队
◼ E front(); // 获取队列的头元素
◼ E rear();// 获取队列的尾元素

代码实现

package com.njf;

public class Deque<E>  {
    private DoublyLinkedList<E> list = new DoublyLinkedList<>();
    
    public int size() {
        return list.size();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
    
    public void clear() {
        list.clear();
    }

    public void enQueueRear(E element) {
        list.add(element);
    }

    public E deQueueFront() {
        return list.remove(0);
    }

    public void enQueueFront(E element) {
        list.add(0, element);
    }

    public E deQueueRear() {
        return list.remove(list.size() - 1);
    }

    public E front() {
        return list.get(0);
    }

    public E rear() {
        return list.get(list.size() - 1);
    }
}

代码调用

package com.njf;

public class Main {

    public static void main(String[] args) {
        Deque<Integer> queue = new Deque<>();
        queue.enQueueFront(11);
        queue.enQueueFront(22);
        queue.enQueueRear(33);
        queue.enQueueRear(44);
        /* 尾  44  33   11  22 头 */
        while (!queue.isEmpty()) {
            System.out.println(queue.deQueueRear());
        }
    }
}

队尾出队结果

44
33
11
22

循环队列（Circle Queue）

◼ 其实队列底层也可以使用动态数组实现，并且各项接口也可以优化到 O(1) 的时间复杂度
◼ 这个用数组实现并且优化之后的队列也叫做：循环队列

front指针的改变只针对：队头的操作（在队头添加和删除元素）

代码实现

package com.njf;
@SuppressWarnings("unchecked")

public class CircleQueue<E> {
    private E[] elements;
    private int size;
    private int front;
    private static final int DEFAULT_CAPACITY = 10;
    
    public CircleQueue() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }
    
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[index(i)] = null;
        }
        front = 0;
        size = 0;
    }

    public void enQueue(E element) {
        ensureCapacity(size + 1);
        elements[index(size)] = element;
        size ++;
    }

    public E deQueue() {
        E frontElement = elements[front];
        elements[front] = null;
        front = index(1);
        size --;
        return frontElement;
    }

    public E front() {
        return elements[front];
    }
    
    /**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[index(i)];
        }
        elements = newElements;
        // 重置front
        front = 0;
    }
    
    private int index(int index) {
        return (front + index)%elements.length;
    }
    
    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("capcacity=").append(elements.length)
        .append(" size=").append(size)
        .append(" front=").append(front)
        .append(", [");
        for (int i = 0; i < elements.length; i++) {
            if (i != 0) {
                string.append(", ");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }
}

代码调用

package com.njf;

public class Main {

    public static void main(String[] args) {
        test();
    }
    static void test() {
        CircleQueue<Integer> queue = new CircleQueue<Integer>();
        // 0 1 2 3 4 5 6 7 8 9
        for (int i = 0; i < 10; i++) {
            queue.enQueue(i);
        }
        // null null null null null 5 6 7 8 9
        for (int i = 0; i < 5; i++) {
            queue.deQueue();
        }
        // 15 16 17 18 19 5 6 7 8 9
        for (int i = 15; i < 25; i++) {
            queue.enQueue(i);
        }
        System.out.println(queue);
        queue.clear();
        System.out.println(queue);
    }
}

显示结果

capcacity=15 size=15 front=0, [5, 6, 7, 8, 9, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
capcacity=15 size=0 front=0, [null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]

循环双端队列

代码实现

package com.njf;
@SuppressWarnings("unchecked")

public class CircleDeque<E> {
    private E[] elements;
    private int size;
    private int front;
    private static final int DEFAULT_CAPACITY = 10;
    
    public CircleDeque() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }
    
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[index(i)] = null;
        }
        front = 0;
        size = 0;
    }

    /**
     * 从尾部入队
     * @param element
     */
    public void enQueueRear(E element) {
        ensureCapacity(size + 1);
        elements[index(size)] = element;
        size ++;
    }

    /**
     * 从头部出队
     * @param element
     */
    public E deQueueFront() {
        E frontElement = elements[front];
        elements[front] = null;
        front = index(1);
        size --;
        return frontElement;
    }

    /**
     * 从头部入队
     * @param element
     */
    public void enQueueFront(E element) {
        ensureCapacity(size + 1);
        front = index(-1);
        elements[front] = element;
        size ++;
    }

    /**
     * 从尾部出队
     * @param element
     */
    public E deQueueRear() {
        int rearIndex = index(size - 1);
        E rear = elements[rearIndex];
        elements[rearIndex] = null;
        size --;
        return rear;
    }

    public E front() {
        return elements[front];
    }

    public E rear() {
        return elements[index(size -1)];
    }
    /**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[index(i)];
        }
        elements = newElements;
        // 重置front
        front = 0;
    }
    
    private int index(int index) {
        index += front;
        if (index < 0) {
            return index + elements.length;
        }
        return index%elements.length;
    }
    
    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("capcacity=").append(elements.length)
        .append(" size=").append(size)
        .append(" front=").append(front)
        .append(", [");
        for (int i = 0; i < elements.length; i++) {
            if (i != 0) {
                string.append(", ");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }
}

代码调用

package com.njf;

public class Main {

    public static void main(String[] args) {
        test();
    }
    static void test() {
        CircleDeque<Integer> queue = new CircleDeque<>();
        // 头5 4 3 2 1  100 101 102 103 104 105 106 8 7 6 尾
        // 头 8 7 6  5 4 3 2 1  100 101 102 103 104 105 106 107 108 109 null null 10 9 尾
        for (int i = 0; i < 10; i++) {
            queue.enQueueFront(i + 1);
            queue.enQueueRear(i + 100);
        }
        // 头 null 7 6  5 4 3 2 1  100 101 102 103 104 105 106 null null null null null null null 尾
        for (int i = 0; i < 3; i++) {
            queue.deQueueFront();
            queue.deQueueRear();
        }
        // 头 11 7 6  5 4 3 2 1  100 101 102 103 104 105 106 null null null null null null 12 尾
        queue.enQueueFront(11);
        queue.enQueueFront(12);
        System.out.println(queue);
        while (!queue.isEmpty()) {
            System.out.println(queue.deQueueFront());
        }
    }
}

显示结果

capcacity=22 size=16 front=21, [11, 7, 6, 5, 4, 3, 2, 1, 100, 101, 102, 103, 104, 105, 106, null, null, null, null, null, null, 12]
12
11
7
6
5
4
3
2
1
100
101
102
103
104
105
106

%运算符优化

尽量避免使用乘*、除/、模%、浮点数运算，效率低下

 private int index(int index) {
        return (front + index)%elements.length;
    }

优化

private int index(int index) {
    front += index;
    return index - (index >= elements.length ? elements.length : 0);
}

已知n>=0，m>0
n%m 等价于 n – (m > n ? 0 : m) 的前提条件：n < 2m

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,163评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,301评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,089评论 0赞 352
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,093评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,110评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,079评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,005评论 3赞 417
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,840评论 0赞 273
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,278评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,497评论 2赞 332
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,667评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,394评论 5赞 343
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,980评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,628评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,796评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,649评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,548评论 2赞 352