数据结构与算法之队列

1. 基本知识

1.1 基本概念

队列也是一种受限制的线性表，可以由数组和链表实现，主要操作由入队和出队，具有先进进出的特点。

1.2 分类

1. 顺序队列：数组实现，需要解决假溢出问题，需要搬迁数据；
2. 链式队列：链表实现；
3. 循环队列：解决假溢出问题，性能较高；
4. 阻塞队列：在队列的基础上增加了阻塞条件，队列为空，出队阻塞；队列已满，入队阻塞，典型的“生产者-消费者模型”；
5. 并发队列：在入队和出队的方法上加锁，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。

1.3 基本操作

6. 入队 enQueue(T data)
7. 出队 deQueue()
8. 获取队列第一个元素 top()
9. 是否为空

1.4 假溢出

假溢出是由队尾 tail 的值和队头 head 的值不能由所定义的数组下界值自动转为数组上界值而产生的.

解决方案：
  1. 入队时 (tail + 1) / capacity
  2. 出队时 (head + 1) / capacity
  3. 判断队满 size > 0 && tail == head

2. 实现

2.1 循环队列

package com.baidu.test.construct.queue;

import java.util.Arrays;

/**
 * 顺序队列
 * @param <T>
 */
public class ArrayQueue<T> {

    // 默认容量
    private final static int DEFAULT_CAPACITY = 10;

    // 数据
    private Object[] datas;

    // 容量
    private int capacity;

    // 长度
    private int size;

    // 对头下标
    private int head;

    // 队尾下标
    private int tail;

    public ArrayQueue() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        this.datas = new Object[capacity];
        this.size = 0;
        this.head = 0;
        this.tail = 0;
    }

    public void enQueue(T data) {
        if (size > 0 && head == tail) {
            throw new RuntimeException("队列已满");
        }
        datas[tail] = data;
        tail = (tail + 1) % capacity;
        size++;
    }

    public T deQueue() {
        if (size == 0) {
            throw new RuntimeException("队列已空");
        }
        T data = (T) datas[head];
        head = (head + 1) % capacity;
        size--;
        return data;
    }

    public T top() {
        return (T) datas[head];
    }

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


    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        queue.enQueue(1);
        queue.enQueue(2);
        queue.enQueue(3);
        queue.enQueue(4);
        System.out.println(queue.isEmpty());
        System.out.println(queue.top());
        System.out.println("出队：");
        System.out.print(queue.deQueue() + "，");
        System.out.print(queue.deQueue() + "，");
        System.out.print(queue.deQueue() + "，");
        System.out.print(queue.deQueue() + "，");
        System.out.println("入队：");
        queue.enQueue(5);
        queue.enQueue(6);
        queue.enQueue(7);
        queue.enQueue(8);
        queue.enQueue(9);
        queue.enQueue(10);
        queue.enQueue(11);
        queue.enQueue(12);
        queue.enQueue(13);
        queue.enQueue(14);
        System.out.println(Arrays.toString(queue.datas));
        System.out.println("出队：");
        System.out.print(queue.deQueue() + "，");
        System.out.print(queue.deQueue() + "，");
        System.out.print(queue.deQueue() + "，");
        System.out.print(queue.deQueue() + "，");
    }
}

2.2 链式队列

package com.baidu.test.construct.queue;

/**
 * 链式队列
 * @param <T>
 */
public class LinkedListQueue<T> {

    private Node<T> head;
    private Node<T> current;
    private int size;

    public LinkedListQueue() {
        this.head = this.current = new Node<>(null, null);
        this.size = 0;
    }

    public void enQueue(T data) {
        head.next = new Node<>(data, head.next);
        size++;
    }

    public T deQueue() {
        index(size-2);
        Node<T> node = current.next;
        current.next = node.next;
        size--;
        return node.data;
    }

    public T top() {
        index(size-1);
        return current.data;
    }

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

    private void index(int index) {
        if (index < -1 || index > size -1) {
            throw new IndexOutOfBoundsException();
        }

        if (index == -1) {
            current = head;
            return;
        }

        current = head.next;
        int i=0;
        while (i<index) {
            current = current.next;
            i++;
        }
    }

    private void print() {
        current = head.next;
        while (current != null) {
            System.out.print(current.data + "->");
            current = current.next;
        }
    }

    private static class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        queue.enQueue(1);
        queue.enQueue(2);
        queue.enQueue(3);
        queue.enQueue(4);
        System.out.println(queue.isEmpty());
        System.out.println(queue.top());
        System.out.println("出队：");
        System.out.print(queue.deQueue() + "，");
        System.out.print(queue.deQueue() + "，");
        System.out.print(queue.deQueue() + "，");
        System.out.print(queue.deQueue() + "，");
        System.out.println("入队：");
        queue.enQueue(5);
        queue.enQueue(6);
        queue.enQueue(7);
        queue.enQueue(8);
        queue.enQueue(9);
        queue.enQueue(10);
        queue.enQueue(11);
        queue.enQueue(12);
        queue.enQueue(13);
        queue.enQueue(14);
        queue.print();
        System.out.println("出队：");
        System.out.print(queue.deQueue() + "，");
        System.out.print(queue.deQueue() + "，");
        System.out.print(queue.deQueue() + "，");
        System.out.print(queue.deQueue() + "，");
    }
}