队列： 先进先出(FIFO)。
优先级队列： 在优先级队列中，数据项按照关键字的值有序，关键字最小的数据项总在对头，数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序，从后往前将小于插入项的数据项后移。在图的最小生成树算法中应用优先级队列。
示例代码：
package chap04.Queue;
class Queue {
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
public Queue(int s) {
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
// 插入方法，队尾是数组的最后一项
public void insert(long j) {
if (rear == maxSize - 1) {
rear = -1;
}
queArray[++rear] = j;
nItems++;
}
// 先进先出
public long remove() {
long temp = queArray[front++];
if (front == maxSize) {
front = 0;
}
nItems--;
return temp;
}
public long peekFront() {
return queArray[front];
}
public boolean isEmpty() {
return (nItems == 0);
}
public boolean isFull() {
return (nItems == maxSize);
}
public int size() {
return nItems;
}
}
class PriorityQ {
private int maxSize;
private long[] queArray;
private int nItems;
public PriorityQ(int s) {
maxSize = s;
queArray = new long[maxSize];
nItems = 0;
}
// 插入方法，从大到小排列
public void insert(long item) {
int j;
if (nItems == 0) {
queArray[nItems++] = item;
}
else {
for (j = nItems - 1; j >= 0; j--) {
if (item > queArray[j]) { // if new item larger,
queArray[j + 1] = queArray[j];
}
else {
break;
}
}
queArray[j + 1] = item;
nItems++;
}
}
// 按照优先级从后往前移除，不再跟先进还是后进有关
public long remove() {
return queArray[--nItems];
}
public long peekMin() {
return queArray[nItems - 1];
}
public boolean isEmpty() {
return (nItems == 0);
}
public boolean isFull() {
return (nItems == maxSize);
}
}
class QueueApp {
public static void main(String[] args) {
Queue theQueue = new Queue(5);
theQueue.insert(10);
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove();
theQueue.remove();
theQueue.remove();
theQueue.insert(50);
theQueue.insert(60);
theQueue.insert(70);
theQueue.insert(80);
while (!theQueue.isEmpty()) {
long n = theQueue.remove();
System.out.print(n); // 40, 50, 60, 70, 80
System.out.print(" ");
}
System.out.println("");
PriorityQ thePQ = new PriorityQ(5);
thePQ.insert(30);
thePQ.insert(50);
thePQ.insert(10);
thePQ.insert(40);
thePQ.insert(20);
while (!thePQ.isEmpty()) {
long item = thePQ.remove();
System.out.print(item + " "); // 10, 20, 30, 40, 50
}
System.out.println("");
}
}