java数据结构----队列，优先级队列

1.队列：和栈中的情况不同，队列中的数据项不总是从数组下标0开始，移除一个数据项后，队头指针会指向下标较高的数据项，其特点：先入先出

2.图解

 

 3.队列的实现代码：

　　3.1.Queue.java

package com.cn.queue;
/**
 * 数据结构之队列实现
 * @author Administrator
 *
 */
public class Queue {
private int maxsize;
private long[] queuearray;
private int front;
private int rear;
private int nItems;
public Queue(int s){
    maxsize = s;
    queuearray = new long[maxsize];
    front = 0;
    rear = -1;
    nItems = 0;
}
public void insert(long j){
    if (rear == maxsize - 1)
        rear = -1;
    queuearray[++ rear] = j;
    nItems ++;
}
public long remove(){
    long temp = queuearray[front ++];
    if (front == maxsize)
        front = 0;
    nItems --;
    return temp;
}
public long peekFront(){
    return queuearray[front];
}
public boolean isEmpty(){
    return (nItems == 0);
}
public boolean isFull(){
    return (nItems == maxsize);
}
public int size(){
    return nItems;
}

}

　　3.2.QueueTest.java

package com.cn.queue;

public class QueueTest {
public static void main(String[] args) {
    Queue q = new Queue(100);
    q.insert(100);
    q.insert(200);
    q.insert(300);
    while (q.size()!=0){
        System.out.print(q.remove()+"   ");
    }
    System.out.println("");
    System.out.println(q.isEmpty());
}
}

4.队列插入和删除的时间复杂度和栈的一样，都是O(1)

5.优先级队列：优先级队列是比栈和队列更加专用的数据结构，他有一个队头和队尾，并且也是从队头移除数据项，不过在优先级队列中，数据项按关键字的值有序，这样关键字最小的数据项总是在队头，而最大的就在队尾。做插入操作时会按照顺序插入到合适的位置以确保队列的顺序。除了可以快速访问最小关键值的数据项，优先队列还必须实现非常快的插入数据项，由此，优先级队列通常使用一种称为堆得数据结构实现。本程序暂时使用数组实现，该实现的插入比较慢，适用于数据量小，并且对速度要求并不高场景。

6.优先级队列的实现：

　　6.1.PriorityQ.java

package com.cn.queue;
/**
 * 优先级队列的实现代码
 * @author Administrator
 *
 */
public class PriorityQ {
private int maxsize;
private long[] queuearray;
private int nItems;
public PriorityQ(int s){
    maxsize = s;
    queuearray = new long[maxsize];
    nItems = 0;
}
public void insert(long item){
    int k;
    if (nItems == 0)
        queuearray[nItems ++] = item;
    else{
        for(k = nItems - 1;k >= 0;k --){
            if (item > queuearray[k])
                queuearray[k + 1] = queuearray[k];
            else
                break;
        }
        queuearray[k + 1] = item;
        nItems ++;
    }
}
public long remove(){
    return queuearray[-- nItems];
}
public long peekmin(){
    return queuearray[nItems - 1];
}
public boolean isEmpty(){
    return (nItems == 0);
}
public boolean isFull(){
    return (nItems == maxsize);
}
}

　　6.2图解

7.优先级队列的效率：插入操作时间复杂度位O(N),删除操作时间复杂度为O(1)，后续堆数据结构将改进他。