数据结构之队列的java实现

　队列在计算机术语中使用queue,和list(排)其实是一个意思。队列也是一种数据结构，类似于栈，只是与栈相反，在队列中最先插入的数 据也最先被移除，即先进先出(FIFO,First In First Out)。队列可以理解成排队，比如，食堂窗口排的队，越在前面的，越早得到服务而先离开。在银行大厅的排号的机器也许就用了队列这个数据结构。在打印的 时候，有“添加到队列”的选项，队列应用是很广泛的。

　　队列的操作有：插入到队尾数据项，移除队头数据项，查看数据项等功能。

　　下面用Java实现队列的基本功能（数组版）。

package cn.zhf.list;
public class MyQueue {
private int maxSize;//定义最大容量
private int[] qarray;//存放元素的数组
private int front;//前一个元素索引
private int rear;//后一个元素索引
private int nItems;//队列中元素的个数
//构造对象并初始化
public MyQueue(int s){
maxSize = s;
qarray = new int[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//在队列尾端插入元素
public void enqueue(int i){
if(rear == maxSize - 1){
rear = -1;
}
qarray[++rear] = i;
nItems++;
}
//删除队首元素
public int dequeue(){
int temp = qarray[front++];
if(front == maxSize){
front = 0;
}
nItems--;
return temp;
}
public int peekFront(){//取第一个元素
return qarray[front];
}
public boolean isEmpty(){
return (nItems == 0);
}
public static void main(String[] args) {
MyQueue queue = new MyQueue(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
while(!queue.isEmpty()){
int i = queue.dequeue();
System.out.println(i);
}
}
}

 

package cn.zhf.list;
//其中的Link和LinkList两类同栈中的相同
public class LinkQueue {
private LinkList list;
public LinkQueue(){
list = new LinkList();
}
public boolean isEmpty(){
return list.isEmpty();
}
public void insert(int id,double dd){
list.insertFirst(id, dd);
}
public Link delete(){
return list.deleteFirst();
}
public void display(){
list.displayLink();
}
public static void main(String[] args) {
LinkQueue lq = new LinkQueue();
lq.insert(12, 20.0);
lq.insert(13, 20.1);
lq.insert(14, 20.2);
lq.display();
System.out.println("-----------");
lq.delete();
lq.display();
}
}

 　运行结果：

14,20.2
13,20.1
12,20.0
-----------
13,20.1
12,20.0

 

评论

1 楼 EXvision 2014-03-10  

JDK的LinkedList就是实现了Queue及Deque的队列。