数据结构：队列

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。队列中没有元素时，称为空队列。

队列特点：先进先出(FIFO)

队列的结构
如下图所示：

线性表的操作主要包括：
（1）清空队列
（2）判断是否为空
（3）元素的个数
（4）入队列
（5）出队列
（6）取对头元素

接口

package queue;  

public interface Queue {  
    /** 
     * 清空队列 
     */  
    public void clear();  
    /** 
     * 出队列 
     * @return 
     */  
    public Object deQueue();  
    /** 
     * 判断是否为空 
     * @return 
     */  
    public boolean isEmpty();  
    /** 
     * 取对头元素 
     * @return 
     */  
    public Object peek();  
    /** 
     * 入队列 
     * @param obj 
     */  
    public void push(Object obj);  
    /** 
     * 元素的个数 
     * @return 
     */  
    public int size();  
} 

顺序循环队列

结构模型

•存在问题
设数组长度为M，则：
–当front=0,rear=M时，再有元素入队发生溢出——真溢出
–当front!=0,rear=M时，再有元素入队发生溢出——假溢出
•解决方案
–队首固定，每次出队剩余元素向下移动——浪费时间
–循环队列
»基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;

源代码 （把队列想成环形,越增加越大,除非出队）

package queue;  
/** 
 * 顺序循环队列 
 * @author Administrator 
 * 
 */  
public class ArrayQueue implements Queue {  
    private static  int  DEFAULT_SIZE = 10;   
    private Object array[] = null;  
    private int front, rear, count; //队首，队尾标注和队列的大小  

    public ArrayQueue() {  
        array = new Object[DEFAULT_SIZE];  
        front = rear = count = 0;  
    }  

    public boolean isEmpty() {  
        if((rear == front) && (0 == count))  
            return true;  
        else  
            return false;  
    }  

    public int size() {  
        return count;  
    }  

    @Override  
    public void push(Object obj) {  
        if((rear == front) && (count>0))  
            expand();  
        array[rear] = obj;  
        rear = (rear+1)%DEFAULT_SIZE;  
        count ++;  
    }  

    @Override  
    public Object deQueue() {  
        if(0 == count) {  
            throw new IllegalStateException("队列已空，无数据元素可出队列！");  
        } else {  
            Object obj = array[front];  
            front = (front+1)%DEFAULT_SIZE;  
            count --;  
            return obj;  
        }  
    }  


    @Override  
    public Object peek() {  
        if(0 == count) {  
            throw new IllegalStateException("队列已空，无数据元素可出队列！");  
        } else return array[front];  
    }  

    @Override  
    public void clear() {  
        for(int i=0; i<DEFAULT_SIZE; i++) {  
            array[i] = null;  
        }  
        front = rear = count = 0;  
    }  

    private void expand() {  
            Object newArray[] = new Object[2*DEFAULT_SIZE];  
            for(int i=0; i<count; i++) {  
                newArray[i] = array[(front+i)%DEFAULT_SIZE];  
            }  
            array = newArray;  
            front = 0;   
            rear = count;  
            DEFAULT_SIZE = 2*DEFAULT_SIZE;  
    }  

    public String toString() {  
        String str= "[";  
        for(int i=0; i<count; i++) {  
            str =str + array[(front+i)%DEFAULT_SIZE];  
            str += ",  ";  
        }  
        str += "]";  
        return str;   
    }  

}  

链式队列

结构模型

设队首、队尾指针front和rear,front指向头结点，rear指向队尾

源代码

package queue;  

/** 
 * 链队列的结点 
 * @author luoweifu 
 * 
 */  
class Node{  
    Object data;    //数据元素  
    Node next;      //后驱结点  
    public Node() {  
        this(null);  
    }  
    public Node(Object data) {  
        this.data = data;  
        this.next = null;  
    }  
}  
/** 
 * 链队列 
 * @author Administrator 
 * 
 */  
public class LinkQueue implements Queue{  
    private Node front,rear;    //队头指针和队尾指针  
    private int size;  
    public LinkQueue() {  
        front = rear = new Node();  
        size = 0;  
    }  
    @Override  
    public void clear() {  
        front.next = null;  
        rear = front;  
        size = 0;  
    }  

    @Override  
    public Object deQueue() {  
        Node p = front.next;  
        front.next = p.next;  
        rear = p.next;  //----------深思ing---------
        size --;  
        return p.data;  
    }  

    @Override  
    public boolean isEmpty() {  
        if(size == 0)  
            return true;  
        else   
            return false;  
    }  

    @Override  
    public Object peek() {  
        return front.next.data;  
    }  

    @Override  
    public void push(Object obj) {  
        Node p = new Node(obj);  
        rear.next = p;  
        rear = p;  
        size ++;  
    }  

    @Override  
    public int size() {  
        return size;  
    }  

    public String toString() {  
        StringBuilder sb= new StringBuilder("[");  
        Node p = front;  
        while((p=p.next) != null) {  
            sb.append(p.data + ", ");  
        }  
        sb.append("]");  
        return sb.toString();     
    }  
}

测试队列

package queue;  

public class Test {  
    /** 
     * 测试队列 
     * 测试结果：各项功能正确无误 
     * @param args 
     */  
    public static void main(String[] args) {  
        //Queue queue = new LinkQueue();  
        Queue queue = new ArrayQueue();  
        for(int i=0; i<10; i++) {  
            queue.push(i);  
        }  
        System.out.println(queue);  
        Object obj1 = queue.deQueue();  
        Object obj2 = queue.deQueue();  
        System.out.println("count:" + queue.size() + "  obj1:" + obj1 + "  obj2:" + obj2);  
        System.out.println(queue);  
        System.out.println("peek:" + queue.peek());  
        //System.out.println(test.toString());  

        for(int i=0; i<12; i++) {  
            queue.push(i+10);  
        }  
    }  
}

结果

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ]
count:8 obj1:0 obj2:1
[2, 3, 4, 5, 6, 7, 8, 9, ]
peek:2

感觉链表都是要注意指针的走动

转载：https://blog.csdn.net/luoweifu/article/details/8507835