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)，后续堆数据结构将改进他。