一、队列的特点

1. 先进先出：从队尾进、队头出。

二、队列的实现

需提供的方法
// 队是否为空
public boolean isEmpty() 
// 从队尾进队（用数组实现时：若队满则扩充容量后进队）
public void enqueue(E data) 
// 返回并删除队头出队
public E dequeue()
// 返回队头元素，但不删除
public E peek()
// 打印队中元素
public void print()

2.1 基于数组实现顺序队列（泛型）

维护队头指针head，队尾指针tail，初始值都为-1。
进队时：先将tail加1，将元素放在该位置；
出队时：head加1，返回该位置元素。（有的文章中说将头指针和尾指针初始化为0，都可以，此处用-1初始化）

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * 
 * <p>
 * Description: 队列：用数组、泛型实现
 * </p>
 * 
 * @author 杨丽金
 * @date 2018-4-1
 * @version 1.0
 */
public class MyQueue_array_generic<E> {
    // 用数组存储队列元素
    E[] queue;
    // 队头指针
    int head = -1;

    // 队尾指针
    int tail = -1;
    // 默认数组容量
    private static final int DEFAULT_SIZE = 3;

    // 构造函数中进行初始化
    public MyQueue_array_generic(Class<E> type) {
        this(type, DEFAULT_SIZE);
    }

    public MyQueue_array_generic(Class<E> type, int size) {
        queue = (E[]) Array.newInstance(type, size);
    }

    /**
     * 从队尾进队
     * 
     * @param data
     */
    public void enqueue(E data) {
        ensureCapacity();
        queue[++tail] = data;

    }

    private void ensureCapacity() {
        if (isFull()) {
            int newLength = queue.length * 2;
            queue = Arrays.copyOf(queue, newLength);
        }
    }

    /**
     * 返回并删除队头出队
     * 
     * @return
     */
    public E dequeue(){
        E r=peek();
        head++;
        return r;
    }
    
    /**
     * 返回队头元素，但不删除
     * @return
     */
    public E peek(){
        if(isEmpty()){
            throw new NoSuchElementException();
        }else{
            return queue[head+1];
        }
    }

    /**
     * 队是否为空
     * 
     * @return
     */
    public boolean isEmpty() {
        return tail==head;
    }

    /**
     * 是否满
     * 
     * @return
     */
    public boolean isFull() {
        return tail == queue.length - 1;
    }
    
    /**
     * 打印队中元素
     */
    public void print(){
        if(isEmpty()){
            return;
        }else{
            int cur=head+1;
            // 
            while(cur!=(tail+1)){// 循环条件
                System.out.print(queue[cur++]+" ");// 迭代条件
            }
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        MyQueue_array_generic<Integer> q=new MyQueue_array_generic<Integer>(Integer.class);
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        q.enqueue(4);
        q.enqueue(5);
        q.enqueue(6);
        q.print();
        System.out.println(String.format("队头元素为:%s", q.peek()));
        q.dequeue();
        q.dequeue();
        q.print();
        System.out.println(String.format("队头元素为:%s", q.peek()));
    }

}

运行结果.png

2.2 基于链表实现顺序队列

维护队头指针head，队尾指针tail，初始值都为null。队空状态为：head==null

import java.util.NoSuchElementException;

/**
 * 
 * <p>
 * Description: 队列：用链表、泛型实现
 * </p>
 * 
 * @author 杨丽金
 * @date 2018-4-1
 * @version 1.0
 */
public class MyQueue_linkedList<E> {
    class Node {
        // 数据域
        E data;
        // 指针域
        Node next;

        public Node(E data) {
            this.data = data;
        }
    }

    // 队头指针
    private Node head = null;
    // 队尾指针
    private Node tail = null;

    // 从队尾进队
    public void enqueue(E data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            // 若队为空，则将head和tail都指向节点
            // 队列是从队尾入队，但队为空时入队要把head指向新节点（因为不指向的话head没法和队列关联起来）
            head = newNode;
            tail = newNode;
        } else {
            // 若不为空，则将tail.next指向新节点，tail指向新节点
            tail.next = newNode;
            tail = newNode;
        }
    }

    // 返回并删除队头出队
    public E dequeue() {
        E r = peek();
        head = head.next;
        return r;
    }

    // 返回队头元素的值，但不删除
    public E peek() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        } else {
            return head.data;
        }
    }

    // 打印队中元素
    public void print() {
        Node cur = head;
        while (cur != tail) {
            System.out.print(cur.data + " ");
            cur = cur.next;// 迭代条件
        }
        System.out.println(tail.data);
    }

    // 队是否为空
    public boolean isEmpty() {
        // head为空说明队列中没元素了
        return head == null;
    }

    public static void main(String[] args) {
        MyQueue_linkedList<Integer> q = new MyQueue_linkedList<Integer>();
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        q.enqueue(4);
        q.enqueue(5);
        q.enqueue(6);
        q.print();
        System.out.println(String.format("队头元素为:%s", q.peek()));
        q.dequeue();
        q.dequeue();
        q.print();
        System.out.println(String.format("队头元素为:%s", q.peek()));
    }

}

2.3 循环队列

普通的队列存在的情况是队尾指针已经=length-1，为队满状态，但前面还有很多闲置空间， 造成假溢出，即数组空间还有很多、但队列已经是满的状态不能入队，所以用循环队列改进。
特点：1. 循环队列必须损失一个存储空间，否则无法区分对空队满状态

/**
 * 
 * <p>
 * Description: 循环队列，基于int[]实现
 * </p>
 * 
 * @author 杨丽金
 * @date 2018-4-2
 * @version 1.0
 */
public class MyCircleQueue_array_int {

    // 默认数组长度
    private static final int MAX_SIZE = 4;
    // 数组存储队列元素
    private int[] queue;
    // 队头指针（循环队列，就要损失一个存储空间）
    private int head = 0;
    // 队尾指针
    private int tail = 0;

    public MyCircleQueue_array_int() {
        // 初始化操作
        queue = new int[MAX_SIZE];
    }

    /**
     * 从队尾进队，队满则扩充容量后再进队
     * 
     * @param data
     * @throws Exception
     */
    public void enqueue(int data) throws Exception {
        if (isFull()) {
            throw new Exception("队列已满不可入队");
        }
        tail = (tail + 1) % MAX_SIZE;
        queue[tail] = data;
    }

    private boolean isFull() {
        return (tail + 1) % MAX_SIZE == head;
    }

    /**
     * 返回并删除队头出队
     * 
     * @return
     * @throws Exception 
     */
    public int dequeue() throws Exception {
        int r = peek();
        head = (head + 1) % MAX_SIZE;
        return r;
    }

    /**
     * 返回队头元素，但不删除
     * 
     * @return
     * @throws Exception 
     */
    public int peek() throws Exception {
        if (isEmpty()) {
            throw new Exception("当前队列为空");
        } else {
            return queue[(head + 1) % MAX_SIZE];
        }
    }

    // 队是否为空
    public boolean isEmpty() {
        return head == tail;
    }

    // 从队尾进队（用数组实现时：若队满则扩充容量后进队）
    // 打印队中元素
    public void print() {
        if (isEmpty()) {
            System.out.println("当前队列为空");
        } else {
            int i = head + 1;
            while (i <= tail) {
                System.out.print(queue[i] + " ");
                i++;// 迭代条件
            }
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        MyCircleQueue_array_int m= new MyCircleQueue_array_int();
        try {
            m.enqueue(1);
            m.enqueue(2);
            m.enqueue(3);
//          m.enqueue(4);// 因为MAX_SIZE=4，故队列中最多可放3个元素
            m.print();
            System.out.println("队头元素："+m.peek());
            // 将1出队
            m.dequeue();
            m.print();// 2,3
            // 将2出队
            m.dequeue();// 3
            m.print();
            // 将3出队
            m.dequeue();
            m.print();// 队空
            m.dequeue();// 抛出异常
            m.print();
        } catch (Exception e) {
            e.printStackTrace();
        }
        
    }
}

三、队列的应用

1. 树的层次遍历